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
Y1 - 2010
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
T2 - 11th International Symposium on Quality Electronic Design, ISQED 2010
Y2 - 22 March 2010 through 24 March 2010
ER -