Efficient large-scale power grid analysis based on preconditioned krylov-subspace iterative methods

ABSTRACT

In this paper, we propose preconditioned Krylov-subspace iterative methods to perform efficient DC and transient simulations for large-scale linear circuits with an emphasis on power delivery circuits. We also prove that a circuit with inductors can be simplified from MNA to NA format, and the matrix becomes an s.p.d matrix. This property makes it suitable for the conjugate gradient with incomplete Cholesky decomposition as the preconditioner, which is faster than other direct and iterative methods. Extensive experimental results on large-scale industrial power grid circuits show that our method is over 200 times faster for DC analysis and around 10 times faster for transient simulation compared to SPICE3. Furthermore, our algorithm reduces over 75% of memory usage than SPICE3 while the accuracy is not compromised.

REFERENCES

• 1: 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]
• 2: 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]
• 3: Howard H. Chen , David D. Ling, Power supply noise analysis methodology for deep-submicron VLSI chip design, Proceedings of the 34th annual conference on Design automation, p.638-643, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266307]
• 4: Yi-Min Jiang , Kwang-Ting Cheng, Analysis of performance impact caused by power supply noise in deep submicron devices, Proceedings of the 36th ACM/IEEE conference on Design automation, p.760-765, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310053]
• 5: Rajendran Panda , David Blaauw , Rajat Chaudhry , Vladimir Zolotov , Brian Young , Ravi Ramaraju, Model and analysis for combined package and on-chip power grid simulation, Proceedings of the 2000 international symposium on Low power electronics and design, p.179-184, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344574]
• 6: 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]
• 7: 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]
• 8: R.Freund,"Passive reduced-order models for interconnect simulation and their computation via Krylov-subspace algorithms,"Numerical Analysis Manuscript No.98-3-06,Bell Lab.,1998
• 9: Hasan Dag, Iterative methods and parallel computation for power systems, University of Wisconsin at Madison, Madison, WI, 1996
• 10: Y. Saad, Iterative Methods for Sparse Linear Systems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2003
• 11: M.Jones and P.Plassmann,"An improved incomplete Cholesky factorization,"Argonne National Laboratory,1992.
• 12: Michael T.Heath,"Parallel direct methods for sparse linear systems,"Parallel Numerical Algorithms,p55-90,1997

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Measurement, Performance, Theory