Sensitivity guided net weighting for placement driven synthesis

ABSTRACT

Net weighting is a key technique in large scale timing driven placement, which plays a crucial role for deep submicron physical synthesis and timing closure. A popular way to assign net weight is based on the slack of the nets, trying to minimize the worst negative slack (WNS) for the entire circuit. While WNS is an important optimization metric, another figure of merit (FOM), defined as the total slack difference compared to a certain slack threshold for all timing end points, is of equivalent importance to measure the overall timing closure result for highly complex modern ASIC and microprocessor designs. In this paper, we perform a comprehensive analysis of the slack and FOM sensitivities to the net weight, and propose a new net weighting scheme based on the slack and FOM sensitivities. Such sensitivity analysis implicitly takes potential physical synthesis effect into consideration. Experiment results on a set of industrial circuits are promising for both stand-alone timing driven placement and physical synthesis afterwards.

REFERENCES

• 1: Semiconductor Industry Association, International Technology Roadmap for Semiconductors, 2003, http://public.itrs.net/.
• 2: 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]
• 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: T. Gao , P. M. Vaidya , C. L. Liu, A performance driven macro-cell placement algorithm, Proceedings of the 29th ACM/IEEE conference on Design automation, p.147-152, June 08-12, 1992, Anaheim, California, United States
• 6: 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]
• 7: B. M. Riess and G. G. Ettelt, "SPEED: fast and efficient timing driven placement," in Proc. IEEE Int. Symp. on Circuits and Systems, pp. 377--380, 1995.
• 8: M. Marek-Sadowska and S. P. Lin, "Timing driven placement," in Proc. Int. Conf. on Computer Aided Design, pp. 94--97, 1989.
• 9: 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]
• 10: 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]
• 11: 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]
• 12: 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]
• 13: J. Kleinhans, G. Sigl, F. M. Johannes, and K. Antreich, "GORDIAN: VLSI placement by quadratic programming and slicing optimization," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. CAD-10, pp. 356--365, Mar. 1991.
• 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: 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]
• 16: David S. Kung, A fast fanout optimization algorithm for near-continuous buffer libraries, Proceedings of the 35th annual conference on Design automation, p.352-355, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277143]
• 17: Charles J. Alpert , Anirudh Devgan , Stephen T. Quay, Buffer insertion for noise and delay optimization, Proceedings of the 35th annual conference on Design automation, p.362-367, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277145]
• 18: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide-band amplifiers," Journal of Applied Physics, vol. 19, pp. 55--63, Jan. 1948.
• 19: Jason Cong , Lei He , Cheng-Kok Koh , Patrick H. Madden, Performance optimization of VLSI interconnect layout, Integration, the VLSI Journal, v.21 n.1-2, p.1-94, Nov. 1996 [doi>10.1016/S0167-9260(96)00008-9]
• 20: P. Villarrubia, G. Nusbaum, R. Masleid, and P. T. Patel, "IBM RISC chip design methodology," in Proc. IEEE Int. Conf. on Computer Design, pp. 143--147, 1989.
• 21: http://www-306.ibm.com/chips/services/foundry/technologies/cmos.html.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
interconnect, net weight, physical synthesis, sensitivity analysis, timing driven placement