Accelerating sparse matrix-vector multiplication on GPUs using bit-representation-optimized schemes

Abstract

The sparse matrix-vector (SpMV) multiplication routine is an important building block used in many iterative algo-rithms for solving scientific and engineering problems. One of the main challenges of SpMV is its memory-boundedness. Although compression has been proposed previously to im-prove SpMV performance on CPUs, its use has not been demonstrated on the GPU because of the serial nature of many compression and decompression schemes. In this pa-per, we introduce a family of bit-representation-optimized (BRO) compression schemes for representing sparse matrices on GPUs. The proposed schemes, BRO-ELL, BRO-COO, and BRO-HYB, perform compression on index data and help to speed up SpMV on GPUs through reduction of memory trafic. Furthermore, we formulate a BRO-aware matrix re-ordering scheme as a data clustering problem and use it to increase compression ratios. With the proposed schemes, ex-periments show that average speedups of 1.5 compared to ELLPACK and HYB can be achieved for SpMV on GPUs. Copyright 2013 ACM.