Acknowledgements

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 walk