Efficient Sparse Matrix-Vector Multiplication on GPUs Using the CSR Storage Format

TLDR

Sparse matrix–vector multiplication is critical for computational science, yet the widely used CSR format performs poorly on GPUs because of irregular memory access, load imbalance, and limited parallelism, prompting the development of alternative storage schemes. This work introduces CSR‑Adaptive, an algorithm that preserves the CSR representation while optimizing its execution on GPUs. CSR‑Adaptive mitigates performance bottlenecks by streaming data into local scratchpad memory and dynamically allocating varying row counts to each GPU compute unit. The method delivers an average 14.7× speedup over existing CSR‑based approaches and 2.3× over the clSpMV cocktail, which combines multiple matrix formats.

Abstract

The performance of sparse matrix vector multiplication (SpMV) is important to computational scientists. Compressed sparse row (CSR) is the most frequently used format to store sparse matrices. However, CSR-based SpMV on graphics processing units (GPUs) has poor performance due to irregular memory access patterns, load imbalance, and reduced parallelism. This has led researchers to propose new storage formats. Unfortunately, dynamically transforming CSR into these formats has significant runtime and storage overheads. We propose a novel algorithm, CSR-Adaptive, which keeps the CSR format intact and maps well to GPUs. Our implementation addresses the aforementioned challenges by (i) efficiently accessing DRAM by streaming data into the local scratchpad memory and (ii) dynamically assigning different numbers of rows to each parallel GPU compute unit. CSR-Adaptive achieves an average speedup of 14.7× over existing CSR-based algorithms and 2.3× over clSpMV cocktail, which uses an assortment of matrix formats.