论文部分内容阅读
在大型电路模拟中,Ax=b形式的线性方程组的求解是影响电路模拟效率的关键问题。为了解决这一问题,目前已经存在许多针对大型电路模拟矩阵的求解器,例如sparce 1.3、superLU、KLU等。实验表明,与其他算法相比,KLU算法效率更高、更适合于处理大型电路模拟矩阵。KLU(Clark Kent LU),是由Clark Kent专门针对大型电路模拟矩阵设计的一种新型的稀疏矩阵求解算法。KLU算法共分为四个阶段：预处理阶段、分解阶段、再分解阶段、求解阶段。本文重点在GPU平台上,对KLU算法中的预处理阶段(btf_strongcomp算法、)和求解阶段(klu_solve算法)进行并行性研究与实现。在预处理阶段,利用btf算法将矩阵转化为上三角块的形式。btf算法包括两个部分：btf_maxtrans算法和btf_strongcomp算法。对btf_strongcomp算法在GPU平台上的可并行性作了详细的研究与探讨,提出了几种可并行的方案：深度优先搜索算法、可达矩阵算法、zdec算法的并行,并对DCSC算法在GPU平台上的可并行性作了研究。研究结果表明,在GPU平台上实现btf_strongcomp算法的并行,会导致算法性能下降,进而降低KLU算法的整体效率。但是对于某些矩阵而言,在使用zdec算法将矩阵转化为上三角块的形式后,可以提高KLU算法的整体效率。求解阶段可分为两部分：顺序消元和回代求解。由于在顺序消元的过程中存在很强的依赖性,本文只对klu_solve算法的回代求解部分在GPU平台上实现了并行。对于大部分矩阵而言,并行实现的klu_solve算法在Nvidia GeforceGTX275平台上的运行时间,是串行klu_solve算法在Intel Pentium D 2.80GHzCPU平台上运行时间的10倍以上。本文通过分析电路模拟矩阵和GPU平台的特点,并将KLU算法中的btf_strongcomp算法和klu_solve算法在GPU平台上实现了并行。实验结果表明,KLU算法中的预处理阶段和求解阶段不适合在GPU平台上实现并行。