A sequential quadratic programming approach to concurrent gate and wire sizing

ABSTRACT

With an ever-increasing portion of the delay in high- speed CMOS chips attributable to the interconnect, interconnect-circuit design automation continues to grow in importance. By transforming the gate and multilayer wire sizing problem into a convex programming problem for the Elmore delay approximation, we demonstrate the efficacy of a sequential quadratic programming (SQP) solution method. For cases where accuracy greater than that provided by the Elmore delay approximation is required, we apply SQP to the gate and wire sizing problem with more accurate delay models. Since efficient calculation of sensitivities is of paramount importance during SQP, we describe an approach for efficient computation of the accurate delay sensitivities.

REFERENCES

• 1: Jason Cong , Kwok-Shing Leung, Optimal wiresizing under the distributed Elmore delay model, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.634-639, November 07-11, 1993, Santa Clara, California, United States
• 2: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.206-212, November 06-10, 1994, San Jose, California, United States
• 3: Sachin S. Sapatnekar, RC interconnect optimization under the Elmore delay model, Proceedings of the 31st annual conference on Design automation, p.387-391, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196430]
• 4: Noel Menezes , Satyamurthy Pullela , Lawrence T. Pileggi, Simultaneous gate and interconnect sizing for circuit-level delay optimization, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.690-695, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217612]
• 5: J. Rubinstein, E Penfield, Jr., and M. A. Horowitz, "Signal delay in RC tree networks," IEEE Trans. Computer-Aided Design, vol. CAD-2, pp. 202-211, July 1983.
• 6: W.C. Elmore, "The transient response of damped linear networks with particular regard to wide-band amplifiers," J. Applied Physics, vol. 19, no. 1, pp. 55-63, Jan. 1948.
• 7: Curtis L. Ratzlaff , Nanda Gopal , Lawrence T. Pillage, RICE: Rapid interconnect circuit evaluator, Proceedings of the 28th conference on ACM/IEEE design automation, p.555-560, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127732]
• 8: Florentin Dartu , Noel Menezes , Jessica Qian , Lawrence T. Pillage, A gate-delay model for high-speed CMOS circuits, Proceedings of the 31st annual conference on Design automation, p.576-580, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196562]
• 9: J. E Fishburn and A. E. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," Proc. of the Intl. Conf. on Computer-Aided Design, November 1985.
• 10: M. J. D. Powell, "A fast algorithm for nonlinearly constrained optimization calculations," Lecture Notes in Mathematics, No. 630, ed. G. A. Watson, pp. 144-157, Springer Verlag.
• 11: J. K. Ousterhout, "A switch-level timing verifier for digital MOS VLSI," IEEE Trans. Computer-Aided Design, vol. CAD-4, no. 3, pp. 336-349, July 1985.
• 12: J. Qian, S. Pullela, and L. T. Pillage, "Modeling the effective capacitance for the RC interconnect of CMOS gate," IEEE Trans. Computer-AidedDesign, vol. 12, no. 12, pp. 1526-1535, Dec. 1994.
• 13: N. Gopal, "Fast evaluation of VLSI interconnect structures using moment-matching methods," Ph.D. dissertation, The University of Texas at Austin, December 1992.
• 14: Rohini Gupta , Byron Krauter , Bogdan Tutuianu , John Willis , Lawrence T. Pileggi, The Elmore delay as bound for RC trees with generalized input signals, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.364-369, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217556]
• 15: J. G. Ecker, "Geometric programming: methods, computations and applications" SlAM Review, vol. 22, no. 3, pp. 338-362, July 1980.
• 16: S. S. Sapatnekar, et al., "An exact solution to the transistor sizing problem for CMOS circuits using convex optimization," IEEE Trans. Computer-Aided Design, vol. 12, no. 11, pp. 1621- 1634, May 1992.
• 17: J. Stoer, "Principles of sequential quadratic programming methods for solving nonlinear programs," Computational Mathematical Programming (ed. K. Schittkowski), NATO ASI Series, vol. 15, Springer Verlag, Berlin.
• 18: K. Schittkowski, "NLPQL: A FORTRAN subroutine solving constrained nonlinear programming problems," Annals of Operations Research, vol. 5, pp 485-500, 1985/86.
• 19: Noel Menezes , Satyamurthy Pullela , Florentin Dartu , Lawrence T. Pillage, RC interconnect synthesis—a moment fitting approach, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.418-425, November 06-10, 1994, San Jose, California, United States
• 20: Noel Anthony Francis Menezes , Lawrence T. Pileggi, Algorithms for rc interconnect synthesis, 1995
• 21: NAG C library manual- Mark 3, vol. 2, The Numerical Algorithms Group Ltd., Downers Grove, Illinois.
• 22: L.T. Pillage and R.A. Rohrer, "Asymptotic waveform evaluation for timing analysis," IEEE Trans. Computer-Aided Design, vol. 9, no. 4, pp. 352-366, April 1990.
• 23: J. Y. Lee, X. Huang, and R. Rohrer, "Pole and zero sensitivity calculation in asymptotic waveform evaluation," IEEE Trans. Computer-AidedDesign, vol. 11, no. 5, pp. 586 - 597, May 1992.
• 24: K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins, "Fidelity and near-optimality of Elmore-based routing constructions," Proc. of the Intl. Conf. Computer Design, October 1993.
• 25: S. Pullela, "Reliable interconnect design for on-chip clock distribution," Ph.D. dissertation, The University of Texas at Austin, May 1995.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

General Terms:
Theory

Keywords:
RC interconnect, optimization, sequential quadratic programming