面向矩阵指数积分瞬态电路仿真的加速方法

随着现代集成电路的发展，越来越复杂的设计和不断迭代的先进技术节点使 得集成电路规模呈指数级增长，利用传统积分方法进行瞬态电路仿真的时间已经 逐渐增加到难以接受的程度。为加速大规模瞬态电路仿真，矩阵指数积分方法在 近年来被广泛研究，本文提出了三种面向矩阵指数积分瞬态电路仿真的加速方法。 在第一种方法中，由于矩阵指数积分方法精度更高，仿真步长更大，可能会导致 忽略一些波形细节，因此我们提出矩阵指数积分的步长缩放方法，用于以非常小 的计算开销得到部分时间点的解，实现快速补全波形细节。在第二种加速方法中， 由于在大规模电源地网络瞬态电路仿真中存在大量不对齐输入源导致过多的线性 转折点，而不能充分发挥矩阵指数积分方法精度高，仿真步长更大的优势，因此 我们先证明了矩阵指数积分与模型降阶方法的等价性，并提出一种混合加速方法， 将所有输入源分到矩阵指数积分和模型降阶方法中分别进行仿真，再将两者的结 果叠加到一起，该过程中会利用步长缩放方法对矩阵指数积分中的部分时间点进 行求解，从而实现了矩阵指数积分方法对大规模电源地网络瞬态电路仿真的加速。 在第三种加速方法中，我们先分析了大规模线性方程组中的三角求解会占比矩阵 指数积分瞬态电路仿真的大部分时间，基于现有求解器只并行加速 LU 分解阶段 而忽视对三角求解阶段的并行加速，我们提出了边界块对角矩阵重排序算法，实 现对三角求解阶段的并行加速，从而实现矩阵指数积分瞬态电路仿真的并行加速。 最后我们对这三种加速方法都进行了实验验证，文章中数值实验的结果也证实了 这三种加速方法的有效性。

