Benchmarking for large-scale placement and beyond

ABSTRACT

Over the last five years the VLSI Placement community achieved great strides in the understanding of placement problems, developed new high-performance algorithms, and achieved impressive empirical results. These advances have been supported by non-trivial benchmarking infrastructure, and future achievements are set to draw on benchmarking as well. In this paper we review motivations for benchmarking, especially for commercial EDA, analyze available benchmarks, and point out major pitfalls in benchmarking. We outline major outstanding problems and discuss the future of placement benchmarking. Furthermore, we attempt to extrapolate our experience to circuit layout tasks beyond placement.

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: Charles J. Alpert , Gi-Joon Nam , Paul G. Villarrubia, Free space management for cut-based placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.746-751, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774682]
• 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: 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]
• 5: M. R. Beasley, S. Datta, H. Kogelnik, H. Kroemer, and D. Monroe. "Report of the Investigation Committee on the Possibility of Scientific Misconduct in the Work of Hendrik Schon and Coauthors," 2000. http://www.lucent.com/news_events/researchreview.html.
• 6: Andrew E. Caldwell , Andrew B. Kahng , Andrew A. Kennings , Igor L. Markov, Hypergraph partitioning for VLSI CAD: methodology for heuristic development, experimentation and reporting, Proceedings of the 36th ACM/IEEE conference on Design automation, p.349-354, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309955]
• 7: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Improved algorithms for hypergraph bipartitioning, Proceedings of the 2000 conference on Asia South Pacific design automation, p.661-666, January 2000, Yokohama, Japan [doi>10.1145/368434.368864]
• 8: A. E. Caldwell, A. B. Kahng and I. L. Markov, "Hypergraph Partitioning With Fixed Vertices," IEEE Trans. on CAD, vol. 19, no. 2, 2000, pp. 267--272.
• 9: Andrew E. Caldwell , Andrew B. Kahng , Igor L. Markov, Design and implementation of move-based heuristics for VLSI hypergraph partitioning, Journal of Experimental Algorithmics (JEA), 5, p.5-es, 2000 [doi>10.1145/351827.384247]
• 10: 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]
• 11: A. E. Caldwell, A. B. Kahng, I. L. Markov, "Optimal Partitioners and End-case Placers for Standard-cell Layout", IEEE Trans. on CAD, vol. 19, no. 11, 2000, pp. 1304--1314.
• 12: A. E. Caldwell, A. B. Kahng, I. L. Markov, "Hierarchical Whitespace Allocation", to appear in IEEE Trans. on CAD 2003.
• 13: A. E. Caldwell, A. B. Kahng, I. L. Markov, "VLSI CAD Bookshelf" http://vlsicad.eecs.umich.edu/BK
• 14: 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
• 15: Chin-Chih Chang , Jason Cong , Min Xie, Optimality and scalability study of existing placement algorithms, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119914]
• 16: 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]
• 17: Hongyu Chen , Changge Qiao , Feng Zhou , Chung-Kuan Cheng, Refined single trunk tree: a rectilinear steiner tree generator for interconnect prediction, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505366]
• 18: Yih-Chih Chou , Youn-Long Lin, A performance-driven standard-cell placer based on a modified force-directed algorithm, Proceedings of the 2001 international symposium on Physical design, p.24-29, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369722]
• 19: Jason Cong , Michail Romesis , Min Xie, Optimality, scalability and stability study of partitioning and placement algorithms, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640021]
• 20: J. Cong and J. R. Shinnerl, "Multi-level Optimization in VLSI CAD," Kluwer, Boston, 2002.
• 21: Willaim J. Dally , Andrew Chang, The role of custom design in ASIC Chips, Proceedings of the 37th conference on Design automation, p.643-647, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337604]
• 22: K. Doll, F. M. Johannes and K. J. Antreich, "Iterative Placement Improvement By Network Flow Methods". IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol.13, (no.10), Oct. 1994. pp. 1189--1200.
• 23: 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]
• 24: 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]
• 25: C. M. Fiduccia , R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th conference on Design automation, p.175-181, January 1982
• 26: S. Goto, "An Efficient algorithm for the Two-Dimensional Placement Problem in Electrical Circuit Layout," IEEE Trans. on Circuits and Systems, vol. 28 no. 1, 1981, pp. 12--18.
• 27: Lars W. Hagen , Dennis J. H. Huang , Andrew B. Kahng, Quantified suboptimality of VLSI layout heuristics, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.216-221, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217532]
• 28: Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, Timing driven placement using physical net constraints, Proceedings of the 38th conference on Design automation, p.780-783, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379065]
• 29: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 30: Andrew B. Kahng , Stefanus Mantik , Dirk Stroobandt, Requirements for models of achievable routing, Proceedings of the 2000 international symposium on Physical design, p.4-11, May 2000, San Diego, California, United States [doi>10.1145/332357.332364]
• 31: Andrew B. Kahng , Stefanus Mantik , Igor L. Markov, Min-max placement for large-scale timing optimization, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505423]
• 32: 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]
• 33: Parivallal Kannan , Shankar Balachandran , Dinesh Bhatia, On metrics for comparing routability estimation methods for FPGAs, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513937]
• 34: Ryan Kastner , Elaheh Bozorgzadeh , Majid Sarrafzadeh, Predictable routing, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 35: Tim (Tianming) Kong, A novel net weighting algorithm for timing-driven placement, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.172-176, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774597]
• 36: Prabhakar Kudva , Andrew Sullivan , William Dougherty, Metrics for structural logic synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.551-556, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774653]
• 37: E. Lerner, "Fraud Shows Peer-review Flaws," The Industrial Physicist, 8(2), 2002.
• 38: Jinan Lou , Shankar Krishnamoorthy , Henry S. Sheng, Estimating routing congestion using probabilistic analysis, Proceedings of the 2001 international symposium on Physical design, p.112-117, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369749]
• 39: Magma Design Automation Inc., "White Papers," http://www.magma-da.com/whitepapers.html
• 40: P. H. Madden, "Reporting of Standard Cell Placement Results," IEEE Trans. on CAD, 21(2), Feb. 2002, pp. 240--247.
• 41: Fan Mo , Abdallah Tabbara , Robert K. Brayton, A force-directed maze router, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 42: Monterey Design Systems, "Dolphin," http://www.mondes.com/products/dolphin.htm
• 43: Open Access, http://www.si2.org/openaccess/.
• 44: Open Library Architecture (OLA), http://www.si2.org/OLA/.
• 45: Shih-Lian Ou , Massoud Pedram, Timing-driven placement based on partitioning with dynamic cut-net control, Proceedings of the 37th conference on Design automation, p.472-476, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337548]
• 46: Phiroze N. Parakh , Richard B. Brown , Karem A. Sakallah, Congestion driven quadratic placement, Proceedings of the 35th annual conference on Design automation, p.275-278, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277121]
• 47: Ulrich Brenner , André Rohe, An effective congestion driven placement framework, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA [doi>10.1145/505388.505391]
• 48: Lou Scheffer , Eric Nequist, Why interconnect prediction doesn't work, Proceedings of the 2000 international workshop on System-level interconnect prediction, p.139-144, April 08-09, 2000, San Diego, California, United States [doi>10.1145/333032.333044]
• 49: H. Schmit, "Vertical Benchmarks," http://www.ece.cmu.edu/~herman/html/benchmark_slot.html
• 50: Georg Sigl , Konrad Doll , Frank M. Johannes, Analytical placement: A linear or a quadratic objective function?, Proceedings of the 28th conference on ACM/IEEE design automation, p.427-432, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127707]
• 51: The Standard Performance Evaluation Corporation (SPEC), "SPECmark benchmarks," http://www.specbench.org/
• 52: D. Stroobandt, "A Priori Wire Length Estimates for Digital Design," 324 pages, Kluwer, ISBN 0-7923-7360-X, 2001.
• 53: William Swartz , Carl Sechen, Timing driven placement for large standard cell circuits, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.211-215, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217531]
• 54: 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
• 55: 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]
• 56: Xiaojian Yang , Bo-Kyung Choi , Majid Sarrafzadeh, Timing-driven placement using design hierarchy guided constraint generation, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.177-180, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774598]
• 57: X. Yang, B-K. Choi, and M. Sarrafzadeh, "A Standard-Cell Placement Tool for Designs with High Row Utilization," ICCD 2002, p. 45--47.
• 58: 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

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.4 VLSI Systems

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Documentation, Experimentation, Human Factors, Measurement, Performance, Standardization

Keywords:
benchmark, comparison, congestion, evaluation, layout, performance, placement, placer, routing, signal delay, timing, wirelength