Computer Engineering ›› 2019, Vol. 45 ›› Issue (9): 23-31,39.doi: 10.19678/j.issn.1000-3428.0053513

Previous Articles     Next Articles

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).

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: