Floorplanning using a tree representation

We present an ordered tree (O tree) structure to represent nonslicing floorplans, The O tree uses only n(2 + inverted right perpendicular lg n inverted left perpendicular) bits for a floorplan of n, rectangular blocks. We define an admissible placement as a compacted placement in both a: and y directions. For each admissible placement, we can find an O-tree representation. We show that the number of possible O-tree combinations is O(n!2(2n-2)/n(1.5)). This is very concise compared to a sequence pair representation that has O((n!)(2)) combinations. The approximate ratio of sequence pair and O-tree combinations is O(n(2)(n/4e)(n)), The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!2(5n-3)/n(1.5)) combinations, Given an O tree, it takes only linear time to construct the placement and its constraint graph, We have developed a deterministic floorplanning algorithm utilizing the structure of O tree. Empirical results on MCNC (www.mcnc.org) benchmarks show promising performance with average 16% improvement in wire length and 1% less dead space over previous central processing unit (CPU) intensive cluster refinement method.