Incremental analysis of power grids using backward random walks

Power grid design and analysis is a critical part of modern VLSI chip design and demands tools for accurate modeling and efficient analysis. The process of power grid design is inherently iterative, during which numerous small changes are made to an initial design, either to enhance the design or to fix design constraint violations. Due to the large sizes of power grids inmodern chips, updating the solution for these perturbations can be a computationally intensive task. In this work, we first introduce an accurate modeling methodology for power grids that, contrary to conventional models, can result in asymmetrical equations. Next, we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is then updated for this significantly smaller region only. The proposed algorithm is capable of handling both symmetrical and asymmetrical power grid equations. Moreover, it can handle consecutive perturbations without any degradation in the quality of the solution. Experimental results show speedups of up to 13× for our incremental solver, as compared to a full resolve of the power grid. Categories and Subject Descriptors: B.8.2 [Performance and Reliability]: Performance Analysis and Design Aids General Terms: Reliability.