求解电路方程组的改进分块对角加边方法
Improved Bordered Block Diagonal Method for Solving Circuit Equation Systems
摘要: 针对电路仿真中瞬态分析底层产生的超大规模稀疏线性方程组的求解，分块对角加边(Bordered Block Diagonal, BBD)方法是一类经典的方法。本文提出了一种改进的BBD方法，通过在边界分解时引入以列为基础单位的动态并行分解，缓解了经典BBD方法中线程负载不均的问题，同时增强了并行性。使用8个电路方程的矩阵进行了数值实验，实验结果显示对于测试矩阵的LU分解速度，本文提出的改进方法在2线程和8线程情况下相比经典BBD方法均有一定的提升。
Abstract: The Bordered Block Diagonal (BBD) method is a classic approach for solving the large and sparse linear equation systems generated at the bottom level in transient analysis of circuits simulation. In this paper, an improved BBD method is proposed, which introduces a fine-grained parallel decomposition based on columns during the boundary decomposition to alleviate the issue of uneven thread workload in the classical BBD method, while enhancing parallelism. Numerical experiments were conducted using a matrix of 8 circuit equations, and the results show that the proposed improvement method achieves a certain speedup in LU decomposition for the test matrix compared to the classical BBD method when using 2-thread and 8-thread scenarios.
文章引用：陈炳旭. 求解电路方程组的改进分块对角加边方法[J]. 运筹与模糊学, 2024, 14(3): 102-108. https://doi.org/10.12677/orf.2024.143249

参考文献

[1] Nagel, L.W. and Pederson, D.O. (1973) SPICE (Simulation Program with Integrated Circuit Emphasis). Memo No. ERL-M382, Electronics Research Laboratory, University of California, Berkeley.
[2] Li, P. (2012) Parallel Circuit Simulation: A Historical Perspective and Recent Developments. Foundations and Trends® in Electronic Design Automation, 5, 211-318. [Google Scholar] [CrossRef] 
[3] Thornquist, H.K. and Rajamanickam, S. (2014) A Hybrid Approach for Parallel Transistor-Level Full-Chip Circuit Simulation. In: International Conference on High Performance Computing for Computational Science, Springer International Publishing, 102-111. [Google Scholar] [CrossRef] 
[4] Bollhöfer, M., Schenk, O., Janalik, R., Hamm, S. and Gullapalli, K. (2020) State-of-the-Art Sparse Direct Solvers. In: Parallel Algorithms in Computational Science and Engineering, Birkhäuser, 3-33. [Google Scholar] [CrossRef] 
[5] Chan, K.W. (2001) Parallel Algorithms for Direct Solution of Large Sparse Power System Matrix Equations. IEE Proceedings—Generation, Transmission and Distribution, 148, 615-622. [Google Scholar] [CrossRef] 
[6] Zecevic, A.I. and Siljak, D.D. (1994) Balanced Decompositions of Sparse Systems for Multilevel Parallel Processing. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 41, 220-233. [Google Scholar] [CrossRef] 
[7] Duff, I.S. and Scott, J.A. (2005) Stabilized Bordered Block Diagonal Forms for Parallel Sparse Solvers. Parallel Computing, 31, 275-289. [Google Scholar] [CrossRef] 
[8] Rajamanickam, S., Boman, E.G. and Heroux, M.A. (2012) ShyLU: A Hybrid-Hybrid Solver for Multicore Platforms. 2012 IEEE 26th International Parallel and Distributed Processing Symposium, Shanghai, 21-25 May 2012, 631-643. [Google Scholar] [CrossRef] 
[9] Li, L., Liu, Z., Liu, K., Shen, S. and Yu, W. (2023) Parallel Incomplete LU Factorization Based Iterative Solver for Fixed-Structure Linear Equations in Circuit Simulation. Proceedings of the 28th Asia and South Pacific Design Automation Conference, 339-345. [Google Scholar] [CrossRef] 
[10] Gilbert, J.R. and Peierls, T. (1988) Sparse Partial Pivoting in Time Proportional to Arithmetic Operations. SIAM Journal on Scientific and Statistical Computing, 9, 862-874. [Google Scholar] [CrossRef] 

为你推荐