大规模稀疏线性系统的并行求解方法研究

• 作 者: 宋丽翠
• 出 处: 华北电力大学
• 发表日期: 2020年01期
• 关键词: GPU众核处理器 并行计算 大规模稀疏线性三角系统 变量部分值相加

目前,大规模稀疏线性系统的求解是许多科学计算和工程技术的重要组成部分。在一些以直接法为基础的稀疏线性系统求解任务中,稀疏线性三角系统的计算是求解大规模稀疏线性系统的核心环节。因此,快速求解稀疏线性三角系统成为了解决整个科学计算问题的关键。近几年,随着科学计算任务的规模和复杂度不断提高,稀疏线性三角系统的规模和复杂度也越来越大,导致所需处理的数据量骤增。然而,已有的求解方法均受限于稀疏线性三角系统求解的传统观点,即某一个变量的求解必须等到其所有前驱变量求解完成之后才能开始。这种方式不仅限制了求解时能够达到的任务并行度,无法充分利用众核处理器丰富的并行硬件资源。而且,线程间频繁的数据传递使同步开销较大,甚至抵消了并行计算技术带来的优势。针对现有方法存在的问题,本文提出一种基于部分值相加的并行求解算法。该方法首先并行计算变量的部分值,然后把变量的所有部分值相加得到变量的最终值。由于变量计算时无需等待所有前驱变量完成计算,大大提高了求解并行度和计算速度。在本文工作中,基于CUDA计算平台实现了并行求解算法。该算法把表示变量求解顺序的关联图分解成多个子图,每个线程计算子图的一层,充分利用了GPU丰富的并行计算资源。其次,为了减少存储器访问对算法性能的影响,充分利用了全局内存容量大及共享内存访存延迟低的特点,对本文提出的并行求解算法进行了优化。实验结果表明,与调用cuSPARSE库的求解算法以及无同步并行求解算法的计算时间比较,本文并行算法的计算速度平均提高80%,最大提高99%。在保证计算精度的前提下,大大提高了稀疏线性三角系统的求解速度。