Title :
PowerRush: A linear simulator for power grid
Author :
Yang, Jianlei ; Li, Zuowei ; Cai, Yici ; Zhou, Qiang
Author_Institution :
Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing, China
Abstract :
As the increasing size of power grids, IR drop analysis has become more computationally challenging both in runtime and memory consumption. In this paper, we propose a linear complexity simulator named PowerRush, which consists of an efficient SPICE Parser, a robust circuit Builder and a linear solver. The proposed solver is a pure algebraic method which can provide an optimal convergence without geometric information. It is implemented by Algebraic Multigrid Preconditioned Conjugate Gradient method, in which an aggregation based algebraic multigrid with K-Cycle acceleration is adopted as a preconditioner to improve the robustness of conjugate gradient iterative method. In multigrid scheme, double pairwise aggregation technique is applied to the matrix graph in coarsening procedure to ensure low setup cost and memory requirement. Further, a K-Cycle multigrid scheme is adopted to provide Krylov subspace acceleration at each level to guarantee optimal or near optimal convergence. Experimental results on real power grids have shown that PowerRush has a linear complexity in runtime cost and memory consumption. The DC analysis of a 60 Million nodes power grid can be solved by PowerRush for 0.01mV accuracy in 170 seconds with 21.89GB memory used.
Keywords :
algebra; conjugate gradient methods; iterative methods; power grids; IR drop analysis; K-cycle acceleration; PowerRush; SPICE parser; algebraic multigrid preconditioned conjugate gradient method; complexity simulator; conjugate gradient iterative method; double pairwise aggregation technique; linear simulator; power grid; robust circuit builder; Acceleration; Benchmark testing; Complexity theory; Convergence; Power grids; Robustness; Symmetric matrices; Aggregation; Algebraic Multigrid; K-Cycle; Power Grid; PowerRush;
Conference_Titel :
Computer-Aided Design (ICCAD), 2011 IEEE/ACM International Conference on
Conference_Location :
San Jose, CA
Print_ISBN :
978-1-4577-1399-6
Electronic_ISBN :
1092-3152
DOI :
10.1109/ICCAD.2011.6105372