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

Fingerprint

Decomposition
Domain decomposition methods
Iterative methods
Data storage equipment
Processing

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Zhong, Y., & Wong, M. D. F. (2010). Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid. In Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010 (pp. 277-283). [5450430] (Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010). https://doi.org/10.1109/ISQED.2010.5450430

Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid. / Zhong, Yu; Wong, Martin D F.

Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010. 2010. p. 277-283 5450430 (Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010).

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

Zhong, Y & Wong, MDF 2010, Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid. in Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010., 5450430, Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010, pp. 277-283, 11th International Symposium on Quality Electronic Design, ISQED 2010, San Jose, CA, United States, 3/22/10. https://doi.org/10.1109/ISQED.2010.5450430
Zhong Y, Wong MDF. Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid. In Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010. 2010. p. 277-283. 5450430. (Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010). https://doi.org/10.1109/ISQED.2010.5450430
Zhong, Yu ; Wong, Martin D F. / Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid. Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010. 2010. pp. 277-283 (Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010).
@inproceedings{2fb45f1e861244339cf2fb6c0140102e,
title = "Fast block-iterative domain decomposition algorithm for IR drop analysis in large power grid",
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.",
author = "Yu Zhong and Wong, {Martin D F}",
year = "2010",
month = "5",
day = "28",
doi = "10.1109/ISQED.2010.5450430",
language = "English (US)",
isbn = "9781424464555",
series = "Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010",
pages = "277--283",
booktitle = "Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010",

}

TY - GEN

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

AU - Zhong, Yu

AU - Wong, Martin D F

PY - 2010/5/28

Y1 - 2010/5/28

N2 - 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.

AB - 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.

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

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

U2 - 10.1109/ISQED.2010.5450430

DO - 10.1109/ISQED.2010.5450430

M3 - Conference contribution

AN - SCOPUS:77952654671

SN - 9781424464555

T3 - Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010

SP - 277

EP - 283

BT - Proceedings of the 11th International Symposium on Quality Electronic Design, ISQED 2010

ER -