An efficient algorithm for statistical minimization of total power under timing yield constraints

ABSTRACT

Power minimization under variability is formulated as a rigorous statistical robust optimization program with a guarantee of power and timing yields. Both power and timing metrics are treated probabilistically. Power reduction is performed by simultaneous sizing and dual threshold voltage assignment. An extremely fast run-time is achieved by casting the problem as a second-order conic problem and solving it using efficient interior-point optimization methods. When compared to the deterministic optimization, the new algorithm, on average, reduces static power by 31% and total power by 17% without the loss of parametric yield. The run time on a variety of public and industrial benchmarks is 30X faster than other known statistical power minimization algorithms.

REFERENCES

• 1: Chandu Visweswariah, Death, taxes and failing chips, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775921]
• 2: Y. Taur et al., "CMOS scaling into the nanometer regime," Proc. of the IEEE, no. 4, 1997, pp. 486--504.
• 3: Robert W. Brodersen , Mark A. Horowitz , Dejan Markovic , Borivoje Nikolic , Vladimir Stojanovic, Methods for true power minimization, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.35-42, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774578]
• 4: Shekhar Borkar , Tanay Karnik , Siva Narendra , Jim Tschanz , Ali Keshavarzi , Vivek De, Parameter variations and impact on circuits and microarchitecture, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775920]
• 5: Supamas Sirichotiyakul , Tim Edwards , Chanhee Oh , Jingyan Zuo , Abhijit Dharchoudhury , Rajendran Panda , David Blaauw, Stand-by power minimization through simultaneous threshold voltage selection and circuit sizing, Proceedings of the 36th ACM/IEEE conference on Design automation, p.436-441, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309975]
• 6: Qi Wang , Sarma B. K. Vrudhula, Static power optimization of deep submicron CMOS circuits for dual VT technology, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.490-496, November 08-12, 1998, San Jose, California, United States [doi>10.1145/288548.289076]
• 7: David Nguyen , Abhijit Davare , Michael Orshansky , David Chinnery , Brandon Thompson , Kurt Keutzer, Minimization of dynamic and static power through joint assignment of threshold voltages and sizing optimization, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871545]
• 8: Hongliang Chang , Sachin S. Sapatnekar, Statistical Timing Analysis Considering Spatial Correlations using a Single Pert-Like Traversal, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.621, November 09-13, 2003 [doi>10.1109/ICCAD.2003.129]
• 9: Xiaoliang Bai , Chandu Visweswariah , Philip N. Strenski, Uncertainty-aware circuit optimization, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513935]
• 10: Sreeja Raj , Sarma B. K. Vrudhula , Janet Wang, A methodology to improve timing yield in the presence of process variations, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996694]
• 11: Ashish Srivastava , Dennis Sylvester , David Blaauw, Statistical optimization of leakage power considering process variations using dual-Vth and sizing, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996775]
• 12: E. T. A. F. Jacobs , M. R. C. M. Berkelaar, Gate sizing using a statistical delay model, Proceedings of the conference on Design, automation and test in Europe, p.283-291, March 27-30, 2000, Paris, France [doi>10.1145/343647.343782]
• 13: Seung Hoon Choi , Bipul C. Paul , Kaushik Roy, Novel sizing algorithm for yield improvement under process variation in nanometer technology, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996695]
• 14: Murari Mani , Michael Orshansky, A New Statistical Optimization Algorithm for Gate Sizing, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.272-277, October 11-13, 2004
• 15: J. Fishburn and A. Dunlop, "TILOS: A Posynomial Programming Approach to Transistor Sizing," Proc. of ICCAD, 1985, pp. 326--328.
• 16: D. Markovic et al., "Methods for true energy-performance optimization," J. of Solid-State Circuits, 2004, pp. 1282--1293.
• 17: V. Sundararajan et al., "Fast and Exact Transistor sizing Based on Iterative Relaxation," IEEE Trans. on CAD, vol. 21, 2002, pp.568--581.
• 18: James Kao , Siva Narendra , Anantha Chandrakasan, Subthreshold leakage modeling and reduction techniques, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.141-148, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774593]
• 19: C. Chatfield, Introduction to Multivariate analysis, Chapman and Hall, 1980.
• 20: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 21: Kim et al., "A Heuristic for Optimizing Stochastic Activity Networks with Applications to Statistical Circuit Sizing", preprint.
• 22: A. Prekopa, Stochastic Programming, Kluwer Academic, 1995
• 23: http://www.mosek.com/documentation.html#manuals
• 24: Y. Cao et al., "New paradigm of predictive MOSFET and interconnect modeling for early circuit design," Proc. of IEEE CICC, 2000, pp. 201--204.
• 25: M. Pelgrom et al., Matching Properties of MOS Transistors, IEEE Journal of Solid-State Circuits, vol. 24, 1989, pp. 1433--1440.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids

General Terms:
Algorithms, Design, Performance, Reliability

Keywords:
leakage, manufacturability, statistical optimization