Free space management for cut-based placement

ABSTRACT

IP blocks and large macro cells are increasingly prevalent in physical design, actually causing an increase in the available free space for the dust logic. We observe that top-down placement based on recursive bisection with multilevel partitioning performs poorly on these porous designs. However, analytic solvers have the ability to find the natural distribution of cells in the layout. Consequently, we propose an enhancement to cut-based placement called Analytic Constraint Generation (ACG). ACG utilizes an analytic engine to set constraints for the multi-level partitioner. We show that for real industry designs, ACG significantly improves the performance of cut-based placement, as implemented within a state-of-the-art industrial placer.

REFERENCES

• 1: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 2: C. J. Alpert , T. Chan , D. J.-H. Huang , I. Markov , K. Yan, Quadratic placement revisited, Proceedings of the 34th annual conference on Design automation, p.752-757, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266362]
• 3: Charles J. Alpert , Jen-Hsin Huang , Andrew B. Kahng, Multilevel circuit partitioning, Proceedings of the 34th annual conference on Design automation, p.530-533, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266275]
• 4: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Can recursive bisection alone produce routable placements?, Proceedings of the 37th conference on Design automation, p.477-482, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337549]
• 5: Tony F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: Wilm Donath , Prabhakar Kudva , Leon Stok , Lakshmi Reddy , Andrew Sullivan , Kanad Chakraborty , Paul Villarrubia, Transformational placement and synthesis, Proceedings of the conference on Design, automation and test in Europe, p.194-201, March 27-30, 2000, Paris, France [doi>10.1145/343647.343732]
• 7: Shantanu Dutt , Wenyong Deng, VLSI circuit partitioning by cluster-removal using iterative improvement techniques, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.194-200, November 10-14, 1996, San Jose, California, United States
• 8: Hans Eisenmann , Frank M. Johannes, Generic global placement and floorplanning, Proceedings of the 35th annual conference on Design automation, p.269-274, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277119]
• 9: Sung Woo Hur , John Lillis, Mongrel: hybrid techniques for standard cell placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: application in VLSI domain, Proceedings of the 34th annual conference on Design automation, p.526-529, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266273]
• 11: J. Kleinhaus, G. Sigl, F. Johannes and K. Antreich, "GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization", IEEE Trans. on CAD, 10(3), 1991, pp. 356--365.
• 12: Ren-Song Tsay , Ernest S. Kuh , Chi-Ping Hsu, Proud: a fast sea-of-gates placement algorithm, Proceedings of the 25th ACM/IEEE conference on Design automation, p.318-323, June 12-15, 1988, Atlantic City, New Jersey, United States
• 13: P. Villarrubia, G. Nusbaum, R. Masleid, and P. T. Patel, "IBM RISC Chip Design Methodology", ICCD, 1989, pp. 143--147.
• 14: Jens Vygen, Algorithms for large-scale flat placement, Proceedings of the 34th annual conference on Design automation, p.746-751, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266360]
• 15: Maogang Wang , Xiaojian Yang , Majid Sarrafzadeh, Dragon2000: standard-cell placement tool for large industry circuits, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 16: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Routability driven white space allocation for fixed-die standard-cell placement, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505400]
• 17: Mehmet Can Yildiz , Patrick H. Madden, Improved cut sequences for partitioning based placement, Proceedings of the 38th conference on Design automation, p.776-779, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379064]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Standards

General Terms:
Algorithms, Design, Standardization, Theory