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 language||English (US)|
|Number of pages||21|
|Journal||IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems|
|State||Published - Aug 2005|
Bibliographical noteFunding 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.
- Physical design
- Power grid
- Random walk
- Supply network