CB-Sparse:A Cache-Friendly Data Aggregating Algorithm for Block-Based Sparse Matrix Multiplication on GPUs
Abstract
Sparse matrix multiplications—including SpMV, SpMM, and SpGEMM—are fundamental to scientific computing, graph analytics, and machine learning. Despite extensive GPU-focused optimizations such as custom sparse formats and load balance, CSR-style and block-based methods can still underexploit fine-grained cache locality because separated metadata/value streams, block padding, and scattered matrix-matrix updates limit data reuse. In this paper, we propose CB-Sparse, a cache-friendly sparse multiplication algorithm leveraging a 2D blocking structure and virtual memory pointers. The matrix is first partitioned into independent and regular sub-blocks, where intra-block data is compactly aggregated via virtual pointers. Then, distinct optimization strategies are applied for various sparse multiplication paradigms. For SpMV and SpMM, we design a warp-level column aggregation scheme and a format selection mechanism to enhance both warp utilization and parallel efficiency. For SpMV specifically, a load-balancing algorithm is introduced to address the imbalance in non-zero element workloads across thread blocks. For SpMM, we develop efficient accumulation and write-back strategies to improve the overall performance of matrix-matrix operations. For SpGEMM, We design a faster symbol stage processing algorithm for 2D block formats to improve the speed of obtaining C-block nonzero structures. All these techniques are integrated into three efficient block-based sparse kernels, each tailored to its corresponding multiplication paradigm, thereby improving performance under the unified blocked structure. We evaluate CB-Sparse on NVIDIA A100 and RTX 4090 GPUs using up to 2,843 SuiteSparse matrices. Across representative baselines, CB-Sparse achieves up to 3.95 ×, 4.78 ×, and 2.93 × average speedups for SpMV, SpMM, and SpGEMM, respectively. Cache hit rates improve by up to 47.8%, confirming the effectiveness of CB-Sparse’s cache-aware design. The implementation is available at: https://github.com/xing-cong/CB-Sparse.