2024-03-28T15:10:24Z
https://niigata-u.repo.nii.ac.jp/oai
oai:niigata-u.repo.nii.ac.jp:00001713
2022-12-15T03:34:27Z
453:454
468:469:470
Floorplanning using a tree representation
Floorplanning using a tree representation
Guo, P. N.
5162
Takahashi, T.
5163
Cheng, C. K.
5164
Yoshimura, T.
5165
Building block placement
floorplan
rooted ordered tree
We present an ordered tree (O tree) structure to represent nonslicing floorplans. The O tree uses only n(2+[lg n]) bits for a floorplan of n rectangular blocks. We define an admissible placement as a compacted placement in both x 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!22n-2/nl.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(n2(n/4e)n). The complexity of O tree is even smaller than a binary tree structure for slicing floorplan that has O(n!25n-3/n1.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
journal article
IEEE
2001-02
application/pdf
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
2
20
281
289
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
AA10629136
02780070
https://niigata-u.repo.nii.ac.jp/record/1713/files/TCAD_20.pdf
eng
info:doi/10.1109/43.908471
©(2001) IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained the IEEE.