CB-SpMV:A Data Aggregating and Balance Algorithm for Cache-Friendly Block-Based SpMV on GPUs

Xing Cong, FuKai Sun, Yifan Chen, Chenhao Xie, Yi Liu, Depei Qian

TL;DR

This paper introduces CB-SpMV, a novel algorithm for optimizing sparse matrix-vector multiplication (SpMV) on GPUs. By employing a cache-friendly 2D blocking structure with data aggregation and intelligent load balancing, CB-SpMV significantly boosts performance and cache efficiency compared to existing state-of-the-art methods.

What Problem Does This Paper Address?

Sparse matrix-vector multiplication (SpMV) is a fundamental operation in many scientific and engineering domains. However, its performance on GPUs is hampered by several challenges:

  • Data Locality: Traditional sparse matrix formats (like CSR) store non-zero elements and their indices separately, leading to scattered memory accesses that reduce cache hit rates. Block-based formats improve this but can still suffer from inefficient data layout.
  • Hardware Utilization: GPUs have a highly parallel architecture, but sparse matrices often have irregular sparsity patterns. This can lead to "idle" threads within warps, especially in highly sparse sub-blocks, wasting computational resources.
  • Load Balancing: The varying number of non-zero elements across different sub-blocks can result in uneven workloads assigned to GPU thread blocks, leading to performance bottlenecks as some blocks finish much earlier than others.

Existing methods have attempted to address these issues through various storage formats, dynamic format selection, and hardware-specific optimizations, but a comprehensive solution that tackles all three challenges simultaneously remains elusive.

Methods

CB-SpMV introduces a multi-faceted approach to optimize SpMV on GPUs:

  • 2D Blocking Structure: The input matrix is divided into uniform 16x16 sub-blocks. This size is chosen to efficiently map to GPU warps.
  • Intra-Block Data Aggregation: Within each sub-block, different data types (indices, values) are aggregated into a contiguous memory region using a virtual pointer mechanism. This significantly improves data locality by reducing scattered memory accesses. Techniques like coordinate compression and padding are used to handle mixed data types and memory alignment issues.
  • Computational Adaptation: To address varying sub-block sparsity:
  • Block-Aware Column Aggregation: For sparse sub-blocks, columns with all-zero elements are removed and remaining columns are shifted. This increases the density of non-zero elements within the sub-block, improving warp utilization. A threshold (th0) determines when this is applied.
  • Format Selection: For denser sub-blocks, a strategy is employed to select the most efficient format (COO, CSR, or Dense) based on the sub-block's sparsity level, minimizing overhead and maximizing performance. Thresholds (th1, th2) guide this selection.
  • Thread-Block Load Balancing: A priority queue-based algorithm is used to dynamically reassign sub-blocks among thread blocks. This ensures a more equitable distribution of work, preventing bottlenecks caused by heavily loaded blocks.

Datasets

The paper evaluates CB-SpMV using 2,843 matrices from the SuiteSparse Collection. For specific analyses (e.g., cache hit rate comparison, ablation studies), a subset of 15 representative matrices from this collection was used. No new benchmarks were introduced.

Key Insights and Ideas

  • Data Aggregation is Key for Locality: The core idea of packing all data related to a sub-block contiguously in memory, regardless of its original format, is a powerful way to exploit GPU caches. This goes beyond simply choosing a "good" format and actively reorganizes data for optimal access.
  • Adaptability is Crucial: No single sparse matrix format or optimization strategy works best for all sub-blocks. CB-SpMV's strength lies in its ability to adapt its approach (column aggregation, format selection) based on the specific sparsity characteristics of each sub-block.
  • Load Balancing is Not an Afterthought: The paper emphasizes that even with efficient data handling, uneven workload distribution can cripple performance. The dynamic load balancing mechanism is presented as a critical component for achieving overall efficiency.
  • Bridging the Gap Between Sparse and Dense: By intelligently handling both very sparse and very dense sub-blocks, CB-SpMV can effectively leverage hardware for a wider range of matrices, unlike methods that might excel only in one extreme.

Key Results

  • Significant Speedups: CB-SpMV achieves average speedups of up to 3.95x on an NVIDIA A100 GPU and 3.06x on an NVIDIA RTX 4090 GPU compared to state-of-the-art methods like cuSPARSE-BSR, TileSpMV, and DASP.
  • Improved Cache Performance: CB-SpMV significantly boosts L1 and L2 cache hit rates. For example, compared to TileSpMV on the RTX 4090, it achieves 82% higher L1 cache hit rates and 19% higher L2 cache hit rates.
  • Effective Load Balancing: The load balancing strategy demonstrably reduces workload disparities among thread blocks, contributing to overall performance gains.
  • Storage Efficiency: CB-SpMV's storage overhead is comparable to CSR, outperforming BSR which incurs higher overhead due to storing zero elements.

Limitations and Future Work

  • Tensor Core Integration: The paper notes that while DASP leverages Tensor Cores, CB-SpMV does not explicitly integrate them. The authors suggest that exploring Tensor Core acceleration for CB-SpMV is a key direction for future work.
  • Pre-processing Overhead: While CB-SpMV's preprocessing time is competitive, especially for smaller matrices, it is still an overhead. The authors acknowledge this as a trade-off for improved computation performance, particularly for iterative solvers.
  • Block Size Optimization: The paper uses a fixed 16x16 block size. Further research could explore adaptive block sizing strategies.

Summary updated

Abstract

Sparse matrix-vector multiplication (SpMV) is crucial in computational science, engineering, and machine learning. Despite substantial efforts to improve SpMV performance on GPUs through various techniques, issues related to data locality, hardware utilization, and load balancing persist, leaving room for further optimization. This paper presents CB-SpMV, a cache-friendly SpMV optimization algorithm, using a novel data convergent and adaptable 2D blocking structure. The matrix in CB-SpMV is divided into independent sub-blocks, with virtual pointers aggregating different types of intra-block data for better cache-level data locality. To enhance hardware utilization, a block-aware column aggregation strategy and the selection of sub-block formats are proposed to accelerate computation and adapt to varying sparse matrices. Finally, an inter-block load-balancing algorithm is designed to ensure efficient workload distribution across thread blocks. Experimental evaluations on 2,843 matrices from the SuiteSparse Collection show that CB-SpMV significantly improves cache hit rates and achieves average speedups of up to 3.95x over state-of-the-art methods like cuSPARSE-BSR, TileSpMV, and DASP on NVIDIA A100 and RTX 4090 GPUs. The implementation is available at: \url{https://github.com/xing-cong/CB-Sparse}.
BibTeX
@inproceedings{cong2025cb,
  author = {Xing Cong and FuKai Sun and Yifan Chen and Chenhao Xie and Yi Liu and Depei Qian},
  title = {{CB-SpMV:A Data Aggregating and Balance Algorithm for Cache-Friendly Block-Based SpMV on GPUs}},
  booktitle = {ICS},
  year = {2025},
  url = {https://openreview.net/forum?id=GtMTPA8J24},
}
Figure