MP-trees: A packing-based macro placement algorithm for modern mixed-size designs

作者：Chen Tung Chieh^*; Yuh Ping Hung; Chang Yao Wen; Huang Fwu Juh; Liu Tien Yueh

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(9): 1621-1634.

DOI：10.1109/TCAD.2008.927760

• floorplanning
• layout
• physical design
• placement

In this paper, we present a new multipacking-tree (MP-tree) representation for macro placements to handle modern mixed-size designs with large macros and high chip utilization rates. Based on binary trees, the NIP-tree is very efficient, effective, and flexible for handling macro placements with various constraints. Given a global placement that already considers the areas and the interconnections among standard cells and macros, our MP-tree-based macro placer optimizes macro positions, minimizes the macro displacement from the initial macro positions, and maximizes the area of the chip center for standard-cell placement and routing. Experiments based on the Proceedings of the 2006 International Symposium on Physical Design placement contest benchmarks and Faraday benchmarks show that our macro placer combined with APlace 2.0, Capo 10.2, mPL6, or NTUplace3 for a standard-cell placement outperforms these state-of-the-art academic mixed-size placers alone by large margins in robustness and quality. In addition to wirelength, experiments on four real industrial designs with large macros and high utilization rates show that our method significantly reduces the average lialf-perimeter wirelength by 35%, the average routed wirelength by 55%, and the routing overflows by 13 times compared with Capo 10.2, implying that our macro placer leads to much higher routability.

• 出版日期2008-9
• 单位中国科学院电工研究所