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

doi:10.19678/j.issn.1000-3428.0053513

Abstract

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

CLC Number:

TP312

YANG Shiwei, JIANG Guoping, SONG Yurong, TU Xiao. Research on Storage Format Optimization of Sparse Matrix Based on GPU[J]. Computer Engineering, 2019, 45(9): 23-31,39.

Figures/Tables 15

References

[1] 尹孟嘉,许先斌,何水兵,等.GPU稀疏矩阵向量乘的性能模型构造[J].计算机科学,2017,44(4):182-187.
[2] BRIN S,PAGE L.The anatomy of a large-scale hypertextual Web search engine[J].Computer Networks and ISDN Systems,1998,30(1):107-117.
[3] TONG Hanghang,FALOUTSOS C,PAN Jiayu.Random walk with restart:fast solutions and applications[J].Knowledge and Information Systems,2008,14(3):327-346.
[4] LANGR D,TVRDÍK P.Evaluation criteria for sparse matrix storage formats[J].IEEE Transactions on Parallel and Distributed Systems,2016,27(2):428-440.
[5] 李佳佳,张秀霞,谭光明,等.选择稀疏矩阵乘法最优存储格式的研究[J].计算机研究与发展,2014,51(4):882-894.
[6] 刘芳芳,杨超,袁欣辉,等.面向国产申威26010众核处理器的SpMV实现与优化[J].软件学报,2018,29(12):3921-3932.
[7] LINDHOLM E,NICKOLLS J,OBERMAN S,et al.NVIDIA Tesla:a unified graphics and computing architecture[J].IEEE Micro,2008,28(2):39-55.
[8] MAGGIONI M,BERGER-WOLF T.Optimization techniques for sparse matrix-vector multiplication on GPUs[J].Journal of Parallel and Distributed Computing,2016,93(C):66-86.
[9] 张珩,张立波,武延军.基于Multi-GPU平台的大规模图数据处理[J].计算机研究与发展,2018,55(2):273-288.
[10] 程凯,田瑾,马瑞琳.基于GPU的高效稀疏矩阵存储格式研究[J].计算机工程,2018,44(8):54-60.
[11] LIU Yongchao,SCHMIDT B.LightSpMV:faster CUDA-compatible sparse matrix-vector multiplication using compressed sparse rows[J].Journal of Signal Processing Systems,2018,90(1):69-86.
[12] LIU Weifeng,VINTER B.CSR5:an efficient storage format for cross-platform sparse matrix-vector multiplication[C]//Proceedings of ACM International Conference on Supercomputing.New York,USA:ACM Press,2015:339-350.
[13] ASHARI A,SEDAGHATI N,EISENLOHR J,et al.An efficient two-dimensional blocking strategy for sparse matrix-vector multiplication on GPUs[M].Berlin,Germany:Springer,2014.
[14] ASHARI A,SEDAGHATI N,EISENLOHR J,et al.A model-driven blocking strategy for load balanced sparse matrix-vector multiplication on GPUs[J].Journal of Parallel and Distributed Computing,2015,76:3-15.
[15] WILKINSON J H.Error analysis of floating-point computation[J].Numerische Mathematik,1960,2(1):319-340.
[16] HILLIS W D,STEELE G L.Data parallel algorithms[J].Communications of the ACM,1986,29(12):1170-1183.
[17] HARRIS M,SENGUPTA S,OWENS J D.Parallel prefix sum(scan) with CUDA[M]//NGUYEN H.GPU Gems 3.New Jersey,USA:Addison Wesley,2007:851-876.
[18] SENGUPTA S,HARRIS M,ZHANG Yao,et al.Scan primitives for GPU computing[C]//Proceedings of ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware.New York,USA:ACM Press,2007:97-106.
[19] FILIPPONE S,CARDELLINI V,BARBIERI D,et al.Sparse matrix-vector multiplication on GPGPUs[J].ACM Transactions on Mathematical Software,2017,43(4):1-49.
[20] BLELLOCH G E,HEROUX M A,ZAGHA M.Segmented operations for sparse matrix computation on vector multiprocessors:CMU-CS-93-173[R].Pittsburgh,USA:Carnegie Mellon University,1993:1-7.
[21] CHENG J,GROSSMAN M,MCKERCHER T.Professional CUDA C Programming[M].[S.l.]:Wrox,2014.
[22] NVIDIA.CUDA C programming guide[EB/OL].[2018-11-27].https://docs.nvidia.com/cuda/cuda-c-programming-guide/index.html.
[23] DAVIS T A,HU Yifan.The university of florida sparse matrix collection[J].ACM Transactions on Mathematical Software,2011,38(1):1-25.

