Power grid simulation via efficient sampling-based sensitivity analysis and hierarchical symbolic relaxation

ABSTRACT

On-chip supply networks are playing an increasingly important role for modern nanometer-scale designs. However, the ever growing sizes of power grids make the analysis problem extremely difficult thereby introducing severe challenges in design and optimization. The inherent analysis complexity calls for innovations in simulation techniques that must provide appropriate accuracy, efficiency as well as the tradeoff thereof to aid design verification and optimization. In this paper, we first present a sampling-based sensitivity analysis by employing the notation of importance sampling in a Monte Carlo based circuit simulation framework. This technique allows the extraction of multi-parameter sensitivities for the node voltages of interest in the same Monte Carlo runs that are used for computing the nominal voltage values. For more efficient nonstructured whole-grid solution approaches, we further introduce a new direct solution method by embedding symbolic relaxation steps in a hierarchical fashion. As a direct method, the proposed hierarchical symbolic relaxation is suitable to both dc and transient analyses. Circuit examples are included to demonstrate the efficacy of the proposed techniques.

REFERENCES

• 1: 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]
• 2: J. Kozhaya, S. Nassif and F. Najm, "A multi-grid like technique for power grid analysis," IEEE Trans. CAD, vol. 21, no. 10, Oct. 2002.
• 3: M. Zhao, R. Panda, S. Sapatnekar and D. Blaauw, "Hierarchical analysis of power distribution networks," IEEE Trans. on CAD, vol. 21, no. 2, Feb. 2002.
• 4: Haihua Su , Emrah Acar , Sani R. Nassif, Power grid reduction based on algebraic multigrid principles, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775863]
• 5: 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]
• 6: Reuven Y. Rubinstein, Simulation and the Monte Carlo Method, John Wiley & Sons, Inc., New York, NY, 1981
• 7: Haifeng Qian , Sachin S. Sapatnekar, Hierarchical random-walk algorithms for power grid analysis, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.499-504, January 27-30, 2004, Yokohama, Japan
• 8: E. Chiprout, Fast flip-chip power grid analysis via locality and grid shells, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.485-488, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382626]
• 9: Y. Coz and R. Iverson, "A stochastic algorithm for high speed capacitance extraction in integrated circuits," Solid State Electronics, vol. 35, no. 7, pp. 1005--1012, 1992.
• 10: Xiang-Dong Tan , C.-J. Richard Shi , Dragos Lungeanu , Jyh-Chwen Lee , Li-Pen Yuan, Reliability-constrained area optimization of VLSI power/ground networks via sequence of linear programmings, Proceedings of the 36th ACM/IEEE conference on Design automation, p.78-83, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.309880]
• 11: S. Director and R. Rohrer, "The generalized adjoint network and network sensitivities," IEEE Trans. Circ. Theory, vol. 16, no. 8, pp. 318--323, Aug 1969.
• 12: Shiyou Zhao , Kaushik Roy , Cheng-Kok Koh, Decoupling capacitance allocation for power supply noise suppression, Proceedings of the 2001 international symposium on Physical design, p.66-71, April 01-04, 2001, Sonoma, California, United States [doi>10.1145/369691.369737]
• 13: Hui Zheng , Byron Krauter , Lawrence Pileggi, Electrical Modeling of Integrated-Package Power and Ground Distributions, IEEE Design & Test, v.20 n.3, p.24-31, May 2003 [doi>10.1109/MDT.2003.1198682]
• 14: H. Su, S. Sapatnekar and S. Nassif, "Optimal decoupling capacitor sizing and placement for standard-cell layout designs," IEEE Trans. on CAD, vol. 22, no. 4, April 2003.
• 15: 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]
• 16: T. Hesterberg, "Advances in importance sampling," Ph.D. Dissertation, Dept. of Statistics, Standford University, 1988.
• 17: M. Iosifescu, "Finite Markov processes and their applications," John Wiley & Sons, 1980.

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
power grids, sensitivity and hierarchical analysis