Geometric programming for circuit optimization

ABSTRACT

This tutorial concerns a method for solving a variety of circuit sizing and optimization problems, which is based on formulating the problem as a geometric program (GP), or a generalized geometric program (GGP). These nonlinear, constrained optimization problems can be transformed to convex optimization problems, and then solved (globally) very efficiently.

REFERENCES

• 1: Arif Ishaq Abou-Seido , Brian Nowak , Chris Chu, Fitted Elmore delay: a simple and accurate interconnect delay model, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.691-696, July 2004 [doi>10.1109/TVLSI.2004.830932]
• 2: M. Borah, R. Owens, and M. Irwin. A fast algorithm for minimizing the Elmore delay to identified critical sinks. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 16(7):753--759, 1997.
• 3: S. Boyd, S.-J. Kim, and S. Mohan. Geometric programming and its applications to EDA problems. Design and Test in Europe (DATE) 2005 tutorial. Available from www.stanford.edu/~boyd/date05.html.
• 4: S. Boyd, S.-J. Kim, D. Patil, and M. Horowitz. Digital circuit optimization via geometric programming. Available from www.stanford.edu/~boyd/~gp_digital_ckt.html, Jan. 2005. Technical Report, Stanford University.
• 5: S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi. A tutorial on geometric programming, 2004. Manuscript. Available from www.stanford.edu/boyd/~gp_tutorial.html.
• 6: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 7: W. Chen, C.-T. Hseih, and M. Pedram. Simultaneous gate sizing and placement. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(2):206--214, Feb. 2000.
• 8: Chris Chu , D. F. Wong, Closed form solutions to simultaneous buffer insertion/sizing and wire sizing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.343-371, July 2001 [doi>10.1145/383251.383256]
• 9: C. Chu and D. Wong. An efficient and optimal algorithm for simultaneous buffer and wire sizing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(9):1297--1304, 1999.
• 10: C. Chu and D. Wong. VLSI circuit performance optimization by geometric programming. Annals of Operations Research, 105:37--60, 2001.
• 11: D. Colleran, C. Portmann, A. Hassibi, C. Crusius, S. Mohan, S. Boyd, T. Lee, and M. Hershenson. Optimization of phase-locked loop circuits via geometric programming. In Proceedings of the Custom Integrated Circuits Conference (CICC), pages 326--328, Sept. 2003.
• 12: Jason Cong , Cheng-Kok Koh, Simultaneous driver and wire sizing for performance and power optimization, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.2 n.4, p.408-425, Dec. 1994 [doi>10.1109/92.335010]
• 13: J. Cong and K.-S. Leung. Optimal wiresizing under Elmore delay model. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14(3):321--336, 1995.
• 14: J. Cong and Z. Pan. Wire width planning for interconnect performance optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 21(3):319--329, 2002.
• 15: J. Dawson, S. Boyd, M. Hershenson, and T. Lee. Optimal allocation of local feedback in multistage amplifiers via geometric programming. IEEE Transactions on Circuits and Systems I, 48(1):1--11, January 2001.
• 16: J. Fishburn and A. Dunlop. TILOS: A posynomial programming approach to transistor sizing. In IEEE International Conference on Computer-Aided Design: ICCAD-85. Digest of Technical Papers, pages 326--328. IEEE Computer Society Press, 1985.
• 17: Y. Gao and D. Wong. Optimal shape function for a bidirectional wire under Elmore delay model. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 18(7):994--999, 1999.
• 18: Maria del Mar Hershenson, Design of pipeline analog-to-digital converters via geometric programming, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.317-324, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774620]
• 19: Maria del Mar Hershenson , Stephen P. Boyd , Thomas H. Lee, GPCAD: a tool for CMOS op-amp synthesis, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.296-303, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.288628]
• 20: Maria del Mar Hershenson , Ali Hajimiri , Sunderarajan S. Mohan , Stephen P. Boyd , Thomas H. Lee, Design and optimization of LC oscillators, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.65-69, November 07-11, 1999, San Jose, California, United States
• 21: I. Jiang, Y. Chang, and J. Jou. Crosstalk-driven interconnect optimization by simultaneous gate and wire sizing. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(9):999--1010, 2000.
• 22: K. Kasamsetty, M. Ketkar, and S. Sapatnekar. A new class of convex functions for delay modeling and its application to the transistor sizing problem. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 19(7):779--788, July 2000.
• 23: R. Kay and L. Pileggi. EWA: Efficient wiring-sizing algorithm for signal nets and clock nets. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 17(1):40--49, Jan. 1998.
• 24: S.-J. Kim, S. Boyd, S. Yun, D. Patil, and M. Horowitz. A heuristic for optimizing stochastic activity networks with applications to statistical digital circuit sizing, 2005. Manuscript. Available from www.stanford.edu/~boyd/heur_san_opt.html.
• 25: Y.-M. Lee, C. Chen, and D. Wong. Optimal wire-sizing function under the Elmore delay model with bounded wire sizes. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 49(11):1671--1677, 2002.
• 26: Tao Lin , Lawrence T. Pileggi, RC(L) interconnect sizing with second order considerations via posynomial programming, Proceedings of the 2001 international symposium on Physical design, p.16-21, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369720]
• 27: P. Mandal and V. Visvanathan. CMOS op-amp sizing using a geometric programming formulation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(1):22--38, Jan. 2001.
• 28: S. Mohan, M. Hershenson, S. Boyd, and T. Lee. Simple accurate expressions for planar spiral inductances. IEEE Journal of Solid-State Circuit, 34(10):1419--1424, Oct. 1999.
• 29: S. Mohan, M. Hershenson, S. Boyd, and T. Lee. Bandwidth extension in CMOS with optimized on-chip inductors. IEEE Journal of Solid-State Circuits, 35(3):346--355, March 2000.
• 30: Dinesh Patil , Sunghee Yun , Seung-Jean Kim , Alvin Cheung , Mark Horowitz , Stephen Boyd, A New Method for Design of Robust Digital Circuits, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.676-681, March 21-23, 2005 [doi>10.1109/ISQED.2005.11]
• 31: M. Pattanaik, S. Banerjee, and B. Bahinipati. GP based transistor sizing for optimal design of nanoscale CMOS inverter. In IEEE Conference on Nanotechnology, pages 524--527, Aug. 2003.
• 32: Zhanhai Qin , Chung-Kuan Cheng, Realizable parasitic reduction using generalized Y-Δ transformation, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775890]
• 33: J. Rubenstein, P. Penfield, and M. Horowitz. Signal delay in RC tree networks. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2(3):202--211, July 1983.
• 34: S. Sapatnekar. Wire sizing as a convex optimization problem: Exploring the area-delay tradeoff. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 15:1001--1011, Aug. 1996.
• 35: Sachin Sapatnekar, Timing, Springer-Verlag New York, Inc., Secaucus, NJ, 2004
• 36: Sachin S. Sapatnekar , Weitong Chuang, Power-delay optimizations in gate sizing, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.1, p.98-114, Jan. 2000 [doi>10.1145/329458.329473]
• 37: S. Sapatnekar, V. Rao, P. Vaidya, and S. Kang. An exact solution to the transistor sizing problem for CMOS circuits using convex optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 12(11):1621--1634, Nov. 1993.
• 38: Ivan Sutherland , Bob Sproull , David Harris, Logical effort: designing fast CMOS circuits, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 39: Johan P. Vanderhaegen , Robert W. Brodersen, Automated design of operational transconductance amplifiers using reversed geometric programming, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996608]
• 40: Yang Xu , Lawrence T. Pileggi , Stephen P. Boyd, ORACLE: optimization with recourse of analog circuits including layout extraction, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996611]
• 41: F. Young, C. Chu, W. Luk, and Y. Wong. Handling soft modules in general nonslicing floorplan using Lagrangian relaxation. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 20(5):687--629, May 2001.

INDEX TERMS

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

General Terms:
Algorithms, Design

Keywords:
circuit sizing, convex optimization, generalized geometric programming, geometric programming