CUDA架构下大规模稠密线性方程组的并行求解

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (32): 27-30.

CUDA架构下大规模稠密线性方程组的并行求解

杨梅1，李志民1，曹大勇2

1.哈尔滨工业大学电气工程系，哈尔滨 150001
2.哈尔滨理工大学应用数学系，哈尔滨 150080

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-11-11 发布日期:2011-11-11

Parallel algorithm for solving large-scale dense linear system on CUDA

YANG Mei1，LI Zhimin1，CAO Dayong2

1.Department of Electrical Engineering，Harbin Institute of Technology，Harbin 150001，China
2.Department of Applied Mathematics，Harbin University of Science and Technology，Harbin 150080，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-11-11 Published:2011-11-11

摘要/Abstract

摘要： 在Gauss-Jordan消去法的基础上，给出了一种适应于CUDA架构的改进Gauss-Jordan消去并行算法。通过分析该方法的处理过程以及CUDA架构的相应限制，在CUDA的grid-block-thread三层组织结构的基础上，从算法构造的角度提出了grid-strip-group-block-thread五层结构，给出了基础行以及全局基础行等概念，并构建了适应于CUDA架构的Gauss-Jordan消去法的并行版本，在最高维数为4 000维的大规模稠密线性方程组的算例求解上与串行Gauss-Jordan消去法进行了比较，实验结果表明，该算法能够充分利用GPU的硬件特性，有效地降低了大规模稠密线性方程组的求解时间。

关键词: 计算统一设备架构（CUDA）, 并行算法, 改进Gauss-Jordan消去法, 大规模稠密线性方程组

Abstract: A parallel improved version of the Gauss-Jordan elimination algorithm for solving large-scale dense linear system on CUDA is proposed in this paper.After analyzing the procedure of Gauss-Jordan elimination algorithm and the constraints of CUDA，it gives a new logical organization of “grid-strip-group-block-thread” and the concepts of “based line” and “global based line”，based on which the parallel version of the Gauss-Jordan elimination algorithm on CUDA is proposed.The numerical experiment of test instances with max size 4 000 shows that the algorithm can utilize the advantage of the GPU and decrease the computational time for the large-scale dense linear system effectively.

Key words: Compute Unified Device Architecture（CUDA）, parallel algorithm, improved Gauss-Jordan elimination algorithm, large-scale dense linear system

杨梅1，李志民1，曹大勇2. CUDA架构下大规模稠密线性方程组的并行求解[J]. 计算机工程与应用, 2011, 47(32): 27-30.

YANG Mei1，LI Zhimin1，CAO Dayong2. Parallel algorithm for solving large-scale dense linear system on CUDA[J]. Computer Engineering and Applications, 2011, 47(32): 27-30.

[1]	杨捷，吴素萍. 点云重建的并行算法[J]. 计算机工程与应用, 2020, 56(6): 213-219.
[2]	朱超，吴素萍. 特征点检测DoG并行算法[J]. 计算机工程与应用, 2020, 56(10): 36-43.
[3]	陈亚中1，李振军1，李荣华1，毛睿1，乔少杰2. TSCAN：利用并行策略改进的图结构聚类算法[J]. 计算机工程与应用, 2019, 55(1): 76-83.
[4]	王德政1，张益农1，杨帆2. 基于MapReduce的并行PLS过程监控算法实现[J]. 计算机工程与应用, 2018, 54(24): 61-65.
[5]	孙劲光1，吴素红2. 基于空间分割与椭球包围盒的碰撞检测算法[J]. 计算机工程与应用, 2016, 52(4): 217-222.
[6]	喻津1，周浩杰2，柴志雷1. 一种基于众核架构的稠密光流并行计算方法[J]. 计算机工程与应用, 2016, 52(16): 186-191.
[7]	曾博1，2，雷友诚1，王丛知2，邱维宝2，冯歌2，曾成志2，杨戈2，郑海荣2. 基于CUDA的声辐射力弹性成像算法研究[J]. 计算机工程与应用, 2015, 51(18): 249-254.
[8]	李敏1，2，宋曰聪1，吴斌3，彭保3. 基于Beowulf机群中改进粒子滤波的3D人体运动跟踪[J]. 计算机工程与应用, 2015, 51(14): 17-22.
[9]	王艾昕. 基于SIMD结构的矩形行列式并行算法研究[J]. 计算机工程与应用, 2012, 48(25): 48-51.
[10]	李文敬，刘之家，蓝贞雄. 无约束最优化问题的BFGS松弛异步并行算法[J]. 计算机工程与应用, 2012, 48(17): 44-47.
[11]	刘佳昆，周永权. 具有主从结构的并行人工萤火虫群优化算法[J]. 计算机工程与应用, 2012, 48(14): 33-37.
[12]	王震1，孙卫1，蔺小林2. 多自由度Vanderpol振子极限环计算[J]. 计算机工程与应用, 2012, 48(13): 230-233.
[13]	吴立强1，杨晓元1，2，郝斌3，刘镇3. 并行的NTRU格规约算法[J]. 计算机工程与应用, 2011, 47(28): 62-64.
[14]	汪保，孙秦. 求解非线性方程组的一种并行算法[J]. 计算机工程与应用, 2011, 47(2): 49-51.
[15]	于方. 三角网格表面任意两点间并行近似测地线算法[J]. 计算机工程与应用, 2011, 47(10): 197-200.