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

Research on Storage Format Optimization of Sparse Matrix Based on GPU

作　　者：杨世伟 蒋国平[2] 宋玉蓉[2] 涂潇 YANG Shiwei;JIANG Guoping;SONG Yurong;TU Xiao(School of Computer Science,Nanjing Utniversity of Posts and Telecommunications,Nanjing 210023,China;School of Automation,Nanjing Utniversity of Posts and Telecommunications,Nanjing 210023,China)

机构地区：[1]南京邮电大学计算机学院,南京210023 [2]南京邮电大学自动化学院,南京210023

出　　处：《计算机工程》2019年第9期23-31,39,共10页Computer Engineering

基　　金：国家自然科学基金(61672298,61873326,61373136)

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

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

分 类 号：TP312[自动化与计算机技术—计算机软件与理论]