Efficient algorithms for fast IR drop analysis exploiting locality

Closed-form expressions and related algorithms for fast power grid analysis are proposed in this paper. Four algorithms to determine the IR voltage drop at an arbitrary node are described when voltage supplies and current loads are non-uniformly distributed throughout a power grid. Two techniques are used to determine the effective impedance in a non-uniform and semi-uniform power grid. An effective resistance model is proposed for semi-uniform power grids. The principle of spatial locality is exploited to accelerate the proposed power grid analysis process. Since no iterations are required for the proposed IR drop analysis, the proposed algorithms are over 60 and two times faster for smaller power grids composed of less than five million nodes and over 175 and three times faster for larger power grids composed of more than 25 million nodes as compared to, respectively, the random walk and second order iterative methods. The proposed method exhibits less than 0.3% error.

► Closed-form expressions for fast IR voltage drop analysis are proposed.
► Computational runtime is significantly shorter than existing power grid analysis methods.
► Principle of spacial locality and error correction windows are utilized. Localized power grid analysis is significantly faster.