计算机工程 ›› 2019, Vol. 45 ›› Issue (9): 23-31,39.doi: 10.19678/j.issn.1000-3428.0053513

• 先进计算与数据处理 • 上一篇    下一篇

基于GPU的稀疏矩阵存储格式优化研究

杨世伟a, 蒋国平b, 宋玉蓉b, 涂潇a   

  1. 南京邮电大学 a. 计算机学院;b. 自动化学院, 南京 210023
  • 收稿日期:2018-12-28 修回日期:2019-02-19 出版日期:2019-09-15 发布日期:2019-09-03
  • 作者简介:杨世伟(1994-),男,硕士研究生,主研方向为复杂网络、GPU并行计算;蒋国平、宋玉蓉,教授、博士生导师;涂潇,博士。
  • 基金项目:
    国家自然科学基金(61672298,61873326,61373136)。

Research on Storage Format Optimization of Sparse Matrix Based on GPU

YANG Shiweia, JIANG Guopingb, SONG Yurongb, TU Xiaoa   

  1. a. School of Computer Science;b. School of Automation, Nanjing Utniversity of Posts and Telecommunications, Nanjing 210023, China
  • Received:2018-12-28 Revised:2019-02-19 Online:2019-09-15 Published:2019-09-03
  • Supported by:
    This work is supported by National Key R&D Program of China (No.2017YFB1201003-020), Provincial Key R&D Program of Gansu (No.18YF1FA058).

摘要: 稀疏矩阵存储格式中的稀疏矩阵向量乘(SpMV)计算效率低下,且分块行列(BRC)存储格式的计算结果缺少再现性和确定性。为此,提出一种改进的BRCP存储格式。采用不同的二维分块策略,根据矩阵各行非零元素分布的统计特性自适应调节分块参数,提高SpMV在GPU平台上的并行性,并设计基于快速分段求和算法的GPU内核函数,保证计算结果的确定性及其在不同GPU平台上的再现性。实验结果表明,BRCP存储格式具有较高的计算效率,相比BRC存储格式可减少并行环境中的SpMV计算误差,并提高PageRank排序的准确率。

关键词: 稀疏矩阵向量乘, 计算统一设备架构, 图形处理器, 存储格式, 浮点运算

Abstract: Sparse Matrix-Vector Multiplication(SpMV) calculation in sparse matrix storage format is inefficient,and the computing results of Blocked Row-Column(BRC) storage format lack reproducibility and certainty.To solve the problem,this paper proposes an improved Blocked Row-Column Plus(BRCP) storage format.The BRCP storage format adopts different two-dimensional blocking strategies,adaptively adjusts the blocking parameters according to the statistical characteristics of the distribution of non-zero elements of each row in the matrix,and improves the parallelism of SpMV on the GPU platform.A GPU kernel fuction based on fast segmented summation algorithm is designed to ensure the certainty of calculation results and their reproducibility on different GPU platforms.Experimental results show that the BRCP storage format has high computational efficiency,which reduces the SpMV calculation error in the parallel environment and improves the accuracy of PageRank sorting compared to the BRC storage format.

Key words: Sparse Matrix-Vector Multiplication(SpMV), Compute Unified Device Architecture(CUDA), Graphic Processing Unit(GPU), storage format, floating-point operation

中图分类号: