More Web Proxy on the site http://driver.im/

research-article

ESPSim: An Efficient Scalable Power Grid Simulator Based on Parallel Algebraic Multigrid

Authors:

Xuan ZengAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems, Volume 28, Issue 1

Article No.: 5, Pages 1 - 31

https://doi.org/10.1145/3529533

Published: 10 December 2022 Publication History

Abstract

Fast verification for the extremely large-scale power grid is demanding as CMOS technology advances consistently. In this work, we propose ESPSim, an efficient scalable power grid simulator based on a parallel smoothed aggregation-based algebraic multigrid technique. ESPSim has the ability to do fast DC and transient analysis through MPI and adaptive timestep control mechanism. Thanks to the smoother applied on the prolongation operator, ESPSim copes well with the convergence rate on extremely large-scale power grid transient analysis. Extensive experiments are conducted with a variety of serial/parallel solvers. The runtime of ESPSim is linear with case size. With 16 processors, 1,000 timesteps transient analysis of 63.4M nodes can be completed in 22.1 min. Over 22× speedup compared to the well-known direct solver Cholmod is observed.

References

[1]

Check Memory. 2021. Checking Memory from a Parallel C Program. Retrieved from https://hpcf.umbc.edu/general-productivity/checking-memory-usage/.

[2]

Hypre User Guide. 2021. Hypre Software and Documentation. Retrieved from https://computing.llnl.gov/projects/hypre-scalable-linear-solvers-multigrid-methods.

[3]

xxHash User Guide. 2021. xxHash. Retrieved from https://github.com/Cyan4973/xxHash.

[4]

Parmetis User Guide. 2022. Parmetis Manual Version 4.0. Retrieved from http://glaros.dtc.umn.edu/gkhome/metis/parmetis/overview.

[5]

Ramachandra Achar, Michel S. Nakhla, Harjot S. Dhindsa, Arvind R. Sridhar, Douglas Paul, and Natalie M. Nakhla. 2011. Parallel and scalable transient simulator for power grids via waveform relaxation (PTS-PWR). IEEE Trans. Very Large Scale Integr. Syst. 19, 2 (2011), 319–332.

Digital Library

[6]

Andreas Adelmann, Peter Arbenz, and Yves Ineichen. 2010. Improvements of a fast parallel poisson solver on irregular domains. In Proceedings of the 10th International Conference on Applied Parallel and Scientific Computing (PARA’10)(Lecture Notes in Computer Science, Vol. 7133), Kristján Jónasson (Ed.). Springer, 65–74.

Digital Library

[7]

Satish Balay, Shrirang Abhyankar, Mark F. Adams, Steven Benson, Jed Brown, Peter Brune, Kris Buschelman, Emil M. Constantinescu, Lisandro Dalcin, Alp Dener, Victor Eijkhout, William D. Gropp, Václav Hapla, Tobin Isaac, Pierre Jolivet, Dmitry Karpeev, Dinesh Kaushik, Matthew G. Knepley, Fande Kong, Scott Kruger, Dave A. May, Lois Curfman McInnes, Richard Tran Mills, Lawrence Mitchell, Todd Munson, Jose E. Roman, Karl Rupp, Patrick Sanan, Jason Sarich, Barry F. Smith, Stefano Zampini, Hong Zhang, Hong Zhang, and Junchao Zhang. 2021. PETSc Web Page. Retrieved from https://petsc.org/.

[8]

Marian Brezina, Robert D. Falgout, Scott MacLachlan, Thomas A. Manteuffel, Stephen F. McCormick, and John W. Ruge. 2004. Adaptive smoothed aggregation (\(\alpha\)SA). SIAM J. Sci. Comput. 25, 6 (2004), 1896–1920.

Digital Library

[9]

William L. Briggs, Van Emden Henson, and Stephen F. McCormick. 2000. A Multigrid Tutorial, 2nd ed. SIAM.

[10]

Yici Cai, Jin Shi, Zhu Pan, Xianlong Hong, and Sheldon X.-D. Tan. 2008. Large scale P/G grid transient simulation using hierarchical relaxed approach. Integration 41, 1 (2008), 153–160.

Digital Library

[11]

Tsung-Hao Chen and Charlie Chung-Ping Chen. 2001. Efficient large-scale power grid analysis based on preconditioned Krylov-subspace iterative methods. In Proceedings of the 38th Design Automation Conference. 559–562.

[12]

Yanqing Chen, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. 2008. Algorithm 887: CHOLMOD, supernodal sparse cholesky factorization and update/downdate. ACM Trans. Math. Softw. 35, 3 (2008), 22:1–22:14.

Digital Library

[13]

