A new diagonal storage for efficient implementation of sparse matrix-vector multiplication on graphics processing unit

The sparse matrix-vector multiplication (SpMV) is of great importance in computational science. For multidiagonal sparse matrices that have many long zero sections or scatter points, a great number of zeros are filled to maintain the diagonal structure when using the popular DIA format to store them. This leads to the performance degradation of the DIA kernel. To alleviate the drawback of DIA, we present a novel diagonal storage format, called RBDCS (diagonal compressed storage based on row-blocks), for multidiagonal sparse matrices, and thus propose an efficient SpMV kernel that corresponds to RBDCS. Given that the RBDCS kernel codes must be manually rewritten for different multidiagonal sparse matrices, a code generator is presented to automatically generate RBDCS kernel codes. Experimental results show that the proposed RBDCS kernel is effective, and outperforms HYBMV in the CUSPARSE library, and three popular diagonal SpMV kernels: DIA, HDI, and CRSD.

Automated summary

This paper introduces a new diagonal storage format RBDCS and proposes an efficient SpMV kernel for handling multidiagonal sparse matrices. Experimental results demonstrate that the RBDCS kernel outperforms popular diagonal SpMV kernels.