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

发布时间：2020-04-13 01:58

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

求解算法,计算时间,并行算法

图 4-2 三种求解算法的计算时间比较图 4-2 中的断层柱状图显示了三种算法的计算时间，并对其进行了比较。通过上图可以清晰、直观的看出，本文算法的计算时间明显小于其它两种算法的计算时间，在保证计算精度的前提下，大大提高了稀疏线性三角系统的求解速度。这充分验证了基于部分值相加的并行求解算法具有高效性和优越性。4.3.3.1 与调用库 cuSPARSE 方法比较，本文算法计算速度的提高进一步证明本文并行算法的高效性，以调用 cuSPARSE 库求解算法的计算时间为归一化标准，用公式(4-1)计算本文并行算法计算速度提高的百分比。( )cusp addcuspT TT (4-1)式中，cuspT ——调用 cuSPARSE 库求解方法的计算时间；addT ——本文算法的计算时间。经过计算，本文并行算法计算速度提高的百分比如图 4-3 所示。

计算速度,求解方法,计算时间,折线

图 4-3 本文算法计算速度的提高由图 4-3 中折线可知，以调用 cuSPARSE 库求解方法的计算时间为标准，针对不同规模的稀疏性线性三角系统求解，本文算法的计算速度均有明显的提高，最小的速度提高百分比为 56%，最大的速度提高百分比达到 99%，明显加快了稀疏线性三角系统的求解速度。这是因为调用 cuSPARSE 库的求解算法存在分析和求解两个阶段，其中，分析阶段非常耗时，约占总求解时间的百分之八十，这严重阻碍了求解线性三角系统的速度。然而，基于部分值相加的并行算法不需要分析复杂的稀疏矩阵结构，，变量的计算顺序在求解时自然地执行，完全消除预处理阶段，从而大大减少了计算时间，提高了求解速度。4.3.3.2 与无同步求解算法比较，本文算法计算速度的提高以无同步算法的计算时间为归一化标准，用公式(4-2)计算本文并行算法计算速度提高的百分比。( )unsy addT T (4-2)
【学位授予单位】：华北电力大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP332;TP301.6

【相似文献】