Ganqu Cui, Wenjian Yu, Xin Li, Zhiyu Zeng, and Ben Gu. 2019. Machine-learning-driven matrix ordering for power grid analysis. In Proceedings of the Design, Automation Test in Europe Conference Exhibition (DATE’19). 984–987.

[14]

Timothy A. Davis. [n.d.]. SuiteSparse. Retrieved from https://people.engr.tamu.edu/davis/suitesparse.html.

[15]

Hans De Sterck, Robert D. Falgout, Joshua W. Nolting, and Ulrike Meier Yang. 2008. Distance-two interpolation for parallel algebraic multigrid. Numer. Linear Algebra Appl. 15, 2–3 (2008), 115–139.

[16]

Hans De Sterck, Ulrike Meier Yang, and Jeffrey J. Heys. 2006. Reducing complexity in parallel algebraic multigrid preconditioners. SIAM J. Matrix Anal. Appl. 27, 4 (2006), 1019–1039.

Digital Library

[17]

D. Demidov. 2019. AMGCL: An efficient, flexible, and extensible algebraic multigrid implementation. Lobachevskii J. Math. 40, 5 (May2019), 535–546.

[18]

James Demmel. 1997. Applied Numerical Linear Algebra. SIAM.

[19]

Zhuo Feng and Peng Li. 2008. Multigrid on GPU: Tackling power grid analysis on parallel SIMT platforms. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 647–654.

[20]

Laura Grigori, James Demmel, and Xiaoye S. Li. 2007. Parallel symbolic factorization for sparse LU with static pivoting. SIAM J. Sci. Comput. 29, 3 (2007), 1289–1314.

[21]

Zhuang Hao. 2016. Exponential Time Integration for Transient Analysis of Large-Scale Circuits. Ph.D. Dissertation. Department of Computer Science, University of California, San Diego, CA. Retrieved from https://escholarship.org/uc/item/60d8c2r6.

[22]

Qing He, William Au, Alexander Korobkov, and Subramanian Venkateswaran. 2014. Parallel power grid analysis using distributed direct linear solver. In Proceedings of the IEEE International Symposium on Electromagnetic Compatibility (EMC’14). 866–871.

[23]

Magnus R. Hestenes, Eduard Stiefel, et al. 1952. Methods of conjugate gradients for solving linear systems. J. Res. Natl. Bureau Stand. 49, 6 (1952), 409–436.

[24]

R. M. Kielkowski. 1998. Inside SPICE. McGraw-Hill.

Digital Library

[25]

Zhang Le. 2015. Parallel simulation for VLSI power grid. Ph.D. Dissertation. the Department of Computer Science & Engineering, Texas A&M University.

[26]

Yu-Min Lee and C. C.-P. Chen. 2002. Power grid transient simulation in linear time based on transmission-line-modeling alternating-direction-implicit method. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 21, 11 (2002), 1343–1352.

Digital Library

[27]

Yu-Min Lee and Chia-Tung Ho. 2017. InTraSim: Incremental transient simulation of power grids. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 36, 12 (2017), 2052–2065.

[28]

P. Li. 2021. IBM Power Grid Benchmarks. Retrieved from https://web.ece.ucsb.edu/lip/PGBenchmarks/ibmpgbench.html.

[29]

Calvin Lin and Lawrence Snyder. 2008. Principles of Parallel Programming. Pearson.

Digital Library

[30]

Zhiqiang Liu, Wenjian Yu, and Zhuo Feng. 2021. feGRASS: Fast and effective graph spectral sparsification for scalable power grid analysis. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. (2021), 1–1.

[31]

S. R. Nassif and J. N. Kozhaya. 2000. Fast power grid simulation. In Proceedings of the 37th Design Automation Conference. 156–161.

Digital Library

[32]

Y. Notay. 2010. An aggregation-based algebraic multigrid method. Electr. Trans. Numer. Anal. 37 (2010), 123–146.

[33]

Yvan Notay. 2021. AGMG Software and Documentation Documentation. Retrieved from http://homepages.ulb.ac.be/ynotay/AGMG.

[34]

Yvan Notay and Artem Napov. 2015. A massively parallel solver for discrete Poisson-like problems. J. Comput. Phys. 281 (2015), 237–250.

Digital Library

[35]

Zhu Pan, Yici Cai, S. X.-D. Tan, Zuying Luo, and Xianlong Hong. 2004. Transient analysis of on-chip power distribution networks using equivalent circuit modeling. In Proceedings of the International Symposium on Signals, Circuits and Systems (SCS’03). 63–68.

[36]

Haifeng Qian, S. R. Nassif, and S. S. Sapatnekar. 2005. Power grid analysis using random walks. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 24, 8 (2005), 1204–1224.

Digital Library

[37]

