Adaptive diagonal sparse matrix-vector multiplication on GPU

Jiaquan Gao

doi:10.1016/j.jpdc.2021.07.007

Return

Adaptive diagonal sparse matrix-vector multiplication on GPU

2021-11-01

PRE

Jiaquan Gao *

Yifei Xia

Renjie Yin

DOI：10.1016/j.jpdc.2021.07.007

Original

Original request for help

Save

Abstract

En 中文

For diagonal sparse matrices that have many long zero sections or scatter points or diagonal deviations from the main diagonal, a great number of zeros need be filled to maintain the diagonal structure while using DIA to store them, which leads to the performance degradation of the existing DIA kernels because the padded zeros consume extra computation and memory resources. This motivates us to present an adaptive sparse matrix-vector multiplication (SpMV) for diagonal sparse matrices on the graphics processing unit (GPU), called DIA-Adaptive, to alleviate the drawback of DIA kernels for these cases. For DIA-Adaptive, there are the following characteristics: (1) two new sparse storage formats, BRCSD (Diagonal Compressed Storage based on Row-Blocks)-I and BRCSD-II, are proposed to adapt it to various types of diagonal sparse matrices besides adopting DIA, and SpMV kernels corresponding to these storage formats are presented; and (2) a search engine is designed to choose the most appropriate storage format from DIA, BRCSD-I, and BRCSD-II for any given diagonal sparse matrix; and (3) a code generator is presented to automatically generate SpMV kernels. Using DIA-Adaptive, the ideal storage format and kernel are automatically chosen for any given diagonal sparse matrix, and thus high performance is achieved. Experimental results show that our proposed DIA-Adaptive is effective, and has high performance and good parallelism, and outperforms the state-of-the-art SpMV algorithms for all test cases. (C) 2021 Elsevier Inc. All rights reserved.

Keywords:

Diagonal sparse matrices

Sparse matrix-vector multiplication

Sparse storage format

CUDA

GPU

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.