A new LP based incremental timing driven placement for high performance designs

ABSTRACT

In this paper, we propose a new linear programming based timing driven placement framework for high performance designs. Our LP framework is mainly net-based, but it takes advantage of the path-based delay sensitivity with limited-stage slew propagation, thus it enjoys certain hybrid feature of net and path-based timing driven placement. Our LP formulation considers not only cells on the critical paths, but also cells that are logically adjacent to the critical paths (i.e., the criticality ad jacency network) in a unified manner. We further present a timing aware spreading method to preserve timing in legalization for high performance designs. Our algorithm has been tested on a set of 65nm industry circuits from a multi-GHz microprocessor, and shown to achieve much improved timing on hand-tuned circuits.

REFERENCES

• 1: D. G. Chinnery , K. Keutzer, Closing the gap between ASIC and custom: an ASIC perspective, Proceedings of the 37th conference on Design automation, p.637-642, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337602]
• 2: Michael Burstein , Mary N. Youssef, Timing influenced layout design, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.124-130, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317845]
• 3: Wilm E. Donath , Reini J. Norman , Bhuwan K. Agrawal , Stephen E. Bello , Sang Yong Han , Jerome M. Kurtzberg , Paul Lowy , Roger I. McMillan, Timing driven placement using complete path delays, Proceedings of the 27th ACM/IEEE conference on Design automation, p.84-89, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123232]
• 4: A. Srinivasan, K. Chaudhary, and E. S. Kuh, "Ritual: A performance driven placement algorithm for small cell ICs," in Proc. Int. Conf. on Computer Aided Design, pp. 48--51, 1991.
• 5: Yun-Cheng Ju , Resve A. Saleh, Incremental techniques for the identification of statically sensitizable critical paths, Proceedings of the 28th conference on ACM/IEEE design automation, p.541-546, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127729]
• 6: 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]
• 7: 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]
• 8: Amit Chowdhary , Karthik Rajagopal , Satish Venkatesan , Tung Cao , Vladimir Tiourin , Yegna Parasuram , Bill Halpin, How accurately can we model timing in a placement engine?, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065792]
• 9: M. Marek-Sadowska and S. Lin, "Timing driven placement.," pp. 94--97, 1989.
• 10: 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]
• 11: Bill Halpin , C. Y. Roger Chen , Naresh Sehgal, A sensitivity based placer for standard cells, Proceedings of the 10th Great Lakes symposium on VLSI, p.193-196, March 02-04, 2000, Chicago, Illinois, United States [doi>10.1145/330855.331040]
• 12: 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
• 13: 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]
• 14: 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]
• 15: Wonjoon Choi , Kia Bazargan, Incremental Placement for Timing Optimization, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.463, November 09-13, 2003 [doi>10.1109/ICCAD.2003.84]
• 16: Haoxing Ren , David Z. Pan , David S. Kung, Sensitivity guided net weighting for placement driven synthesis, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981070]
• 17: Majid Sarrafzadeh , David Knol , Gustavo Tellez, Unification of budgeting and placement, Proceedings of the 34th annual conference on Design automation, p.758-761, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266364]
• 18: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide-band amplifliers," Journal of Applied Physics, vol. 19, pp. 55--63, Jan. 1948.
• 19: Padmini Gopalakrishnan , Altan Odabasioglu , Lawrence Pileggi , Salil Raje, Overcoming wireload model uncertainty during physical design, Proceedings of the 2001 international symposium on Physical design, p.182-189, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369769]
• 20: Haoxing Ren , David Z. Pan , Charles J. Alpert , Paul Villarrubia, Diffusion-based placement migration, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065712]
• 21: T. Luo , H. Ren , C. J. Alpert , D. Z. Pan, Computational geometry based placement migration, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.41-47, November 06-10, 2005, San Jose, CA
• 22: 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]
• 23: MOSEK, "http://www.mosek.com," 2005.

INDEX TERMS

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

General Terms:
Algorithms, Design