Optimal aspect ratios of building blocks in VLSI

The building blocks in a given floor-plan may have several possible physical implementations yie1din.g dif-ferent 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 bfranch and bound algorithm which proves to be very eflicient and can handle successfully large general non-slicing floorplans. We show also how the non-slicing and the slicing algorithms can be combined to handle effi-ciently very large general floorplans. 1.