Block strategy and adaptive storage for sparse matrix–vector multiplication on GPU
摘要
Sparse matrix–vector multiplication (SpMV) is a computationally intensive kernel ubiquitously employed in various linear algebra computations. In numerous high-performance applications, SpMV computations often become a performance bottleneck, making their optimization crucial. However, the irregular structure of sparse matrices can lead to redundant calculations, resulting in unbalanced loads and inefficient bandwidth utilization during SpMV operations on GPUs. In this paper, we introduce a novel approach called block strategy and adaptive storage (BSAS) to address these challenges. Our methodology involves partitioning the original matrix into uniform-distribution blocks based on the block strategy, ensuring maximum similarity in the count of non-zero elements per block. This partitioning balances the load, reduces redundant calculations, and minimizes conversion overhead. Additionally, we dynamically assign storage formats to each block using an adaptive storage format selection method that considers the distribution of non-zero elements within the blocks. Furthermore, we develop optimized kernel implementations for each block, significantly enhancing thread-level parallelism and memory utilization. We evaluated our proposed method against NVIDIA’s cuSPARSE library and three advanced SpMV algorithms: SELLP, Merge-Based, and BalanceCSR, using matrices from the SuiteSparse dataset on NVIDIA RTX 2080 Ti and A100 GPUs. The results indicated that our method outperformed the compared algorithms, achieving average speedups of