基于GPU的稀疏线性系统的预条件共轭梯度法

doi:10.3724/SP.J.1087.2013.00825

计算机应用 ›› 2013, Vol. 33 ›› Issue (03): 825-829.DOI: 10.3724/SP.J.1087.2013.00825

基于GPU的稀疏线性系统的预条件共轭梯度法

张健飞,沈德飞^*

河海大学力学与材料学院,南京 210098

收稿日期:2012-09-03 修回日期:2012-10-29 发布日期:2013-03-01 出版日期:2013-03-01
通讯作者: 沈德飞
作者简介:张健飞(1977-),男,江苏海门人,讲师,博士,主要研究方向:高性能计算、应用数值分析、计算力学、工程仿真; 沈德飞(1988-),女,江苏建湖人,硕士研究生,主要研究方向:计算力学、高性能计算。
基金资助:
国家自然科学基金资助项目(51109072)。

GPU-based preconditioned conjugate gradient method for solving sparse linear systems

ZHANG Jianfei, SHEN Defei^*

College of Mechanics and Materials, Hohai University, Nanjing Jiangsu 210098, China

Received:2012-09-03 Revised:2012-10-29 Online:2013-03-01 Published:2013-03-01
Contact: De-Fei SHEN

摘要/Abstract

摘要： 研究了基于GPU的稀疏线性方程组的预条件共轭梯度法加速求解问题,并基于统一计算设备架构(CUDA)平台编制了程序,在NVIDIAGT430 GPU平台上进行了程序性能测试和分析。稀疏矩阵采用压缩稀疏行(CSR)格式压缩存储,针对预条件共轭梯度法的算法特性,研究了基于GPU的稀疏矩阵与向量相乘的性能优化、数据从CPU端传到GPU端的加速传输措施。将编制的稀疏矩阵与向量相乘的kernel函数和CUSPARSE函数库中的cusparseDcsrmv函数性能进行了对比,最优得到了2.1倍的加速效果。对于整个预条件共轭梯度法,通过自编kernel函数来实现的算法较之采用CUBLAS库和CUSPARSE库实现的算法稍具优势,与CPU端的预条件共轭梯度法相比,最优可以得到7.4倍的加速效果。

关键词: 图形处理器, 稀疏线性方程组, 预条件共轭梯度法, 压缩稀疏行, 统一计算设备架构

Abstract: A GPU-accelerated preconditoned conjugate gradient method was studied to solve sparse linear equations. And the sparse matrix was stored in the Compressed Sparse Row (CSR) format. The programmes were coded on Compute Unified Device Architecture (CUDA) and tested on the device of nVidia GT430 GPU. According to the features of conjugate gradient method, strategies were investigated to optimize the sparse matrix vector multiplication and the data transfer between CPU and GPU. Compared with the implementation calling cusparseDcsrmv, the self-developed kernel code of sparse matrix vector multiplication can go to a speed-up of 2.1 in the best case. Equipped with this kernel, the preconditioned conjugate gradient code obtains a maximum speed-up of 7.4 against the CPU code, which is a bit advantageous over that using CUBLAS library and CUSPARSE library.

Key words: Graphic Processing Unit (GPU), sparse linear equations, preconditioned conjugate gradient method, Compressed Sparse Row (CSR), Compute Unified Device Architecture (CUDA)

中图分类号:

TP312

张健飞沈德飞. 基于GPU的稀疏线性系统的预条件共轭梯度法[J]. 计算机应用, 2013, 33(03): 825-829.

ZHANG Jianfei SHEN Defei. GPU-based preconditioned conjugate gradient method for solving sparse linear systems[J]. Journal of Computer Applications, 2013, 33(03): 825-829.

参考文献

