A unified approach to topology generation and optimal sizing of floorplans

Existing algorithms for floorplan topology generation by rectangular dualization 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 sized floorplan, is produced first in a top-down fashion by an AI-based search 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 generation with minimal number of nonslice cores, (3) guaranteed safe routing order without addition of pseudo modules, and (4) design of an efficient bottom-up heuristic for optimal sizing. Experimental results show that this integrated method elegantly solves floorplan optimization problem for general including inherently nonslicible adjacency graphs