Gate sizing by Lagrangian relaxation revisited

ABSTRACT

In this paper, we formulate the Generalized Convex Sizing (GCS) problem that unifies and generalizes the sizing problems. We revisit the approach to solve the sizing problem by Lagrangian relaxation, point out several misunderstandings in the previous works, and extend the approach to handle general convex delay functions in the GCS problems. We identify a class of proper GCS problems whose objective functions in the simplified dual problem are differentiable and show many practical sizing problems, including the simultaneous sizing and clock skew optimization problem, are proper. We design an algorithm based on the method of feasible directions to solve proper GCS problems. The algorithm will provide evidences for infeasible GCS problems according to a condition derived by us. Experimental results confirm the efficiency and the effectiveness of our algorithm when the Elmore delay model is used.

REFERENCES

• 1: J. Fishburn and A. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," in ICCAD, 1985, pp. 326--328.
• 2: S. S. Sapatnekar, V. B. Rao, P. M. Vaidya, and S. M. Kang, "An exact solution to the transistor sizing problem for CMOS circuits using convex optimization," IEEE TCAD, vol. 12, pp. 1621--1634, Nov. 1993.
• 3: W. Chuang, S. S. Sapatnekar, and I. N. Hajj, "Timing and area optimization for standard-cell VLSI circuit design," IEEE TCAD, vol. 14, no. 3, pp. 308--320, Mar. 1995.
• 4: C.-P. Chen, C. C. N. Chu, and D. F. Wong, "Fast and exact simultaneous gate and wire sizing by Lagrangian relaxation," IEEE TCAD, vol. 18, no. 7, pp. 1014--1025, July 1999.
• 5: V. Sundararajan, S. S. Sapatnekar, and K. K. Parhi, "Fast and exact transistor sizing based on iterative relaxation," IEEE TCAD, vol. 21, no. 5, pp. 568--581, May 2002.
• 6: Hiran Tennakoon , Carl Sechen, Gate sizing using Lagrangian relaxation combined with a fast gradient-based pre-processing step, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.395-402, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774631]
• 7: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 8: M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming, 3rd ed. Wiley-Interscience, 2006.
• 9: W. C. Elmore, "The transient response of damped linear networks with particular regard to wide-band amplifiers," Journal of Applied Physics, vol. 19, no. 1, pp. 55--63, Jan. 1948.
• 10: 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 TCAD, vol. 19, no. 7, pp. 779--788, July 2000.
• 11: Faraday Technology Corporation, "UMC 90-nano Libraries," http://freelibrary.faraday-tech.com/, Nov. 2005.
• 12: Hiran Tennakoon , Carl Sechen, Efficient and accurate gate sizing with piecewise convex delay models, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065793]
• 13: Chuan Lin , Hai Zhou, Clock Skew Scheduling with Delay Padding for Prescribed Skew Domains, Proceedings of the 2007 conference on Asia South Pacific design automation, p.541-546, January 23-26, 2007 [doi>10.1109/ASPDAC.2007.358042]
• 14: R. T. Rockafellar, "Ordinary convex programs without a duality gap," Journal of Optimization Theory and Applications, vol. 7, no. 3, pp. 143--148, Mar. 1971.
• 15: Andrew Goldberg's network optimization library, http://www.avglab.com/andrew/soft.html.