Stochastic variational analysis of large power grids considering intra-die correlations

ABSTRACT

For statistical timing and power analysis that are very importantproblems in the sub-100nm technologies, stochastic analysis of power grids that characterizes the voltage fluctuations due to process variations is inevitable. In this paper, we propose an efficient algorithm for the variational analysis of large power grids in the presence of a significant number of Gaussian intra-die process variables that are correlated. We consider variations in the power grid's electrical parameters as spatial stochastic processes and express them as linear expansions in an orthonormal series of random variables using the Karhunen-Loéve(KLE) method. The voltage response is then represented as an orthonormal polynomial series and the coefficients are obtained optimally using the Galerkin method. We propose a novel method to separate the stochastic analysis for the random variables that effect only the inputs (e.g, drain currents) and for those that effect the system parameters as well (e.g., conductance, capacitance). We show that this parallelism can result in significant speed-ups in addition to the speed-ups inherent to Galerkin-based methods. Our analysis has been applied to several industrial power grids and the results show speed-ups of up to two orders of magnitude over Monte Carlo simulations for comparable accuracy.

REFERENCES

• 1: Peng Li, Variational analysis of large power grids by exploring statistical sampling sharing and spatial locality, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.645-651, November 06-10, 2005, San Jose, CA
• 2: M. Loeve. Probability theory., 4th Edition. NY. Springer Verlag
• 3: 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]
• 4: D. Stark, and M. Horowitz. Techniques for calculating currents and voltages in VLSI power supply networks., IEEE TCAD, vol. CAD-9, Feb. 1979, pp. 126--132.
• 5: Min Zhao , Rajendran V. Panda , Sachin S. Sapatnekar , Tim Edwards , Rajat Chaudhry , David Blaauw, Hierarchical analysis of power distribution networks, Proceedings of the 37th conference on Design automation, p.150-155, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337355]
• 6: Haifeng Qian , Sani R. Nassif , Sachin S. Sapatnekar, Random walks in a supply network, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775860]
• 7: H. Kriplani, F. Najm, and I. Hajj. Pattern independent minimum current estimation in power and ground buses of CMOS VLSI Circuits.,In IEEE TCAD, vol. 14, Aug.1995, pp. 998--1012.
• 8: Rajat Chaudhry , Rajendran Panda , Tim Edwards , David Blaauw, Design and Analysis of Power Distribution Networks with Accurate RLC Models, Proceedings of the 13th International Conference on VLSI Design, p.151, January 04-07, 2000
• 9: Sanjay Pant , David Blaauw , Vladimir Zolotov , Savithri Sundareswaran , Rajendran Panda, A stochastic approach To power grid analysis, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996616]
• 10: Imad A. Ferzli , Farid N. Najm, Statistical Verification of Power Grids Considering Process-Induced Leakage Current Variations, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.770, November 09-13, 2003
• 11: D. Boning, and S. R. Nassif. Models of process variations in device and interconnect in design of high performance microprocessor circuits. A. Chandrakasan, W.J. Bowhill and F. Fox ed. John Wiley and Sons, NY, 2001.
• 12: Sani R. Nassif , Joseph N. Kozhaya, Fast power grid simulation, Proceedings of the 37th conference on Design automation, p.156-161, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337359]
• 13: Roger G. Ghanem , Pol D. Spanos, Stochastic finite elements: a spectral approach, Springer-Verlag New York, Inc., New York, NY, 1991
• 14: Rajeev R. Rao , Anirudh Devgan , David Blaauw , Dennis Sylvester, Parametric yield estimation considering leakage variability, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996693]
• 15: Vikas Mehrotra , Shiou Lin Sam , Duane Boning , Anantha Chandrakasan , Rakesh Vallishayee , Sani Nassif, A methodology for modeling the effects of systematic within-die interconnect and device variation on circuit performance, Proceedings of the 37th conference on Design automation, p.172-175, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337370]
• 16: T. Davis. http://wwwciseufledu/research/sparse/UFsparse. Sparse Matrix Package, Univ. of Florida.
• 17: P. Ghanta, S. Bhardwaj, and S. Vrudhula. http://www.tauworkshopcom/05_Slides/TAU_ghanta.pdf. Presentation Slides, ACM/IEEE TAU Workshop, 2005.
• 18: Paul Friedberg , Yu Cao , Jason Cain , Ruth Wang , Jan Rabaey , Costas Spanos, Modeling Within-Die Spatial Correlation Effects for Process-Design Co-Optimization, Proceedings of the 6th International Symposium on Quality of Electronic Design, p.516-521, March 21-23, 2005 [doi>10.1109/ISQED.2005.82]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Verification

General Terms:
Algorithms, Performance, Verification

Keywords:
correlations, orthonormal polynomials, polynomial chaos, power grids, process variations, stochastic analysis