Fast Module Packing Algorithm Using Corner Contour Based on O-Tree Representation

In VLSI physical design,O-Tree is regarded as one of the most effective and efficient placement floorplan representations.However,its induced packing algorithms are complicated and time-consuming,because of their horizontal and vertical constraint graphs and involved operations.Based on stairway up-down characteristic of corner-contour,the proposed algorithm in this paper utilizes parent-son relationship embodied in a given O-Tree code to facilitate module placement.There is only one corner-contour being kept during packing,no constraint graphs and related operations are required.The time complexity of the proposed algorithm can be reduced to O(nlogn).Experimental results on MCNC Benchmarks verified the effectiveness of the our algorithm.