Application of random walks for the analysis of power grids in modern VLSI chips

University of Minnesota Ph.D. dissertatation. August 2013. Major: Electrical Engineering. Advisor: Sachin S. Sapatnekar. 1 computer file (PDF); ix, 104 pages, appendices A-C.Power grid design and analysis is a critical part of modern VLSI chip design and demands tools for accurate modeling and efficient analysis. In this thesis, we develop new solutions for solving power grids, both incrementally and in total, based on an approach that uses random walks. 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 in modern chips, updating the solution for these perturbations can be a computationally intensive task. The first issue addressed in the thesis relates to the problem of incremental analysis of power grids. We introduce two incremental solvers that utilize forward and 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. Our forward incremental random walk solver is capable of identifying the region of influence efficiently leveraging the record of the forward random walks that is obtained in a preprocessing step performed once for a series of consecutive perturbations. Experimental results show that our forward incremental random walk solver achieves speedups of up to 3x for 20 and up to 2x for 10 consecutive perturbations compared to a full system solution. An alternative approach, backward incremental random walk solver, identifies the region of influence directly from perturbed system. It can handle consecutive perturbations without any degradation in the quality of the solution. Moreover, this approach is particularly well-suited to a new and more accurate modeling methodology for power grids, introduced in this work, that can result in asymmetrical systems of linear equations. Experimental results show that our backward incremental random walk solver achieves speedups of up to 13x as compared to a full re-solve of the power grid.Another contribution of this thesis is to introduce a scaled random walk solver that is capable of finding the solution of individual nodes in the power grid much faster than the conventional random walks. This solver uses the notion of importance sampling to reduce the variance of the walks and therefore improve the runtime of the game.Experimental results show that our scaled solver is up to 2x faster than the naive random walks