DeltaSPARSE: High-Performance Sparse General Matrix-Matrix Multiplication on Multi-GPU Systems

Sparse General Matrix-Matrix Multiplication (SpGEMM) serves as a fundamental operation in the domains of sparse linear algebra and graph data processing. The majority of existing research predominantly concentrates on optimizing SpGEMM in the context of single GPU scenarios. Nevertheless, the growing prevalence of multi-GPU systems offers opportunities to harness the computational capabilities of multiple GPUs, thereby enhancing the performance of sparse general matrix-matrix multiplication. The efficacy of multi-GPU SpGEMM is chiefly constrained by two factors: (1) the irregular sparse pattern of sparse matrices, and (2) the load imbalance among multiple GPUs. To address these challenges, this paper presents DeltaSPARSE, the first algorithm to achieve significant speed-up for large-scale SpGEMM on multiple GPUs, to the best of our knowledge. Our algorithm incorporates hybrid accumulators, which dynamically choose the most suitable accumulator algorithm for rows exhibiting varying levels of sparsity. Moreover, we suggest a hierarchical task scheduling approach to partition and allocate tasks across diverse levels of parallel hardware, such as GPU s, blocks, warps, and threads. Experimental outcomes utilizing the SuiteS parse matrix dataset reveal that DeltaSPARSE displays near-linear scalability in multi-GPU configurations. Furthermore, it attains substantial speed enhancements in comparison to the present state-of-the-art single GPU SpGEMM methods, including NSPARSE, spECK, bhSPARSE, and cuSPARSE, across matrices with various sparse characteristics.