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
CountryUnited 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