Fast algorithms for IR drop analysis in large power grid

Yu Zhong; Martin D. F. Wong

doi:10.1109/ICCAD.2005.1560093

Fast algorithms for IR drop analysis in large power grid

Yu Zhong, Martin D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

108 Citations (Scopus)

Abstract

Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical Successive Over Relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the Random-Walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the Random-Walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the Random Walk produced a solution with maximum error of 5.7 mV.

Original language	English
Title of host publication	Proceedings of the 2005 International Conference on Computer-Aided Design
Place of Publication	United States
Publisher	IEEE
Pages	351-357
Number of pages	7
ISBN (Print)	078039254X, 9780780392540
DOIs	https://doi.org/10.1109/ICCAD.2005.1560093
Publication status	Published - Nov 2005
Event	IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005 - San Jose, United States Duration: 6 Nov 2005 → 10 Nov 2005 https://ieeexplore.ieee.org/xpl/conhome/10431/proceeding (Conference proceedings)

Publication series

Name	IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume	2005
ISSN (Print)	1092-3152
ISSN (Electronic)	1558-2434

Conference

Conference	IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005
Country/Territory	United States
City	San Jose
Period	6/11/05 → 10/11/05
Internet address	https://ieeexplore.ieee.org/xpl/conhome/10431/proceeding (Conference proceedings)

Scopus Subject Areas

Software
Computer Science Applications
Computer Graphics and Computer-Aided Design

Access to Document

10.1109/ICCAD.2005.1560093

Cite this

@inproceedings{067c68c5adfa49cb8a7587a558081fa3,

title = "Fast algorithms for IR drop analysis in large power grid",

abstract = "Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical Successive Over Relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the Random-Walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the Random-Walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the Random Walk produced a solution with maximum error of 5.7 mV.",

author = "Yu Zhong and Wong, {Martin D. F.}",

note = "Funding information: This work was partially supported by the National Science Foundation under grant CCR-0306244. Publisher copyright: {\textcopyright} 2005 IEEE.; IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005 ; Conference date: 06-11-2005 Through 10-11-2005",

year = "2005",

month = nov,

doi = "10.1109/ICCAD.2005.1560093",

language = "English",

isbn = "078039254X",

series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD",

publisher = "IEEE",

pages = "351--357",

booktitle = "Proceedings of the 2005 International Conference on Computer-Aided Design",

address = "United States",

url = "https://ieeexplore.ieee.org/xpl/conhome/10431/proceeding",

}

Zhong, Y & Wong, MDF 2005, Fast algorithms for IR drop analysis in large power grid. in Proceedings of the 2005 International Conference on Computer-Aided Design. IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD, vol. 2005, IEEE, United States, pp. 351-357, IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005, San Jose, California, United States, 6/11/05. https://doi.org/10.1109/ICCAD.2005.1560093

Fast algorithms for IR drop analysis in large power grid. / Zhong, Yu; Wong, Martin D. F.
Proceedings of the 2005 International Conference on Computer-Aided Design. United States: IEEE, 2005. p. 351-357 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD; Vol. 2005).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Fast algorithms for IR drop analysis in large power grid

AU - Zhong, Yu

AU - Wong, Martin D. F.

PY - 2005/11

Y1 - 2005/11

N2 - Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical Successive Over Relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the Random-Walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the Random-Walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the Random Walk produced a solution with maximum error of 5.7 mV.

AB - Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical Successive Over Relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the Random-Walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the Random-Walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the Random Walk produced a solution with maximum error of 5.7 mV.

UR - http://www.scopus.com/inward/record.url?scp=33751418985&partnerID=8YFLogxK

U2 - 10.1109/ICCAD.2005.1560093

DO - 10.1109/ICCAD.2005.1560093

M3 - Conference proceeding

AN - SCOPUS:33751418985

SN - 078039254X

SN - 9780780392540

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

SP - 351

EP - 357

BT - Proceedings of the 2005 International Conference on Computer-Aided Design

PB - IEEE

CY - United States

T2 - IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005

Y2 - 6 November 2005 through 10 November 2005

ER -

Fast algorithms for IR drop analysis in large power grid

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this