基于GPU平台的KLU并行算法的研究与实现:预处理及回代求解

摘要

在大型电路模拟中,Ax=b形式的线性方程组的求解是影响电路模拟效率的关键问题。为了解决这一问题,目前已经存在许多针对大型电路模拟矩阵的求解器,例如sparce1.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 D2.80GHzCPU平台上运行时间的10倍以上。
　　 本文通过分析电路模拟矩阵和GPU平台的特点,并将KLU算法中的btf_strongcomp算法和klu_solve算法在GPU平台上实现了并行。实验结果表明,KLU算法中的预处理阶段和求解阶段不适合在GPU平台上实现并行。

目录

文摘

英文文摘

图表目录

第一章 绪论

1.1 论文研究背景

1.2 论文研究内容

1.3 硬件平台和测试用例

1.4 论文结构

第二章 GPU体系结构与CUDA介绍

2.1 GPU体系结构

2.2 CUDA基础

2.2.1 CUDA编程模型

2.2.2 CUDA存储器模型

2.3 本章小结

第三章 KLU算法概述

3.1 KLU算法简介

3.2 预处理阶段介绍

3.2.1 btf(Block Triangular Form)算法

3.2.2 amd(Approximate Minimum Degree)算法

3.3 求解阶段

3.4 相关研究

3.4.1 btf_strongcomp算法的相关研究

3.4.2 amd算法的相关研究

3.5 本章小结

第四章 btf_strongcomp算法在GPU平台上的并行

4.1 深度优先搜索算法的并行

4.2 DCSC算法(divide and conquer strong components)

4.3 可达矩阵算法的并行

4.3.1 可达矩阵的定义及相关并行思想

4.3.2 并行算法存在的问题

4.4 zdec(Zero-descendant)算法

4.4.1 算法思想

4.4.2 算法性能分析

4.4.3 实验结果对整个KLU算法的影响

4.5 本章小结

第五章 klu solve算法在GPU平台上的并行

5.1 求解阶段(klu_solve算法)的并行性研究

5.1.1 并行算法分析

5.1.2 实验结果和性能分析

5.2 本章小结

第六章 总结与进一步工作

6.1 主要结论

6.1.1 btf_strongcomp算法

6.1.2 klu_solve算法

6.1.3 结论

6.2 进一步工作

参考文献

致谢