Modeling and simulation for on-chip power grid networks by locally dominant Krylov subspace method

ABSTRACT

Fast analysis of power grid networks has been a challenging problem for many years. The huge size renders circuit simulation inefficient and the large number of inputs further limits the application of existing Krylov-subspace macromodeling algorithms. However, strong locality has been observed that two nodes geometrically far have very small electrical impact on each other because of the exponential attenuation. However, no systematic approaches have been proposed to exploit such locality. In this paper, we propose a novel modeling and simulation scheme, which can automatically identify the dominant inputs for a given observed node in a power grid network. This enables us to build extremely compact models by projecting the system onto the locally dominant Krylov subspace corresponding to those dominant inputs only. The resulting simulation can be very fast with the compact models if we only need to view the responses of a few nodes under many different inputs. Experimental results show that the proposed method can have at least 100X speedup over SPICE-like simulations on a number of large power grid networks up to 1M nodes.

REFERENCES

• 1: E. H. Bristol, "On a new measure of interaction for multivariable process control," IEEE Trans. Automat. Contr., vol. AC-11, pp. 132--134, 1966.
• 2: Yahong Cao , Yu-Min Lee , Tsung-Hao Chen , Charlie Chung-Ping Chen, HiPRIME:: hierarchical and passivity reserved interconnect macromodeling engine for RLKC power delivery, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514017]
• 3: Tsung-Hao Chen , Charlie Chung-Ping Chen, Efficient large-scale power grid analysis based on preconditioned krylov-subspace iterative methods, Proceedings of the 38th conference on Design automation, p.559-562, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379023]
• 4: 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]
• 5: P. Feldmann and R. W. Freund, "Efficient linear circuit analysis by Pade approximation via the Lanczos process," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 5, pp. 639--649, May 1995.
• 6: J. N. Kozhaya, S. R. Nassif, and F. N. Najm, "A multigrid-like technique for power grid analysis," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 10, pp. 1148--1160, Oct. 2002.
• 7: Duo Li , Sheldon X.-D. Tan , Bruce McGaughy, ETBR: extended truncated balanced realization method for on-chip power grid network analysis, Proceedings of the conference on Design, automation and test in Europe, March 10-14, 2008, Munich, Germany [doi>10.1145/1403375.1403479]
• 8: A. Odabasioglu, M. Celik, and L. Pileggi, "PRIMA: Passive reduced-order interconnect macromodeling algorithm," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, pp. 645--654, 1998.
• 9: Sanjay Pant , Eli Chiprout, Power grid physics and implications for CAD, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146964]
• 10: Sanjay Pant , Eli Chiprout, Power grid physics and implications for CAD, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146964]
• 11: 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]
• 12: L. Miguel Silveira , Mattan Kamon , Ibrahim Elfadel , Jacob White, A coordinate-transformed Arnoldi algorithm for generating guaranteed stable reduced-order models of RLC circuits, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.288-294, November 10-14, 1996, San Jose, California, United States
• 13: Sheldon Tan , Lei He, Advanced Model Order Reduction Techniques in VLSI Design, Cambridge University Press, New York, NY, 2007
• 14: Janet M. Wang , Tuyen V. Nguyen, Extended Krylov subspace method for reduced order analysis of linear circuits with multiple sources, Proceedings of the 37th conference on Design automation, p.247-252, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337407]
• 15: M. Zhao, R. V. Panda, S. S. Sapatnekar, and D. Blaauw, "Hierarchical analysis of power distribution networks," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 21, no. 2, pp. 159--168, Feb. 2002.