Optimal aspect ratios of building blocks in VLSI

摘要

The building blocks in a given floorplan have several possible physical implementations yielding different layouts. A discussion is presented of 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 (nonslicing) floorplans the problem is NP-complete. The authors suggest a branch-and-bound algorithm which proves to be very efficient and can handle successfully large general nonslicing floorplans. The high efficiency of the algorithm stems from the branching strategy and the bounding function used 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, the authors show how the nonslicing and the slicing algorithms can be combined to handle efficiently very large general floorplans.