Optimality and scalability study of existing placement algorithms

ABSTRACT

Placement is an important step in the overall IC design process in DSM technologies, as it defines the on-chip interconnects, which have become the bottleneck in determining circuit performance. The rapidly increasing design complexity, combined with the demand for the capability of handling nearly flattened designs for physical hierarchy generation, poses significant challenges to existing placement algorithms. There are very few studies on understanding the optimality and scalability of placement algorithms, due to the limited sizes of existing benchmarks and limited knowledge of optimal solutions. The contribution of this paper includes two parts: 1) We implemented an algorithm for generating synthetic benchmarks that have known optimal wirelengths and can match any given net distribution vector. 2) Using benchmarks of 10K to 2M placeable modules with known optimal solutions, we studied the optimality and scalability of three state-of-the-art placers, Dragon [4], Capo [1], mPL [24] from academia, and one leading edge industrial placer, QPlace [5] from Cadence. For the first time our study reveals the gap between the results produced by these tools versus true optimal solutions. The wirelengths produced by these tools are 1.66 to 2.53 times the optimal in the worst cases, and are 1.46 to 2.38 times the optimal on the average. As for scalability, the average solution quality of each tool deteriorates by an additional 4% to 25% when the problem size increases by a factor of 10. These results indicate significant room for improvement in existing placement algorithms.

REFERENCES

• 1: 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]
• 2: 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]
• 3: C. Sechen and A. Sangiovanni-Vincentelli, "The TimberWolf Placement and Routing Package," IEEE J of Solid-State Circuits Vol. 20 No. 2, pp. 432--439, 1985.
• 4: 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
• 5: Cadence Design Systems Inc, "Envisia Ultra Placer Reference," QPlace version 5.1.55, compiled on 10/25/1999.
• 6: International Technology Roadmap for Semiconductors 2001 Edition.
• 7: J. Cong, "An Interconnect-Centric Design Flow for Nanometer Technologies," Proceedings of the IEEE, Vol. 89, No. 4, pp 505--528, 2001.
• 8: 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]
• 9: 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]
• 10: Nevin Kapur , Debabrata Ghosh , Franc Brglez, Towards a new benchmarking paradigm in EDA: analysis of equivalence class mutant circuit distributions, Proceedings of the 1997 international symposium on Physical design, p.136-143, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267704]
• 11: Kazuo Iwama , Kensuke Hino, Random generation of test instances for logic optimizers, Proceedings of the 31st annual conference on Design automation, p.430-434, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196452]
• 12: B. S. Landman and R. L. Russo. "On a pin versus block relationship for partitions of logic graphs," IEEE Trans. on Computers, C20, pp. 1469--1479, 1971.
• 13: Joel Darnauer , Wayne Wei-Ming Dai, A method for generating random circuits and its application to routability measurement, Proceedings of the 1996 ACM fourth international symposium on Field-programmable gate arrays, p.66-72, February 11-13, 1996, Monterey, California, United States [doi>10.1145/228370.228380]
• 14: P. Verplaetse, J. Van Campenhout, and D. Stroobandt, "On synthetic benchmark generation methods," Proc International Symposium on Circuits and Systems, pp. 213--216, 2000.
• 15: D. Stroobandt, P. Verplaetse, and J. Van Campenhout. "Generating synthetic benchmark circuits for evaluating CAD tools," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol 19 No 9, pp. 1011--1022, 2000.
• 16: Dirk Stroobandt , Peter Verplaetse , Jan van Campenhout, Towards synthetic benchmark circuits for evaluating timing-driven CAD tools, Proceedings of the 1999 international symposium on Physical design, p.60-66, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300023]
• 17: M. D. Hutton, J. Rose, J. P. Grossman, and D. Corneil, "Characterization and parameterized generation of synthetic combinatinational circuits," IEEE Trans. on Computer-Aided Design, pp. 985--996, 1998.
• 18: G. Parthasarathy , M. Marek-Sadowska , Arindam Mukherjee , Amit Singh, Interconnect complexity-aware FPGA placement using Rent's rule, Proceedings of the 2001 international workshop on System-level interconnect prediction, p.115-121, March 31-April 01, 2001, Sonoma, California, United States [doi>10.1145/368640.368806]
• 19: 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]
• 20: 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
• 21: George Karypis , Rajat Aggarwal , Vipin Kumar , Shashi Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.69-79, March 1999 [doi>10.1109/92.748202]
• 22: K. Boese, personal communication, 2002.
• 23: S. Goto, "An efficient algorithm for the two dimensional placement problem in electrical circuit layout," IEEE Trans. on Circuit and Systems, vol 28, pp. 12--18, 1981.
• 24: K. Sze, personal communication, 2002.
• 25: http://er.cs.ucla.edu/Dragon/download.html.
• 26: http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/Placement/bin/