Power grid analysis using random walks

Haifeng Qian, Sani R. Nassif, Sachin S. Sapatnekar

Research output: Contribution to journalArticlepeer-review

144 Scopus citations


This paper presents a class of power grid analyzers based on a random-walk technique. A generic algorithm is first demonstrated for dc analysis, with linear runtime and the desirable property of localizing computation. Next, by combining this generic analyzer with a divide-and-conquer strategy, a single-level hierarchical method is built and extended to multilevel and "virtual-layer" hierarchy. Experimental results show that these algorithms not only achieve speedups over the generic random-walk method, but also are more robust in solving various types of industrial circuits. Finally, capacitors and inductors are incorporated into the framework, and it is shown that transient analysis can be carried out efficiently. For example, dc analysis of a 71 K-node power grid with C4 pads takes 4.16 s; a 348 K-node wire-bond dc power grid is solved in 93.64 s; transient analysis of a 642 K-node power grid takes 2.1 s per timestep.

Original languageEnglish (US)
Pages (from-to)1204-1224
Number of pages21
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number8
StatePublished - Aug 2005

Bibliographical note

Funding Information:
Manuscript received November 29, 2003; revised October 8, 2004. This work was supported in part by the Semiconductor Research Corporation (SRC) under Contract 2003-TJ-1092, by the National Science Foundation (NSF) under award CCR-0205227, and by an IBM Faculty Award.


  • Capacitance
  • Inductance
  • Physical design
  • Power grid
  • Random walk
  • Simulation
  • Supply network


Dive into the research topics of 'Power grid analysis using random walks'. Together they form a unique fingerprint.

Cite this