About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Paper
Optimal Aspect Ratios of Building Blocks in VLSI
Abstract
The building blocks in a given floorplan may have several possible physical implementations yielding different layouts. This paper discusses the problem of selecting an optimal implementation for each building block so that the area of the final layout is minimized. A polynomial algorithm that solves this problem for slicing floorplans was presented elsewhere, and it has been proved that for general (non-slicing) floorplans the problem is NP-complete. We suggest a branch and bound algorithm which proves to be very efficient and can handle successfully large general non-slicing floorplans. The high efficiency of the algorithm stems from the branching strategy and the bounding function employed in the search procedure. The branch and bound algorithm is supplemented by a heuristic minimization procedure which further prunes the search, is computationally efficient and does not prevent achieving a global minimum. Finally, we show how the nonslicing and the slicing algorithms can be combined to handle efficiently very large general floorplans. © 1989 IEEE