论文部分内容阅读
随着电子科学技术的发展,为设计高质量的电路,电路模拟必不可少。在电路模拟的过程中要涉及到稀疏线性方程组的求解。而随着电路矩阵规模的不断增大,对电路矩阵的求解已经成为电路模拟过程的一个瓶颈。针对电路模拟过程中产生的电路矩阵的特点,通常均采用直接法来进行此类线性方程组的求解。目前常用的求解器有sparse 1.3、superLU、KLU,其中以Timothy Davis教授开发的KLU最为有效率。KLU主要由预处理,首次LU分解,再分解和回代求解这几个部分组成。再分解部分是算法的重要组成部分。在一次电路模拟过程中,就是通过多次调用该部分来完成对稀疏矩阵的数值LU分解。因此,本文主要对这部分的算法进行了并行研究和探索,并提出了基于GPU平台的可行的并行算法。KLU算法在LU分解过程中,采用的算法是基于高斯消去法的Gilbert-Peierls算法。我们通过研究串行算法和程序提出了两种不同的并行设想,并在GPU平台上设计和实现了四种不同的并行算法P_Llen算法、P_Ulen算法、P nk算法和P_stream算法。我们在实验平台Ⅰ上对这四种并行算法进行了性能测试和分析,通过分析我们发现P_stream算法较前三种并行算法在性能上有较大的优势,但由于该并行算法受限于实验平台Ⅰ中GPU显存的限制,导致并行度较低,性能较串行算法有所下降。为提高P_stream算法的并行度,我们在GPU显存容量更大的实验平台Ⅱ上对其进行了性能的测试和分析。通过分析,我们发现随着并行度的提高,P_stream并行算法性能也随之得到提升,但还是受限于显存容量的限制,导致性能较串行算法并没得到提升。由于我们是首次尝试对KLU算法在GPU平台上进行并行算法的实现,加之稀疏矩阵数据的稀疏性、LU分解数据的前后依赖性、硬件限制以及自身编程经验的不足,导致并行算法性能较原有串行算法略有下降,但在本文中我们提出的一些并行设想以及尝试也能为同方向的研究者提供很好的借鉴。