Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Dynamic partition algorithm for diagonal sparse matrix vector multiplication based on GPU
Jinxing TU, Zhixiong LI, Jianqiang HUANG
Journal of Computer Applications    2024, 44 (11): 3521-3529.   DOI: 10.11772/j.issn.1001-9081.2023101524
Abstract113)   HTML1)    PDF (1105KB)(31)       Save

Implementing diagonal Sparse Matrix Vector multiplication (SpMV) on Graphics Processing Unit (GPU) can make full use of the parallel computing capabilities of GPU and accelerate matrix vector multiplication. However, related mainstream algorithms have problems such as a large amount of zero-element filling data and low computational efficiency. In response to the above problems, a diagonal SpMV algorithm DIA-Dynamic (Diagonal-Dynamic) was proposed. Firstly, a new dynamic partition strategy was designed to divide the matrix into blocks according to different characteristics, which greatly reduced the zero-element filling while ensuring high computational efficiency of GPU, thereby removing redundant calculations. Then, a diagonal sparse matrix storage format BDIA (Block DIAgonal) was proposed to store block data, and the data layout was adjusted to improve memory access performance on GPU. Finally, based on the bottom of GPU, the conditional branch optimization was performed to reduce branch judgments, and dynamic shared memory was used to solve the problem of irregular access of vectors. Compared with the state-of-the-art Tile SpMV algorithm, DIA-Dynamic has the average acceleration ratio of 1.88; compared with the cutting-edge BRCSD (Diagonal Compressed Storage based on Row-Blocks)-Ⅱ algorithm, DIA-Dynamic has the average zero-element filling reduced by 43%, and the average acceleration ratio reaches 1.70. Experimental results show that DIA-Dynamic can effectively improve the computational efficiency of diagonal SpMV on GPU, shorten the computing time, improving the program performance.

Table and Figures | Reference | Related Articles | Metrics