Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step

ABSTRACT

In this paper, we present Forge, an optimal algorithm for gate sizing using the Elmore delay model. The algorithm utilizes Lagrangian relaxation with a fast gradient-based pre-processing step that provides an effective set of initial Lagrange multipliers. Compared to the previous Lagrangian-based approach, Forge is considerably faster and does not have the inefficiencies due to difficult-to-determine initial conditions and constant factors. We compared the two algorithms on 30 benchmark designs, on a Sun UltraSparc-60 workstation. On average Forge is 200 times faster than the previously published algorithm. We then improved Forge by incorporating a slew-rate-based convex delay model, which handles distinct rise and fall gate delays. We show that Forge is 15 times faster, on average, than the AMPS transistor-sizing tool from Synopsys, while achieving the same delay targets and using similar total transistor area.

REFERENCES

• 1: W. C. Elmore, "The transient analysis of damped linear networks with particular regard to wideband amplifiers." Journal of Applied Physics, vol. 19, no. 1, pp. 55--63, 1948.
• 2: J. Rubinstein, P. Penfield, and Mark Horowitz, "Signal delay in RC tree networks," IEEE Trans. on CAD, vol. CAD-2, no. 3, pp. 202--210, July 1983.
• 3: S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang, "An exact solution of the transistor sizing problem for CMOS circuits using convex optimization," IEEE Trans. on CAD of IC's and Systems, vol. CAD-12, pp. 1621--1634, Nov 1993.
• 4: J. P. Fishburn and A. E. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," IEEE Trans on CAD, pp. 326--328, Nov 1985.
• 5: Chung-Ping Chen , Chris C. N. Chu , D. F. Wong, Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.617-624, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289097]
• 6: D. Marple, Transistor size optimization in the tailor layout system, Proceedings of the 26th ACM/IEEE conference on Design automation, p.43-48, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74391]
• 7: Ronald E. Miller, Optimization, John Wiley & Sons, Inc, 2000.
• 8: Iris Hui-Ru Jiang, Yao-Wen Chang, and Jing-Yang Jou, "Crosstalk-Driven Interconnect Optimization by Simultaneous Gate and Wire Sizing," IEEE Trans. on CAD of IC's and Systems, vol. 19, no. 9, pp. 999--1010, September 2000.
• 9: Sachin S. Sapatnekar , Sung-Mo Kang, Design Automation for Timing-Driven Layout Synthesis, Kluwer Academic Publishers, Norwell, MA, 1992
• 10: M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Second Edition, John Wiley and Sons, 1993.
• 11: L. A. N. Lorena, E. L. F. Senne, "Improving traditional subgradient scheme for Lagrangian relaxation: application to location problems," International Journal of Mathematical Algorithms, pp. 133--151, 1, 1999.
• 12: John E. Dennis, Jr. , David M. Gay , Roy E. Walsh, An Adaptive Nonlinear Least-Squares Algorithm, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.348-368, Sept. 1981 [doi>10.1145/355958.355965]
• 13: K. Kasamsetty, M. Ketkar, and S. S. Sapatnekar, "A New Class of Convex Functions for Delay Modeling and their Application to the Transistor Sizing Problem," IEEE Trans. on CAD of Integrated Circuits and Systems, Vol. 19, No. 7, pp. 779--788, July 2000.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Parallel circuits

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.9 Integral Equations
          Subjects: Delay equations

General Terms:
Algorithms, Experimentation, Theory