Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid

Yu Zhong, Martin D F Wong

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

Abstract

Due to the extremely large sizes of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. In order to design scalable algorithms to handle ever increasing power-grid sizes, the most promising approach is to use a "divide-and- conquer" strategy such as domain decomposition. Such an approach not only decomposes a large problem into manageable sub-problems, it also naturally allow a parallel processing solution for further speedup in computation time. As a result, a power-grid analysis algorithm based upon the traditional domain decomposition method has been reported in [9]. Unfortunately, the method in [9] has strong limitation on the size of the interfaces between the sub-problems and therefore severely limits its capability in solving very large problems. In this paper, we present a block-iterative domain-decomposition algorithm which effectively combines the advantages of direct solvers and iterative methods. With a carefully chosen domain decomposition strategy, our approach does not suffer from the difficulties of [9]. While the algorithm in [9] fails to analyze a power grid of 4 millions nodes, our algorithm solves a power grid of 42 millions nodes accurately in 1.5 hours.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010
Pages277-283
Number of pages7
DOIs
StatePublished - May 28 2010
Event11th International Symposium on Quality Electronic Design, ISQED 2010 - San Jose, CA, United States
Duration: Mar 22 2010Mar 24 2010

Publication series

NameProceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010

Other

Other11th International Symposium on Quality Electronic Design, ISQED 2010
Country/TerritoryUnited States
CitySan Jose, CA
Period3/22/103/24/10

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid'. Together they form a unique fingerprint.

Cite this