[1]曾攀.工程中的有限元方法[M].3版.北京:清华大学出版社,2006.
[2]Nvidia. NVIDIA CUDA C programming guide[EB/OL]. [2012-05-15]. http://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf.
[3]KRUGER T, WESTERMANN R. Linear algebra operators for GPU implementation of numerical algorithms[J]. ACM Transactions on Graphics, 2003, 22(3):908-916.
[4]BOLZ J, FARMER I, GRISPUN E, et al. Sparse matrix solvers on the GPU:conjugate gradients and multigrid[J].ACM Transactions on Graphics,2003,22(3):917-924.
[5]NATHAN B,MICHAEL G. Efficient sparse matrix-vector multiplication on CUDA [R]. Santa Clara, California: NVIDIA, 2008.
[6]AIL C, AKIRA N, SATOSHI M. Fast conjugate gradients with multiple GPUs[C]// Computational Scinence-ICCS 2009, LNCS 5544. Berlin: Springer,2009:893-903.
[7]MUTHU M B, RAJESH B. Optimizing sparse matrix-vector multiplication on GPUs[R]. Armonk, NY: IBM,2009.
[8]李熙铭. 基于GPU的高性能有限元方法研究[D].长春:吉林大学,2011.
[9]胡耀国.基于GPU的有限元方法研究[D].武汉:华中科技大学,2011.
[10]李晓梅,吴建平. Krylov子空间方法及其并行计算[J].计算机科学,2005, 32(1): 19-20.
[11]李爱芹. 线性方程组的迭代解法[J]. 科学技术与工程,2007, 7(14): 3357-3364.
[12]YOUSEF S. Iterative methods for sparse linear systems[M]. 2rd ed. Philadelphia: Society for Industrial and Applied Mathematics,2003.
[13]张兰.稀疏矩阵方程组预处理迭代技术研究[D].广州:华南理工大学,2010.
[14]Nvidia. CUDA CUSPARSE Library[EB/OL]. [2012-07-01]. http://developer.download.nvidia.com/compute/DevZone/docs/html/CUDALibraries/doc/CUSPARSE_Library.pdf.
[15]Nvidia. CUDA CUBLAS Library[EB/OL]. [2012-07-01].http://developer.download.nvidia.com/compute/DevZone/docs/html/CUDALibraries/doc/CUBLAS_Library.pdf.
[16]刘小虎,胡耀国,符伟.大规模有限元系统的GPU加速计算研究[J].计算力学学报, 2012, 29(1):146-152.
[17]白洪涛.基于GPU的高性能并行算法研究[D].长春:吉林大学,2010.
[18]University of Florida. The University of Florida Sparse Matrix Collection [DB/OL]. [2012-08-06].http://www.cise.ufl.edu/research/sparse/matrices.

基于GPU的稀疏线性系统的预条件共轭梯度法

GPU-based preconditioned conjugate gradient method for solving sparse linear systems

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	涂进兴, 李志雄, 黄建强. 基于GPU对角稀疏矩阵向量乘法的动态划分算法[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3521-3529.
[2]	蔡婧雯, 韦永壮, 刘争红. 基于GPU的密码S盒代数性质评估方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2750-2756.
[3]	徐启迪, 刘争红, 郑霖. 基于GPU的低密度奇偶校验码译码加速技术[J]. 《计算机应用》唯一官方网站, 2022, 42(12): 3841-3846.
[4]	解文博, 韦永壮, 刘争红. 基于CUDA的SKINNY加密算法并行实现与分析[J]. 计算机应用, 2021, 41(4): 1136-1141.
[5]	杨先凤, 贵红军, 傅春常. 统一计算设备架构下的F-X域预测滤波并行算法[J]. 计算机应用, 2021, 41(2): 486-491.
[6]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[7]	何希, 吴炎桃, 邸臻炜, 陈佳. 基于图形处理器的形态学重建系统[J]. 计算机应用, 2019, 39(7): 2008-2013.
[8]	武旭晨, 朴春慧, 蒋学红. 基于GPU并行计算的电动出租车新建充电站选址模型[J]. 计算机应用, 2019, 39(10): 3071-3078.
[9]	姬丽娜, 陈庆奎, 陈圆金, 赵德玉, 方玉玲, 赵永涛. 基于GPU的视频流人群实时计数[J]. 计算机应用, 2017, 37(1): 145-152.
[10]	官亚勤, 赵学胜, 王鹏飞, 李大朋. 基于切片原理的海量点云并行简化算法[J]. 计算机应用, 2016, 36(7): 1793-1796.
[11]	蔡勇, 李胜. Matlab的图形处理器并行计算及其在拓扑优化中的应用[J]. 计算机应用, 2016, 36(3): 628-632.
[12]	龙超, 韩波, 张宇. 基于Kinect和视觉词典的三维SLAM[J]. 计算机应用, 2016, 36(3): 774-778.
[13]	张硕, 何发智, 周毅, 鄢小虎. 基于自适应线程束的GPU并行粒子群优化算法[J]. 计算机应用, 2016, 36(12): 3274-3279.
[14]	查珊珊, 王远军, 聂生东. 基于图形处理器加速的医学图像配准技术进展[J]. 计算机应用, 2015, 35(9): 2486-2491.
[15]	王磊, 王鹏飞, 赵学胜, 卢立托. 基于图形处理器的球面Voronoi图生成算法优化[J]. 计算机应用, 2015, 35(6): 1564-1566.