CoD-SELL: A Non-Zero Location Dictionary Compression Sparse Matrix Format for SpMV on GPU

Sparse matrix-vector multiplication (SpMV) is a fundamental computational kernel extensively utilized in scientific computing. To accelerate SpMV, various sparse matrix formats have been proposed. Among them, SELL-C-σ stands out for adjusting the memory access patterns of sparse matrices on Graphics Processing Units (GPUs), which provide higher memory bandwidth than Central Processing Units (CPUs), making them suitable for memory-intensive computations. However, the majority of studies on sparse matrix formats have primarily focused on mitigating memory access penalties to maximize device memory throughput. While these efforts have led to significant improvements, further acceleration of SpMV requires a reduction in the number of memory accesses themselves. In this paper, we introduce a compressed sparse matrix format, Column Dictionary-compressed SELL (CoD-SELL), which builds upon SELL-C-σ by employing dictionary compression for non-zero locations. This approach aims to minimize memory accesses and enhance computational efficiency. Our contributions include addressing the challenges of applying dictionary compression to SpMV on GPUs, proposing the CoD-SELL format, and evaluating its performance on a GPU. The CoD-SELL format achieves up to a 31.4% reduction in memory footprint and accelerates SpMV computation by up to 1.40× compared to SELL-C-σ.