A UNIFIED APPROACH TO TOPOLOGY GENERATION AND OPTIMAL SIZING OF FLOORPLANS

Existing algorithms for floorplan topology generation by rectangular d ualization usually do not consider sizing issues. In this paper, given a rectangularly dualizable adjacency graph and a set of aspect ratios of the modules, a topology which is likely to yield an optimally size d floorplan, is produced first in a top-down fashion by an AI-based se arch technique with novel heuristic estimates based on size parameters . It is shown that for any rectangular graph, there exists a feasible topology using only either straight or Z-cutlines recursively within a bounding rectangle. The significance of this result is four-fold: 1) considerable acceleration of the heuristic search, 2) topology generat ion with minimal number of nonslice cores, 3) guaranteed safe routing order without addition of pseudo modules, and 4) design of an efficien t bottom-up heuristic for optimal sizing. Experimental results show th at this integrated method elegantly solves floorplan optimization prob lem for general including inherently nonslicible adjacency graphs.