Customizing GPU Kernels for Sparsity

Summary & Methodology Analysis

SparseDitto addresses the performance variability and inefficiency of sparse GPU kernels by providing a system that dynamically adapts data representation, execution strategy, and hardware mapping to specific input matrices, operators, and target GPUs. The system first extracts 36 structural features of the input matrix, categorized into intrinsic, representation-induced, and operator-induced features. It then ranks established optimization strategies using an offline-trained, interpretable additive energy model. Following this, an architecture-aware planner constructs multiple candidate designs by combining strategy rankings with target-GPU constraints. Coding and verification agents implement candidate kernels in CUDA and perform correctness validation, and the system finally refines kernels through iterative target-GPU profiling and performance measurement feedback.

The system relies on several operational components and comparisons. It is evaluated against baselines such as cuSPARSE, CB-SpMV, DTC-SpMM, HSMU-SpGEMM, SparseTIR, and AlphaSparse, using datasets from the SuiteSparse Matrix Collection, GPT-5.6-terra, and Reddit. Generated SpMM kernels accelerate full-batch GCN training by up to 3.39x. On an NVIDIA RTX PRO 6000 GPU, it achieves a geometric-mean speedup of 2.68x over cuSPARSE, with a maximum of 146.61x. On an NVIDIA H200 GPU, it achieves a geometric-mean speedup of 2.79x over cuSPARSE, with a maximum of 78.5x.

Despite these performance improvements, the system has several limitations. The performance gains of SparseDitto narrow as the dense dimension width K grows in SpMM operations. Additionally, SparseDitto may fail on some matrices due to resource constraints, mirroring issues seen in baselines. Finally, the system has a limited search budget, and some candidate generations may fail or return invalid results.