An analytic placer for mixed-size placement and timing-driven placement

ABSTRACT

We extend the APlace wirelength-driven standard-cell analytic placement framework of A.A. Kennings and I.L. Markov (2002) to address timing-driven and mixed-size ("boulders and dust") placement. Compared with timing-driven industry tools, evaluated by commercial detailed routing and STA, we achieve an average of 8.4% reduction in cycle time and 7.5% reduction in wirelength for a set of six industry testcases. For mixed-size placement, we achieve an average of 4% wirelength reduction on ISPD02 mixed-size placement benchmarks compared to results of the leading-edge solver, Feng Shui (v2.4) (Khatkhate et al., 2004). We are currently evaluating our placer on industry testcases that combine the challenges of timing constraints, large instance sizes, and embedded blocks (both fixed and unfixed).

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: Saurabh N. Adya , Igor L. Markov , Paul G. Villarrubia, On Whitespace and Stability in Mixed-Size Placement and Physical Synthesis, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.311, November 09-13, 2003 [doi>10.1109/ICCAD.2003.107]
• 3: [3] C. J. Alpert, T. Chan, A. B. Kahng, I. Markov and P. Mulet, "Faster Minimization of Linear Wirelength for Global Placement", IEEE Trans. Computer Aided Design 17(1) (1998), pp. 3-13.
• 4: 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]
• 5: [5] R. Baldick, A. B. Kahng, A. Kennings and I. L. Markov, "Function Smoothing with Applications to VLSI Layout", Proc. Asia and South Pacific Design Automation Conf., Jan. 1999, pp. 225-228.
• 6: [6] Web site of VLSI CAD Bookshelf. http://www.gigascale.org/bookshelf/.
• 7: 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]
• 8: 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]
• 9: [9] Web site of UCLA/UMICH Physical Design Tools. http://vlsicad.eecs.umich.edu/BK/PDtools/.
• 10: 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]
• 11: Chunhong Chen , Xiaojian Yang , Majid Sarrafzadeh, Potential slack: an effective metric of combinational circuit performance, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 12: 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]
• 13: [13] Web site of Dragon. http://er.cs.ucla.edu/Dragon/.
• 14: 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]
• 15: 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]
• 16: Takeo Hamada , Chung-Kuan Cheng , Paul M. Chau, Prime: a timing-driven placement tool using a piecewise linear resistive network approach, Proceedings of the 30th international conference on Design automation, p.531-536, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.165015]
• 17: [17] D. Hill, "Method and System for High Speed Detailed Placement of Cells within an Integrated Circuit Design", US Patent 6370673, April 2002.
• 18: [18] Web site of ISPD02 Mixed-Size Placement Benchmarks. http://vlsicad.eecs.umich.edu/BK/ ISPD02bench/.
• 19: [19] Web site of ISPD 2001 Circuit Benchmarks. http://nthucad.cs.nthu.edu.tw/~ycchou/ benchmark/placement.htm.
• 20: M. A. B. Jackson , E. S. Kuh, Performance-driven placement of cell based IC's, Proceedings of the 26th ACM/IEEE conference on Design automation, p.370-375, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74444]
• 21: Andrew B. Kahng , Qinke Wang, Implementation and extensibility of an analytic placer, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981071]
• 22: Andrew B. Kahng , Xu Xu, Accurate pseudo-constructive wirelength and congestion estimation, Proceedings of the 2003 international workshop on System-level interconnect prediction, April 05-06, 2003, Monterey, CA, USA [doi>10.1145/639929.639942]
• 23: [23] A. A. Kennings and I. L. Markov, "Smoothening Max-terms and Analytical Minimization of Half-Perimeter Wirelength", VLSI Design 14(3) (2002), pp. 229-237.
• 24: Andrew A. Kennings , Igor L. Markov, Analytical minimization of half-perimeter wirelength, Proceedings of the 2000 conference on Asia South Pacific design automation, p.179-184, January 2000, Yokohama, Japan [doi>10.1145/368434.368600]
• 25: Ateen Khatkhate , Chen Li , Ameya R. Agnihotri , Mehmet C. Yildiz , Satoshi Ono , Cheng-Kok Koh , Patrick H. Madden, Recursive bisection based mixed block placement, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981084]
• 26: 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]
• 27: [27] C. Li and C.-K. Koh, "On Improving Recursive Bipartitioning-Based Placement", Technical Report TRECE-03-14, Purdue Univ., 2003.
• 28: Alexander Marquardt , Vaughn Betz , Jonathan Rose, Timing-driven placement for FPGAs, Proceedings of the 2000 ACM/SIGDA eighth international symposium on Field programmable gate arrays, p.203-213, February 10-11, 2000, Monterey, California, United States [doi>10.1145/329166.329208]
• 29: [29] K. G. Murty, Linear Complementarity, Linear and Nonlinear Programming, Internet Edition, Chapter 10, pp. 389-460. http://ioe.engin.umich.edu/books/murty/ linear_complementarity_webbook/.
• 30: [30] R. Nair, C. L. Berman, P. Hauge and E. J. Yoffa, "Generation of Performance Constraints for Layout", IEEE Trans. Computer Aided Design of Integrated Circuits and Systems 8(8) (1989), pp. 860-874.
• 31: [31] W. Naylor et al., "Non-Linear Optimization System and Method for Wire Length and Delay Optimization for an Automatic Electric Circuit Placer", US Patent 6301693, Oct. 2001.
• 32: 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]
• 33: Karthik Rajagopal , Tal Shaked , Yegna Parasuram , Tung Cao , Amit Chowdhary , Bill Halpin, Timing driven force directed placement with physical net constraints, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640016]
• 34: Arvind Srinivasan, An algorithm for performance-driven initial placement of small-cell ICs, Proceedings of the 28th conference on ACM/IEEE design automation, p.636-639, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127743]
• 35: 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]
• 36: Ren-Song Tsay , Juergen Koehl, An analytic net weighting approach for performance optimization in circuit placement, Proceedings of the 28th conference on ACM/IEEE design automation, p.620-625, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.122882]
• 37: 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]