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

Fast analysis of power grid networks has been a challenging problem for many years. The huge size renders circuit simu-lation inefficient and the large number of inputs further lim-its the application of existing Krylov-subspace macromodel-ing algorithms. However, strong locality has been observed that two nodes geometrically far have very small electrical impact on each other because of the exponential attenua-tion. However, no systematic approaches have been pro-posed to exploit such locality. In this paper, we propose a novel modeling and simulation scheme, which can automati-cally 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. 1