Research on Storage Format Optimization of Sparse Matrix Based on GPU

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References

Related Articles 15

Metrics

Comments

Recommended 10

[1]	ZHOU Qi,CHAI Xiaoli,MA Kejie,YU Zeren. Design and Implementation of Tucker Decomposition Module Based on CUDA and CUBLAS [J]. Computer Engineering, 2019, 45(3): 41-46.
[2]	CHENG Kai,TIAN Jin,MA Ruilin. Study on Efficient Storage Format of Sparse Matrix Based on GPU [J]. Computer Engineering, 2018, 44(8): 54-60.
[3]	TANG Jia,GONG Yili,LI Wenhai. A KNN Dynamic Extended Query Strategy Based on GPU [J]. Computer Engineering, 2018, 44(6): 1-7.
[4]	CHEN Yong,WU Xiaomin,YANG Jian,XI Hongsheng. Design and Implementation of H.264 Parallel Decoder Based on CUDA [J]. Computer Engineering, 2016, 42(5): 249-252,257.
[5]	PEI Xin,NIE Jun,CHEN Maozheng,LI Jian. Realization of Dual-channel Real-time Correlator Based on Heterogeneous Architecture [J]. Computer Engineering, 2016, 42(5): 42-46,53.
[6]	YANG Renzhong,ZHANG Jie,WEI Hongwei,SHI Lu. Real-time Decompression Processing Technology of Landsat8 Based on GPU [J]. Computer Engineering, 2016, 42(3): 301-307.
[7]	WANG Zhen,XU Xiaohang,WANG Jing,LI Sheng,ZHENG Hong. Research on GPU Real-time Stitching of Multi-channel High-definition YUV Video [J]. Computer Engineering, 2016, 42(12): 314-320.
[8]	MENG Xiaohua,QIN Dasheng,ZHENG Dongqin,ZHOU Yuyu. Parallel Simulation of Carbon Nano Tube Molecular Dynamics Based on GPU [J]. Computer Engineering, 2015, 41(4): 288-293.
[9]	YANG Xianfeng,LI Yingjie,LAI Junliang,PENG Bo. Real-time Ultrasound Elastic Imaging Algorithm Based on GPU Parallel Particle Swarm Optimization [J]. Computer Engineering, 2015, 41(12): 220-225,230.
[10]	DU Xiaogang,DANG Jianwu,WANG Yangping. Improved Parallel Computation Method of Mutual Information Based on Compute Unified Device Architecture [J]. Computer Engineering, 2015, 41(12): 288-292,298.
[11]	KANG Lei,ZHANG Shuben,YANG Jian. Design of GPU Cluster Management System Based on B/S Mode [J]. Computer Engineering, 2015, 41(10): 6-9.
[12]	FEI Xiong-wei,LI Ken-li,YANG Wang-dong. Optimization of AES Parallel Alogorithm Based on CUDA [J]. Computer Engineering, 2014, 40(9): 6-12.
[13]	MENG Xiao-hua, HUANG Cong-shan, ZHU Li-sha. Research on GPU Parallel Algorithm of Heat Conduction Based on CUDA [J]. Computer Engineering, 2014, 40(5): 41-44,48.
[14]	WANG Zhen, LI Ren-fa, LI Yan-biao, TIAN Zheng. A Parallel Multiple Pattern Matching Algorithm on Chinese/English Mixing [J]. Computer Engineering, 2014, 40(4): 318-320.
[15]	WU Jiana, LAN Shi-yonga,b, HUANG Fei-hua. Design and Implementation of a Multi-channel Fast Video Stitching System [J]. Computer Engineering, 2014, 40(2): 208-211,218.