Multi-level placement for large-scale mixed-size IC designs

ABSTRACT

In this paper we study the large-scale mixed-size placement problem where there is a significant size variation between big and small placeable objects (the ratio can be as large as 10,000). We develop a multi-level optimization algorithm, MPGMS, for this problem which can efficiently handle both large-scale designs and large size variations. Compared with the recently published work [1] on large-scale mixed macro and standard cell placement benchmarks for wirelength minimization, our method can achieve 13% wirelength reduction on average with comparable runtime.

REFERENCES

• 1: Saurabh N. Adya , Igor L. Markov, Consistent placement of macro-blocks using floorplanning and standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505392]
• 2: H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 12, pp. 1518--1524, 1996.
• 3: Jai-Ming Lin , Yao-Wen Chang, TCG: a transitive closure graph-based representation for non-slicing floorplans, Proceedings of the 38th conference on Design automation, p.764-769, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379062]
• 4: http://nexus6.cs.ucla.edu/~cheese/ispd98.html.
• 5: Jitendra Apte , Gershon Kedem, Heuristic algorithms for combined standard cell and macro block layouts, Proceedings of the sixth MIT conference on Advanced research in VLSI, p.367-385, March 1990, Boston, Massachusetts, United States
• 6: Michael Upton , Khosrow Samii , Stephen Sugiyama, Integrated placement for mixed macro cell and standard cell designs, Proceedings of the 27th ACM/IEEE conference on Design automation, p.32-35, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123219]
• 7: A. Shanbhag, S. Danda, and N. Sherwani, "Floorplanning for mixed macro block and standard cell designs," in Proc. the forth Great Lakes Symp. on VLSI, pp. 26--29, 1994.
• 8: J. Cong, "An interconnect-centric design flow for nanometer technologies," Proceedings of the IEEE, vol. 89, pp. 505--527, April 2001.
• 9: C. Sechen and A. Sangiovanni-Vincentelli, "The Timberwolf placement and routing package," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 20, no. 2, pp. 510--522, 1985.
• 10: W. J. Sun and C. Sechen, "Efficient and effective placement for very large circuits," in Proc. Int. Conf. on Computer Aided Design, pp. 336--339, 1990.
• 11: Hong Yu , Xianlong Hong , Yici Cai, MMP: a novel placement algorithm for combined macro block and standard cell layout design, Proceedings of the 2000 conference on Asia South Pacific design automation, p.271-276, January 2000, Yokohama, Japan [doi>10.1145/368434.368632]
• 12: Chin-Chih Chang , Jason Cong , Zhigang (David) Pan, Physical hierarchy generation with routing congestion control, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505399]
• 13: George Karypis , Vipin Kumar, Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM/IEEE conference on Design automation, p.343-348, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309954]
• 14: B. S. Baker, E. G. Coffman, and R. L. Rivest, "Orthogonal packings in two dimensions," SIAM J. Compute., vol. 9, no. 4, pp. 846--855, 1980.
• 15: Sudip Nag , Kamal Chaudhary, Post-placement residual-overlap removal with minimal movement, Proceedings of the conference on Design, automation and test in Europe, p.116-es, January 1999, Munich, Germany [doi>10.1145/307418.307568]
• 16: http://vlsicad.eecs.umich.edu/BK/ISPD02bench.