Yousef Saad. 2003. Iterative Methods for Sparse Linear Systems. SIAM.

[38]

Robert Sedgewick and Kevin Wayne. 2014. Algorithms, Part I, 4th ed. Pearson Education.

[39]

Kai Sun, Quming Zhou, Kartik Mohanram, and Danny C. Sorensen. 2007. Parallel domain decomposition for simulation of large-scale power grids. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 54–59.

[40]

Petr Vanek, Marian Brezina, and Jan Mandel. 2001. Convergence of algebraic multigrid based on smoothed aggregation. Numer. Math. 88, 3 (2001), 559–579.

[41]

P. Vaněk, J. Mandel, and M. Brezina. 1996. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 3 (Sep.1996), 179–196.

[42]

Jia Wang and Xuanxing Xiong. 2013. Scalable power grid transient analysis via MOR-assisted time-domain simulations. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’13). 548–552.

[43]

R. Webster. 2001. Performance of algebraic multi-grid solvers based on unsmoothed and smoothed aggregation schemes. Int. J. Numer. Methods Fluids 36, 7 (2001), 743–772.

[44]

J. Yang and Z. Li. 2021. THU Power Grid Benchmarks. Retrieved from http://tiger.cs.tsinghua.edu.cn/PGBench/.

[45]

Jianlei Yang, Zuowei Li, Yici Cai, and Qiang Zhou. 2012. PowerRush: Efficient transient simulation for power grid analysis. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’12). 653–659.

Digital Library

[46]

Jianlei Yang, Zuowei Li, Yici Cai, and Qiang Zhou. 2014. PowerRush: An efficient simulator for static power grid analysis. IEEE Trans. Very Large Scale Integr. Syst. 22, 10 (2014), 2103–2116.

[47]

Ting Yu and Martin. D. F. Wong. 2012. PGT_SOLVER: An efficient solver for power grid transient analysis. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD’12). 647–652.

Digital Library

[48]

Ting Yu, Zigang Xiao, and Martin D. F. Wong. 2012. Efficient parallel power grid analysis via additive Schwarz method. In Proceedings of the International Conference on Computer-Aided Design (ICCAD’12). ACM, New York, NY, 399–406.

Digital Library

[49]

Le Zhang and Vivek Sarin. 2016. Parallel power grid analysis based on enlarged partitions. ACM Trans. Design Autom. Electr. Syst. 21, 2 (2016), 26:1–26:21.

Digital Library

[50]

Liu Zhiqiang and Yu Wenjian. 2021. pGRASS-Solver: A parallel iterative solver for scalable power grid analysis based on graph spectral sparsification. Retrieved from https://numbda.cs.tsinghua.edu.cn/papers/iccad21_2.pdf.

[51]

Zhengyong Zhu, Bo Yao, and Chug-Kuan Cheng. 2003. Power network analysis using an adaptive algebraic multigrid approach. In Proceedings of the Design Automation Conference (DAC’03). 105–108.

[52]

Hao Zhuang, Shih-Hung Weng, Jeng-Hau Lin, and Chung-Kuan Cheng. 2014. MATEX: A distributed framework for transient simulation of power distribution networks. In Proceedings of the 51st Annual Design Automation Conference (DAC’14). ACM, New York, NY, 1–6.

Digital Library

[53]

Hao Zhuang, Wenjian Yu, Ilgweon Kang, Xinan Wang, and Chung-Kuan Cheng. 2015. An algorithmic framework for efficient large-scale circuit simulation using exponential integrators. In Proceedings of the 52nd ACM/EDAC/IEEE Design Automation Conference (DAC’15). 1–6.

Digital Library

[54]

Cheng Zhuo, Jiang Hu, Min Zhao, and Kangsheng Chen. 2008. Power grid analysis and optimization using algebraic multigrid. IEEE Trans. Comput.-Aided Design Integr. Circ. Syst. 27, 4 (2008), 738–751.

Digital Library

Cited By

Li PZuo YSun YYan HShi LAmrouch HHu JGarg SLin Y(2024)ICDaIR: Distribution-aware Static IR Drop Prediction Flow Based on Image ClassificationProceedings of the 2024 ACM/IEEE International Symposium on Machine Learning for CAD10.1145/3670474.3685942(1-6)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3670474.3685942
liu wMa TGuan Z(2024)The fast power grid static analysis algorithm based on matrix reorderingThird International Conference on Electronic Information Engineering, Big Data, and Computer Technology (EIBDCT 2024)10.1117/12.3031252(239)Online publication date: 19-Jul-2024
https://doi.org/10.1117/12.3031252
Liu ZYu W(2024)Randomized Cholesky Factorization With Threshold-Based Multisampling for Power Grid SimulationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.338107643:9(2687-2691)Online publication date: Sep-2024
https://doi.org/10.1109/TCAD.2024.3381076
Show More Cited By

