基于变量相关性分解方法的稀疏线性方程组并行求解算法  

Parallel algorithm for solving sparse linear equations based on variable correlation decomposition

作　　者：刘珊瑕 靳松[1] 王文琛 汪宇航 王瑜[1] LIU Shanxia;JIN Song;WANG Wenchen;WANG Yuhang;WANG Yu(Department of Electronics and Communication Engineering,North China Electric Power University,Baoding 071001,China)

机构地区：[1]华北电力大学电子与通信工程系,保定071001

出　　处：《清华大学学报（自然科学版）》2020年第4期312-320,共9页Journal of Tsinghua University(Science and Technology)

基　　金：河北省自然科学基金资助项目(F2017502043);计算机体系结构国家重点实验室开放课题(CARCH201802);中央高校基本科研业务费专项资金项目(2017MS114)。

摘　　要：稀疏线性方程组的求解是许多大规模科学计算任务的核心环节。目前,并行算法的发展为稀疏线性方程组的求解提供了新的思路和强有力的工具。然而,现有的并行算法存在一些缺陷,如最优子矩阵的划分难以获得、并行任务间的同步开销较大等。针对上述问题,该文提出一种基于变量相关性分解方法的稀疏线性方程组并行求解算法。该算法首先对系数矩阵进行不完全LU分解,得到上三角和下三角方程组,然后在这2个方程组求解过程中利用y与x的关系分解变量的相关性,同时并行计算变量的独立部分值,最后将所有的独立部分值相加得到变量的最终值。由于算法中变量的求解无需等待其所有前继变量计算完成即可进行部分值计算,因此有效减少了算法的执行时间,进而提高了算法的求解速度及并行度。实验结果表明:与调用cusparse库函数实现的并行求解方法相比,该文提出的算法能将稀疏线性方程组的求解速度提升了50%以上。Sparse linear equations are the core of many large scientific computing tasks. Although parallel algorithms are providing powerful, new tools for solving sparse linear equations, existing parallel algorithms have some drawbacks such as the optimal sub-matrix being difficult to obtain and the algorithms requiring a large overhead to synchronize parallel tasks. This paper presents a parallel algorithm for sparse linear equations based on the variable correlation decomposition method. Firstly, the algorithm performs an incomplete LU decomposition on the coefficient matrix to obtain two equations for the upper and lower triangles. Then, the correlation between y and x is used to solve for the independent part of the variable in parallel from the upper and lower triangles. All the individual partial values are then added to get the final value of the variable. Since the solution does not need to wait for all the previous variables to be calculated, the partial value calculation can be performed in parallel as the calculation proceeds, which significantly reduces the algorithm execution time and improves the algorithm solution speed and parallelism. Tests show that this sparse linear equation solver is more than 50% faster than the parallel solution method in the cusparse library.

关 键 词：图形处理器 稀疏线性方程组 并行计算 变量部分值 线程 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]