Application of random walks for the analysis of power grids in modern VLSI chips
2013-08
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Application of random walks for the analysis of power grids in modern VLSI chips
Authors
Published Date
2013-08
Publisher
Type
Thesis or Dissertation
Abstract
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.
Keywords
Description
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.
Related to
Replaces
License
Collections
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Boghrati, Baktash. (2013). Application of random walks for the analysis of power grids in modern VLSI chips. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/157738.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.