TL;DR
This paper introduces CB-SpMV, a novel algorithm for accelerating sparse matrix-vector multiplication (SpMV) on GPUs. By employing a cache-friendly 2D blocking structure with data aggregation and an intelligent load balancing strategy, CB-SpMV significantly improves data locality and hardware utilization, leading to substantial performance gains over 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 applications. However, performing SpMV on GPUs is challenging due to two main issues:
- Data Locality: Traditional sparse matrix formats (like CSR and COO) store non-zero elements and their indices separately. This leads to scattered memory accesses, resulting in poor cache hit rates on GPUs, which rely heavily on efficient data access for performance. Block-based formats (like BSR) improve locality but can be inefficient for sparse sub-blocks.
- Hardware Utilization and Load Balancing: In block-based SpMV, the varying number of non-zero elements within sub-blocks can lead to uneven workloads across GPU processing units (thread blocks and Streaming Multiprocessors). This imbalance results in idle threads and processors, hindering overall performance. Existing methods like TileSpMV attempt to address these issues but still face limitations.
Methods
CB-SpMV tackles these challenges with a multi-pronged approach:
- Cache-Friendly 2D Blocking Structure: The matrix is divided into uniform 16x16 sub-blocks. This size is chosen to efficiently map to GPU warps.
- Intra-Block Data Aggregation: Data within each sub-block (coordinates and values) is 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 manage memory efficiently and avoid alignment issues.
- 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 hardware utilization. A threshold (
th_o) determines when this aggregation is applied. - Computation Adaptation (Format Selection): Sub-blocks are dynamically assigned one of three formats: COO (for low-density), Dense (for high-density), or CSR (for intermediate sparsity). This optimizes computation for different sparsity levels.
- Thread-Block Load Balancing: A priority queue-based algorithm is used to dynamically reassign sub-blocks to thread blocks, ensuring a more even distribution of workload and mitigating performance bottlenecks caused by load imbalance.
Datasets
The paper evaluates CB-SpMV on 2,843 matrices from the SuiteSparse Matrix Collection. For specific analyses (like cache hit rates and ablation studies), a subset of 15 representative matrices from this collection is used.
Key Insights and Ideas
- Data Aggregation is Key for Cache Efficiency: By treating sub-block data as a unified, contiguous unit, CB-SpMV dramatically improves L1 and L2 cache hit rates, a critical factor for GPU performance.
- Adaptive Strategies are Crucial: No single sparse matrix format or optimization works best for all matrices. CB-SpMV's success comes from its ability to adapt its strategies (column aggregation, format selection, load balancing) based on sub-block sparsity and overall matrix characteristics.
- Load Balancing is More Than Just Distributing Work: The paper highlights that effective load balancing requires dynamically remapping sub-block assignments to equalize computational load across thread blocks, not just distributing them evenly initially.
- The 16x16 Block Size is a Sweet Spot: This block size is chosen to align well with GPU warp sizes, maximizing parallelism and minimizing under-utilization.
Key Results
- Significant Speedups: CB-SpMV achieves average speedups of up to 3.95x on NVIDIA A100 GPUs and 3.06x on RTX 4090 GPUs compared to state-of-the-art methods like cuSPARSE-BSR, TileSpMV, and DASP.
- Improved Cache Performance: CB-SpMV demonstrates substantial improvements in cache hit rates. For example, it achieves 82% higher L1 cache hit rates and 19% higher L2 cache hit rates compared to TileSpMV on the RTX 4090.
- Storage Efficiency: CB-SpMV's storage overhead is comparable to CSR, significantly outperforming BSR, which incurs higher overhead due to storing zero elements.
- Ablation Study: The combination of all proposed optimizations (data aggregation, column aggregation, format selection, and load balancing) yields the highest performance gains, with each component contributing significantly.
Limitations and Future Work
- Preprocessing Overhead: While CB-SpMV offers excellent runtime performance, there is a preprocessing overhead to convert matrices into its format. However, this is deemed a worthwhile trade-off for iterative solvers.
- DASP on A100: The paper notes that DASP, which leverages Tensor Cores, shows competitive performance on the A100 GPU. The authors suggest that further work is needed to fully exploit Tensor Core potential for SpMV.
- Future Work: The authors mention that extending the CB-SpMV framework to other sparse matrix operations like SpMM (Sparse Matrix-Matrix Multiplication) and SpGEMM (Sparse General Matrix-Matrix Multiplication) is a promising direction.
Summary updated