Power grid reduction based on algebraic multigrid principles

ABSTRACT

With the scaling of technology, power grid noise is becoming increasingly significant for circuit performance. A typical power grid circuit contains millions of linear elements, making noise analysis and verification challenging in terms of both run time and memory. We propose a power grid reduction scheme based on algebraic multigrid principles, in which the coarser-level grid and the restriction operators are constructed automatically from the circuit matrices. This method is suitable for large-scale power grid transient and AC analysis. Experimental results show an order of magnitude speed-up over flat analysis in addition to practical tradeoffs for accuracy, CPU time and memory usage.

REFERENCES

• 1: W. L. Briggs. A Multigrid Tutorial, 1987.
• 2: J. Fang, Z. Chen, Y. Chen, D. Xue, and J. Zhao. Integrated Electromagnetic and Circuit Simulation for Signal Integrity Analysis of High-Speed Electronic Packages. In Proc. of 1997 Government Microcircuit Applications Conference, pages 347--350, Las Vegas, NV, March 1997.
• 3: W. Hackbusch. Multi-Grid Methods and Applications. Springer-Verlag Berlin, Berlin, 1985.
• 4: J. N. Kozhaya, S. R. Nassif, and F. N. Najm. A Multigrid-Like Technique for Power Grid Analysis. IEEE Trans. CAD, October 2002.
• 5: 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]
• 6: L. T. Pillage, R. A. Rohrer, and C. Visweswariah. Electronic and System Simulation Methods. McGraw-Hill, New York, NY, 1995.
• 7: J. W. Ruge and K. Stuben. Handbook of Mathematics and Computational Science. S. McCormick, Ed., 1987.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Algorithms

Keywords:
AC analysis, algebraic multigrid, power grid noise, transient analysis