Fast algorithms for IR drop analysis in large power grid

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

106 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 languageEnglish
Title of host publicationProceedings of the 2005 International Conference on Computer-Aided Design
Place of PublicationUnited States
PublisherIEEE
Pages351-357
Number of pages7
DOIs
Publication statusPublished - Nov 2005
EventIEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005 - San Jose, United States
Duration: 6 Nov 200510 Nov 2005
https://ieeexplore.ieee.org/xpl/conhome/10431/proceeding (Conference proceedings)

Conference

ConferenceIEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005
Country/TerritoryUnited States
CitySan Jose
Period6/11/0510/11/05
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint

Dive into the research topics of 'Fast algorithms for IR drop analysis in large power grid'. Together they form a unique fingerprint.

Cite this