Fast algorithms for IR drop analysis in large power grid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 (US)
Title of host publicationProceedings of theICCAD-2005
Subtitle of host publicationInternational Conference on Computer-Aided Design
Pages351-357
Number of pages7
DOIs
StatePublished - 2005
EventICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005 - San Jose, CA, United States
Duration: Nov 6 2005Nov 10 2005

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
Volume2005
ISSN (Print)1092-3152

Other

OtherICCAD-2005: IEEE/ACM International Conference on Computer-Aided Design, 2005
CountryUnited States
CitySan Jose, CA
Period11/6/0511/10/05

ASJC 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