Geometric Programming and its Applications to EDA Problems
S. Boyd, S.-J. Kim, and S. Mohan
Tutorial presentation, Design, Automation and Test in Europe (DATE), Munich, Germany, March 2005. An earlier version of the tutorial was presented at Integrated Circuit Computer-Aided Design (ICCAD), Santa Clara, CA, November 2004.
Geometric programming (GP) describes a type of optimization problem that has been known since the 1970s, but recently has attracted more attention for several reasons. The first is the development of extremely efficient interior-point algorithms for solving GPs. The second is the discovery that a wide variety of digital and analog circuit design problems can be at least approximately expressed as GPs. We start with the basics of GP, and a recent powerful extension called generalized geometric programming (GGP). We'll illustrate how GGP can be used in a variety of circuit design problems, ranging from device sizing in op-amps to joint selection of threshold voltage, supply voltage, and device sizes in digital circuit design. We consider simple problem formulations involving tradeoffs among area, power, and delay, as well as more sophisticated formulations involving statistical and robust design, and design for multiple operating modes. We'll also give examples involving hierarchical design and joint electrical/physical design. The focus will be on GP modeling, the task of approximately formulating a design problem in GP format. We'll also cover related topics such as fitting empirical data or functions in a form compatible with GP, and how to handle discrete constraints on some of the variables.