Efficient and accurate gate sizing with piecewise convex delay models

ABSTRACT

We present an efficient and accurate gate sizing tool that employs a novel piecewise convex delay model, handling both rise and fall delays, for static CMOS gates. The delay model is used in a new version of a gate-sizing tool called Forge, which not only exhibits optimality, but also efficiently produces the area versus delay trade-off curve for a block in one step. Forge includes a realistic delay propagation scheme that combines arrival times and slew-rates. Forge is 6.4X faster than a commercial transistor sizing tool, while achieving better delay targets and uses 28% less transistor area for specific delay targets, on average.

REFERENCES

• 1: M. delM. Hershenson, S.P. Boyd, and T.H. Lee, "Optimal design of a CMOS op-amp via geometric programming," IEEE Trans. on Computer-Aided Design, vol. 20, no 1, pp. 1--21, Jan 2001.
• 2: Miodrag Vujkovic , Carl Sechen, Optimized power-delay curve generation for standard cell ICs, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.387-394, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774630]
• 3: Miodrag Vujkovic , David Wadkins , Bill Swartz , Carl Sechen, Efficient timing closure without timing driven placement and routing, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996646]
• 4: M.R.C.M. Berkelaar, P.H.W. Buurman, and J. A. G. Jess, "Computing the entire active area/power consumption versus delay tradeoff curve for gate sizing with a piecewise linear simulator," IEEE Trans. on Computer-Aided Design, vol. 15, no. 11, pp. 1424--1434, Nov 1996.
• 5: J. P. Fishburn and A. E. Dunlop, "TILOS: A posynomial programming approach to transistor sizing," IEEE Trans. on Computer-Aided Design, pp. 326--328, Nov 1985.
• 6: 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.
• 7: 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 Computer-Aided, vol. 19, no. 7, pp. 779--788, July 2000.
• 8: Jin Fuw Lee , D. L. Ostapko , Jeffery Soreff , C. K. Wong, On the signal bounding problem in timing analysis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 9: 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 Computer-Aided Design, vol. 12, pp. 1621--1634, Nov 1993.
• 10: V. Sundararajan, S. S. Sapatnekar, and K. K. Parhi, "Fast and Exact Transistor Sizing Based on Iterative Relaxation," IEEE Trans. on Computer-Aided Design, vol. 21, no. 5, pp. 568--581, May 2002.
• 11: 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]
• 12: 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]
• 13: A. R. Conn, P. K. Coulman, R. A. Harring, G. L. Morril, C. Visweshwariah, and C. W. Wu, "JiffyTune: Circuit optimization using time-domain sensitivities," IEEE Trans. on Computer-Aided Design, vol. 17, no. 12, pp. 1292--1309, Dec 1998.
• 14: A. R. Conn , I. M. Elfadel , W. W. Molzen, Jr. , P. R. O'Brien , P. N. Strenski , C. Visweswariah , C. B. Whan, Gradient-based optimization of custom circuits using a static-timing formulation, Proceedings of the 36th ACM/IEEE conference on Design automation, p.452-459, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309979]
• 15: Ivan Sutherland , Bob Sproull , David Harris, Logical effort: designing fast CMOS circuits, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 16: 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]
• 17: Jorge Nocedal, and Stephen J. Wright, Numerical Optimization, Springer-Verlag, 1999.
• 18: M. S. Bazaraa, H. D. Sherali, C. M. Shetty, Nonlinear Programming: Theory and Algorithms, Second Edition, John Wiley and Sons, 1993

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids

General Terms:
Algorithms, Design, Performance

Keywords:
Lagrangian relaxation, delay modeling, gate sizing, optimization, piecewise convex