Incremental analysis of power grids using backward random walks

Baktash Boghrati, Sachin S. Sapatnekar

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Article number31
JournalACM Transactions on Design Automation of Electronic Systems
Issue number3
StatePublished - Jun 2014


  • Architectures
  • Digital circuits
  • Incremental analysis
  • Low power
  • Power grid
  • Random walks
  • Reliability


Dive into the research topics of 'Incremental analysis of power grids using backward random walks'. Together they form a unique fingerprint.

Cite this