[1] MACMILLEN D, CAMPOSANO R, HILL D, et al. An industrial view of electronic designautomation[J/OL]. IEEE Transactions on Computer-Aided Design of Integrated Circuits andSystems, 2000, 19(12): 1428-1448. DOI: 10.1109/43.898825.
[2] NAGEL L W, PEDERSON D. SPICE (Simulation Program with Integrated Circuit Emphasis):UCB/ERL M382[R/OL]. EECS Department, University of California, Berkeley, 1973. http://www2.eecs.berkeley.edu/Pubs/TechRpts/1973/22871.html.
[3] WENG S H, CHEN Q, CHENG C K. Time-domain analysis of large-scale circuits by matrixexponential method with adaptive control[J]. IEEE Transactions on Computer-Aided Designof Integrated Circuits and Systems, 2012, 31(8): 1180-1193.
[4] ZHU Z, ROUZ K, BORAH M, et al. Efficient transient simulation for transistor-level analysis[C]//Proceedings of the 2005 Asia and South Pacific Design Automation Conference. 2005:240-243.
[5] DONG W, LI P. Parallelizable stable explicit numerical integration for efficient circuit simulation[C]//Proceedings of the 46th Annual Design Automation Conference. 2009: 382-385.
[6] PILLAGE L. Electronic Circuit & System Simulation Methods (SRE)[M]. McGraw-Hill, Inc.,1998.
[7] CHEN Q. EI-NK: A Robust Exponential Integrator Method With Singularity Removal andNewton–Raphson Iterations for Transient Nonlinear Circuit Simulation[J/OL]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41(6): 1693-1703.DOI: 10.1109/TCAD.2021.3098749.
[8] ZHUANG H, WENG S H, CHENG C K. Power grid simulation using matrix exponentialmethod with rational Krylov subspaces[C]//2013 IEEE 10th International Conference on ASIC.IEEE, 2013: 1-4.
[9] ZHUANG H, YU W, KANG I, et al. An algorithmic framework for efficient large-scale circuitsimulation using exponential integrators[C]//Proceedings of the 52nd Annual Design Automation Conference. 2015: 1-6.
[10] CHEN P, CHENG C K, PARK D, et al. Transient circuit simulation for differential algebraicsystems using matrix exponential[C]//2018 IEEE/ACM International Conference on ComputerAided Design (ICCAD). IEEE, 2018: 1-6.
[11] ZHUANG H, WENG S H, LIN J H, et al. MATEX: A distributed framework for transient simulation of power distribution networks[C]//2014 51st ACM/EDAC/IEEE Design AutomationConference (DAC). 2014: 1-6.
[12] MOLER C, VAN LOAN C. Nineteen Dubious Ways to Compute the Exponential of a Matrix,Twenty-Five Years Later[J/OL]. SIAM Review, 2003, 45(1): 3-49. DOI: 10.1137/S00361445024180.51参考文献
[13] SAAD Y. Analysis of Some Krylov Subspace Approximations to the Matrix Exponential Operator[J/OL]. SIAM Journal on Numerical Analysis, 1992, 29(1): 209-228. DOI:10.1137/0729014.
[14] SCHENK O, GäRTNER K, FICHTNER W, et al. PARDISO: a high-performance serial andparallel sparse linear solver in semiconductor device simulation[J/OL]. Future Generation Computer Systems, 2001, 18(1): 69-78. https://www.sciencedirect.com/science/article/pii/S0167739X00000765. DOI: https://doi.org/10.1016/S0167-739X(00)00076-5.
[15] DAVIS T A. Algorithm 832: UMFPACK V4.3—an unsymmetric-pattern multifrontal method[J/OL]. ACM Trans. Math. Softw., 2004, 30(2): 196–199. https://doi.org/10.1145/992200.992206.
[16] AMESTOY P R, DUFF I S, L’EXCELLENT J Y, et al. MUMPS: a general purpose distributedmemory sparse solver[C]//International Workshop on Applied Parallel Computing. Springer,2000: 121-130.
[17] LI X S. An overview of SuperLU: Algorithms, implementation, and user interface[J/OL]. ACMTrans. Math. Softw., 2005, 31(3): 302–325. https://doi.org/10.1145/1089014.1089017.
[18] DAVIS T A, PALAMADAI NATARAJAN E. Algorithm 907: KLU, A Direct Sparse Solverfor Circuit Simulation Problems[J/OL]. ACM Trans. Math. Softw., 2010, 37(3). https://doi.org/10.1145/1824801.1824814.
[19] CHEN X. Numerically-Stable and Highly-Scalable Parallel LU Factorization for Circuit Simulation[C]//2022 IEEE/ACM International Conference On Computer Aided Design (ICCAD).2022: 1-9.
[20] CHEN X. Numerically-Stable and Highly-Scalable Parallel LU Factorization for Circuit Simulation[C/OL]//ICCAD ’22: Proceedings of the 41st IEEE/ACM International Conference onComputer-Aided Design. New York, NY, USA: Association for Computing Machinery, 2022.https://doi.org/10.1145/3508352.3549337.
[21] HO C W, RUEHLI A, BRENNAN P. The modified nodal approach to network analysis[J/OL].IEEE Transactions on Circuits and Systems, 1975, 22(6): 504-509. DOI: 10.1109/TCS.1975.1084079.
[22] AMESTOY P R, DAVIS T A, DUFF I S. An Approximate Minimum Degree Ordering Algorithm[J/OL]. SIAM Journal on Matrix Analysis and Applications, 1996, 17(4): 886-905.https://doi.org/10.1137/S0895479894278952.
[23] NIESEN J, WRIGHT W M. Algorithm 919: A Krylov Subspace Algorithm for Evaluating theϕ-Functions Appearing in Exponential Integrators[J/OL]. ACM Trans. Math. Softw., 2012, 38(3). https://doi.org/10.1145/2168773.2168781.
[24] AL-MOHY A H, HIGHAM N J. Computing the Action of the Matrix Exponential, with anApplication to Exponential Integrators[J/OL]. SIAM Journal on Scientific Computing, 2011,33(2): 488-511. DOI: 10.1137/100788860.
[25] GÖCKLER T, GRIMM V. CONVERGENCE ANALYSIS OF AN EXTENDED KRYLOVSUBSPACE METHOD FOR THE APPROXIMATION OF OPERATOR FUNCTIONS INEXPONENTIAL INTEGRATORS[J/OL]. SIAM Journal on Numerical Analysis, 2013, 51(4): 2189-2213
[2024-02-28]. http://www.jstor.org/stable/42004070.52参考文献
[26] HIGHAM N J. The Scaling and Squaring Method for the Matrix Exponential Revisited[J/OL].SIAM Journal on Matrix Analysis and Applications, 2005, 26(4): 1179-1193. DOI: 10.1137/04061101X.
[27] ZHUANG H, YU W, WENG S H, et al. Simulation algorithms with exponential integrationfor time-domain analysis of large-scale power delivery networks[J]. IEEE Transactions onComputer-Aided Design of Integrated Circuits and Systems, 2016, 35(10): 1681-1694.
[28] CHEN Q, WENG S H, CHENG C K. A practical regularization technique for modified nodalanalysis in large-scale time-domain circuit simulation[J]. IEEE Transactions on ComputerAided Design of Integrated Circuits and Systems, 2012, 31(7): 1031-1040.
[29] ROMMES J, MARTINS N. Exploiting structure in large-scale electrical circuit and powersystem problems[J/OL]. Linear Algebra and its Applications, 2009, 431(3): 318-333. https://www.sciencedirect.com/science/article/pii/S0024379509000184. DOI: https://doi.org/10.1016/j.laa.2008.12.027.
[30] ODABASIOGLU A, CELIK M, PILEGGI L. PRIMA: passive reduced-order interconnectmacromodeling algorithm[J/OL]. IEEE Transactions on Computer-Aided Design of IntegratedCircuits and Systems, 1998, 17(8): 645-654. DOI: 10.1109/43.712097.
[31] CHEN X. Parallel performance[EB/OL]. 2023. https://github.com/chenxm1986/cktso/issues/12.
[32] DUFF I S, KOSTER J. On Algorithms For Permuting Large Entries to the Diagonal of a SparseMatrix[J/OL]. SIAM Journal on Matrix Analysis and Applications, 2001, 22(4): 973-996.https://doi.org/10.1137/S0895479899358443.
[33] KARYPIS G, KUMAR V. METIS—A Software Package for Partitioning Unstructured Graphs,Partitioning Meshes and Computing Fill-Reducing Ordering of Sparse Matrices[Z]. 1997.
[34] CHANDRA R, DAGUM L, KOHR D, et al. Parallel programming in OpenMP[M]. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2001.
[35] GROPP W, LUSK E, SKJELLUM A. Using MPI: Portable Parallel Programming with theMessage-Passing Interface[M]. The MIT Press, 2014.
[36] NASSIF S R. Power grid analysis benchmarks[C/OL]//2008 Asia and South Pacific DesignAutomation Conference. 2008: 376-381. DOI: 10.1109/ASPDAC.2008.4483978.
[37] Ahkab: an open-source SPICE-like interactive circuit simulator[EB/OL]. https://ahkab.readthedocs.io/en/latest/