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

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (32): 27-30.

• 研究、探讨 • Previous Articles Next Articles

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

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

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

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

Abstract

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

摘要： 在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消去法, 大规模稠密线性方程组

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

[1]	YANG Jie, WU Suping. Parallel Algorithm for Point Cloud Reconstruction [J]. Computer Engineering and Applications, 2020, 56(6): 213-219.
[2]	ZHU Chao, WU Suping. Feature Point Detection DoG Parallel Algorithm [J]. Computer Engineering and Applications, 2020, 56(10): 36-43.
[3]	CEHN Yazhong1, LI Zhenjun1, LI Ronghua1, MAO Rui1, QIAO Shaojie2. Improved Graph Structure Clustering Algorithm by Using Parallel Strategy [J]. Computer Engineering and Applications, 2019, 55(1): 76-83.
[4]	WANG Dezheng1, ZHANG Yinong1, YANG Fan2. Implementation of parallel PLS algorithm of process monitoring using MapReduce [J]. Computer Engineering and Applications, 2018, 54(24): 61-65.
[5]	SUN Jinguang1, WU Suhong2. Collision detection algorithm based on ellipsoid bounding box and spatial decomposition [J]. Computer Engineering and Applications, 2016, 52(4): 217-222.
[6]	WEI Hongchang, ZHU Zhengdong, DONG Xiaoshe, NING Jie. Asymptotic fitting optimization technology for source-to-source compile system on CPU-GPU architecture [J]. Computer Engineering and Applications, 2016, 52(21): 30-35.
[7]	YU Jin1, ZHOU Haojie2, HAI Zhilei1. Dense optical flow parallel computing method based on mesh many-core architecture [J]. Computer Engineering and Applications, 2016, 52(16): 186-191.
[8]	LI Zhengfu1，2, WANG Xicheng3, LI Keqiu1, YAO Xiang3, DONG Yueli2. Information entropy multi-population genetic algorithm based on CUDA [J]. Computer Engineering and Applications, 2016, 52(1): 12-16.
[9]	ZHONG Jiyuan, MEI Kuizhi, WEN Zhexi. Parallel stream computing implementation of GIST algorithm on heterogeneous platform [J]. Computer Engineering and Applications, 2015, 51(6): 139-144.
[10]	DONG Lili, DONG Wei, ZHANG Xiang. Research for memory data clustering efficiency with CUDA [J]. Computer Engineering and Applications, 2015, 51(22): 243-251.
[11]	LIN Min, ZHONG Yiwen. Three GPU-based parallel simulated annealing algorithm with adaptive neighborhood [J]. Computer Engineering and Applications, 2015, 51(22): 70-76.
[12]	ZHU Zhengdong1, LIU Yuan1, ＷEI Hongchang1, YAN Kang1, WANG Yinfeng2, DONG Xiaoshe1. Novel automatic mapping technology on CPU-GPU heterogeneous systems [J]. Computer Engineering and Applications, 2015, 51(21): 41-47.
[13]	ZENG Bo1，2, LEI Youcheng1, WANG Congzhi2, QIU Weibao2, FENG Ge2, ZENG Chengzhi2, YANG Ge2, ZHENG Hairong2. CUDA-based acoustic radiation force imaging algorithm [J]. Computer Engineering and Applications, 2015, 51(18): 249-254.
[14]	WANG Hong1，2, WANG Peng1，2. Improved AC pattern matching algorithm based on GPU [J]. Computer Engineering and Applications, 2015, 51(18): 7-12.
[15]	XU Liang1, TIAN Zheng2, WANG Zhen2. Parallel stereo matching using variable window based disparity refinement [J]. Computer Engineering and Applications, 2015, 51(15): 193-197.

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

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics