Precise identification of the worst-case voltage drop conditions in power grid verification

ABSTRACT

Identifying worst-case voltage drop conditions in every module supplied by the power grid is a crucial problem in modern IC design. In this paper we develop a novel methodology for power grid verification which is based on accurately constructing the space of current variations of the supplied modules and locating its precise points that yield the worst-case voltage drop conditions. The construction of the current space is performed via plain simulation and statistical extrapolation using results from extreme value theory. The method overcomes limitations of past methods which either relied on loosely bounding the worst-case voltage drop, or abstracted the current space in a vague and incomplete set of bound-type constraints. Experimental results verify the potential of the proposed method to identify worst-case conditions and demonstrate the pessimism inherent in previous bound-type approaches.

REFERENCES

• 1: Abhijit Dharchoudhury , Rajendran Panda , David Blaauw , Ravi Vaidyanathan , Bogdan Tutuianu , David Bearden, Design and analysis of power distribution networks in PowerPC microprocessors, Proceedings of the 35th annual conference on Design automation, p.738-743, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277229]
• 2: Gregory Steele , David Overhauser , Steffen Rochel , Syed Zakir Hussain, Full-chip verification methods for DSM power distribution systems, Proceedings of the 35th annual conference on Design automation, p.744-749, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277231]
• 3: S. Chowdhury and J. Barkatullah, "Estimation of maximum currents in MOS IC logic circuits", IEEE Trans. Computer-Aided Design, vol. 9, pp. 642--654, 1990.
• 4: H. Kriplani, F. Najm, and I. Hajj, "Pattern independent maximum current estimation in power and ground buses of CMOS VLSI circuits: algorithms, signal correlations and their resolution", IEEE Trans. Computer-Aided Design, vol. 14, pp. 998--1012, 1995.
• 5: A. Hill, C. Teng, and S. Kang, "Simulation-based maximum power estimation", IEEE Int. Symp. Circuits and Systems, 1996.
• 6: Chih-Shun Ding , Qing Wu , Chen-Ta Hsieh , Massoud Pedram, Statistical estimation of the cumulative distribution function for power dissipation in VLSI cirucits, Proceedings of the 34th annual conference on Design automation, p.371-376, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266174]
• 7: Q. Wu, Q. Qiu, and M. Pedram, "Estimation of peak power dissipation in VLSI circuits using the limiting distributions of extreme order statistics", IEEE Trans. Computer-Aided Design, vol. 20, pp. 942--956, 2001.
• 8: N. Evmorfopoulos, G. Stamoulis, and J. Avaritsiotis, "A Monte Carlo approach for maximum power estimation based on extreme value theory", IEEE Trans. Computer-Aided Design, vol. 21, pp. 415--432, 2002.
• 9: J. Galambos, The Asymptotic Theory of Extreme Order Statistics, 2^nd ed., Krieger, 1987
• 10: Dionysios Kouroussis , Farid N. Najm, A static pattern-independent technique for power grid voltage integrity verification, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775861]
• 11: Haifeng Qian , Sani R. Nassif , Sachin S. Sapatnekar, Early-stage power grid analysis for uncertain working modes, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981095]
• 12: L. Pillage, R. Rohrer, and C. Visweswariah, Electronic Circuit and System Simulation Methods, McGraw-Hill, 1995.
• 13: H. Royden, Real Analysis, 3^rd ed., Prentice-Hall, 1988.
• 14: S. Resnick, Extreme Values, Regular Variation and Point Processes, Springer, 1987.
• 15: I. Ibragimov and Y. Linnik, Independent and Stationary Sequences of Random Variables, Wolters-Noordhoff, 1971.
• 16: H. Joe, Multivariate Models and Dependence Concepts, Chapman and Hall, 1996.
• 17: S. Kotz, N. Balakrishnan, and N. Johnson, Continuous Multivariate Distributions, vol. 1, Wiley, 2000.
• 18: S. Kotz and S. Nadarajah, Extreme Value Distributions, Imperial College Press, 2002.
• 19: H. T. Kung , F. Luccio , F. P. Preparata, On Finding the Maxima of a Set of Vectors, Journal of the ACM (JACM), v.22 n.4, p.469-476, Oct. 1975 [doi>10.1145/321906.321910]
• 20: D. Luenberger, Linear and Nonlinear Programming, 2^nd ed., Addison-Wesley, 1984.
• 21: R. Fletcher, Practical methods of optimization; (2nd ed.), Wiley-Interscience, New York, NY, 1987

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Simulation; Verification
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance