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

ABSTRACT

In this paper, we present a new multi-packing tree (MP-tree) representation for macro placement to handle mixed-size designs. Based on binary trees, the MP-tree is very efficient, effective, and flexible for handling macro placement with various constraints. Given a global placement, 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 eight ISPD'06 placement contest benchmarks show that our macro placer combined with Capo 10.2, NTUplace3, or mPL6 for standard-cell placement outperforms these state-of-the-art academic mixed-size placers alone by large margins in both robustness and quality. In addition to wirelength, experimented on five real industrial designs show that our method significantly reduce the average HPWL by 35%, the average routed wirelength by 55%, and the routing overflows than the counterpart with Capo 10.2, implying that our macro placer leads to much higher routability.

REFERENCES

• 1: ISPD 2006 Placement Contest, http://www.sigda.org/ispd2006/contest.html.
• 2: S. N. Adya , I. L. Markov, Combinatorial techniques for mixed-size placement, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.10 n.1, p.58-90, January 2005 [doi>10.1145/1044111.1044116]
• 3: A. R. Agnihotri, S. Ono, C. Li, M. C. Yildiz, A. Khatkhate, C.-K. Koh, and P. H. Madden. Mixed block placement via fractional cut recursive bisection. IEEE Trans. Computer-Aided Design, 24(5):748--761, May 2005.
• 4: Tony F. Chan , Jason Cong , Joseph R Shinnerl , Kenton Sze , Min Xie, mPL6: enhanced multilevel mixed-size placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123055]
• 5: Chin-Chih Chang , Jason Cong , Xin Yuan, Multi-level placement for large-scale mixed-size IC designs, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119835]
• 6: Yun-Chih Chang , Yao-Wen Chang , Guang-Ming Wu , Shu-Wei Wu, B*-Trees: a new representation for non-slicing floorplans, Proceedings of the 37th conference on Design automation, p.458-463, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337541]
• 7: Tung-Chieh Chen , Tien-Chang Hsu , Zhe-Wei Jiang , Yao-Wen Chang, NTUplace: a ratio partitioning based placement algorithm for large-scale mixed-size designs, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055188]
• 8: Tung-Chieh Chen , Zhe-Wei Jiang , Tien-Chang Hsu , Hsin-Chen Chen , Yao-Wen Chang, A high-quality mixed-size analytical placer considering preplaced blocks and density constraints, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233538]
• 9: Andrew B. Kahng , Qinke Wang, A faster implementation of APlace, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123057]
• 10: Jarrod A. Roy , David A. Papa , Aaron N. Ng , Igor L. Markov, Satisfying whitespace requirements in top-down placement, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123053]
• 11: Peter Spindler , Frank M. Johannes, Fast and robust quadratic placement combined with an exact linear net model, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California [doi>10.1145/1233501.1233537]
• 12: Taraneh Taghavi , Xiaojian Yang , Bo-Kyung choi , Maogang Wang , Majid Sarrafzadeh, Dragon2006: blockage-aware congestion-controlling mixed-size placer, Proceedings of the 2006 international symposium on Physical design, April 09-12, 2006, San Jose, California, USA [doi>10.1145/1123008.1123054]
• 13: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]
• 14: E. Wein and J. Benkoski. Hard macros will revolutionize SoC design. EETimes Online, Aug. 2004. http://www.eetimes.com/showArticle.jhtml?articleID=26807055.
• 15: Guang-Ming Wu , Yun-Chih Chang , Yao-Wen Chang, Rectilinear block placement using B*-trees, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.8 n.2, p.188-202, April 2003 [doi>10.1145/762488.762490]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design

Keywords:
macro placement, multi-packing tree