Index Terms

ESPSim: An Efficient Scalable Power Grid Simulator Based on Parallel Algebraic Multigrid

Recommendations

Parallel and scalable transient simulator for power grids via waveform relaxation (PTS-PWR)

This paper presents a fast algorithm for transient simulation of power grids in very large scale integration systems using waveform relaxation (WR) techniques. Novel partitioning methods and convergence accelerators are developed for fast convergence of ...
Parallel forward and back substitution for efficient power grid simulation
ICCAD '12: Proceedings of the International Conference on Computer-Aided Design

Parallelizing power grid simulation with factorization-based direct or preconditioned iterative methods is a challenging task due to the data dependency among forward and back substitution. In this paper, we propose two approaches to parallelize forward ...
Power grid reduction based on algebraic multigrid principles
DAC '03: Proceedings of the 40th annual Design Automation Conference

With the scaling of technology, power grid noise is becoming increasingly significant for circuit performance. A typical power grid circuit contains millions of linear elements, making noise analysis and verification challenging in terms of both run ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 28, Issue 1

January 2023

321 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/3573313

Editor:
X. Sharon Hu
University of Notre Dame, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 10 December 2022

Online AM: 19 May 2022

Accepted: 29 March 2022

Revised: 21 February 2022

Received: 11 September 2021

Published in TODAES Volume 28, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Funding Sources

National Key R&D Program of China
National Natural Science Foundation of China (NSFC)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
356
Total Downloads

Downloads (Last 12 months)97
Downloads (Last 6 weeks)14

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Li PZuo YSun YYan HShi LAmrouch HHu JGarg SLin Y(2024)ICDaIR: Distribution-aware Static IR Drop Prediction Flow Based on Image ClassificationProceedings of the 2024 ACM/IEEE International Symposium on Machine Learning for CAD10.1145/3670474.3685942(1-6)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3670474.3685942
liu wMa TGuan Z(2024)The fast power grid static analysis algorithm based on matrix reorderingThird International Conference on Electronic Information Engineering, Big Data, and Computer Technology (EIBDCT 2024)10.1117/12.3031252(239)Online publication date: 19-Jul-2024
https://doi.org/10.1117/12.3031252
Liu ZYu W(2024)Randomized Cholesky Factorization With Threshold-Based Multisampling for Power Grid SimulationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.338107643:9(2687-2691)Online publication date: Sep-2024
https://doi.org/10.1109/TCAD.2024.3381076
Li PZuo YSun YYan HShi L(2024)ICDaIR: Distribution-aware Static IR Drop Prediction Flow Based on Image Classification2024 ACM/IEEE 6th Symposium on Machine Learning for CAD (MLCAD)10.1109/MLCAD62225.2024.10740244(1-6)Online publication date: 9-Sep-2024
https://doi.org/10.1109/MLCAD62225.2024.10740244
Jiang YSong JYang XDong XSun SLin YJin ZYin XZhuo C(2024)A Parallel Simulation Framework Incorporating Machine Learning-Based Hotspot Detection for Accelerated Power Grid Analysis2024 ACM/IEEE 6th Symposium on Machine Learning for CAD (MLCAD)10.1109/MLCAD62225.2024.10740202(1-7)Online publication date: 9-Sep-2024
https://doi.org/10.1109/MLCAD62225.2024.10740202
Shen SLiu ZYu W(2024)SRAM-PG: Power Delivery Network Benchmarks from SRAM Circuits2024 25th International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED60706.2024.10528743(1-7)Online publication date: 3-Apr-2024
https://doi.org/10.1109/ISQED60706.2024.10528743
Li CAn CGao ZYang FSu YZeng X(2023)Unleashing the Power of Graph Spectral Sparsification for Power Grid Analysis via Incomplete Cholesky FactorizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.323884142:9(3053-3066)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3238841
Liu ZYu W(2023)pGRASS-Solver: A Graph Spectral Sparsification-Based Parallel Iterative Solver for Large-Scale Power Grid AnalysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2023.323575442:9(3031-3044)Online publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1109/TCAD.2023.3235754
Chen QLi MYan HShi L(2023)Efficient Improvements of Domain Decomposition Method for Power Grid Transient Simulation2023 International Symposium of Electronics Design Automation (ISEDA)10.1109/ISEDA59274.2023.10218650(1-4)Online publication date: 8-May-2023
https://doi.org/10.1109/ISEDA59274.2023.10218650
An CLi CLi XSu YYang FZeng X(2023)FPDsim: A Structural Simulator For Power Grid Analysis Of Flat Panel Display2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247770(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247770

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents