It is found that no single kernel dominates across all graph structures and that effective Tensor Core utilization reaches only 5–20% on irregular GNN matrices, while graph reordering is broadly beneficial, yielding gains of up to $43\times $ when it enables Sparse Tensor Core execution.
Abstract
Sparse Matrix-Dense Matrix Multiplication (SpMM) is a dominant computational bottleneck in Graph Neural Network (GNN) inference and training. Representative studies report that SpMM consumes roughly 30% of the execution time in some Graph Convolutional Network (GCN) settings and over 80% in full-batch GraphSAGE training. Despite the rapid growth of GPU SpMM optimization techniques, spanning CUDA core kernels, Tensor Core acceleration, adaptive hybrid execution, autotuning, graph reordering, and framework integration, no dedicated survey has focused on this subfield. This paper presents the first such survey, covering 52 GPU-accelerated SpMM methods for GNN workloads published between 2019 and 2026. We constructed the corpus from IEEE Xplore, the ACM Digital Library, USENIX, arXiv, and Google Scholar, screening the studies first by title and abstract and then by full text. We included GPU-based SpMM kernels and GNN aggregation systems and excluded CPU-only, non-SpMM, abstract-only, and duplicate-version papers. We organize the literature into six technique categories and compare the methods using a ten-dimensional framework. Representative dimensions include sparse format, hardware target, parallelism strategy, load balancing, preprocessing cost, and open-source availability. We find that no single kernel dominates across all graph structures and that effective Tensor Core utilization reaches only 5–20% on irregular GNN matrices. Graph reordering is broadly beneficial, yielding gains of up to $43\times $ when it enables Sparse Tensor Core execution. Because the surveyed literature is overwhelmingly based on CUDA and Tensor Cores, our analysis is NVIDIA-centered. Nevertheless, we distinguish architecture-level insights that generalize to AMD and Intel accelerators from vendor-specific implementation details. We conclude with eight open challenges, including the no-single-winner problem, the Tensor Core utilization gap, standardized benchmarking, and graph-to-kernel compilation.
Sparse-dense matrix multiplication (SpMM), a fundamental computational kernel in graph analytics and scientific computing, can be substantially accelerated on modern GPUs by leveraging both dense and sparse Tensor Core units, thereby enabling high-throughput computation. However, existing methods often fail to exploit these hardware units effectively when applied to real-world sparse matrices that exhibit strong local structural heterogeneity. In particular, methods that either (i) reorganize all regions into dense-like tiles or (ii) aggressively convert them into strict 2:4 structured sparsity blocks typically incur low effective block density, substantial padding overhead, and nontrivial preprocessing costs. To address these challenges, we propose AFH-SpMM, a novel Auto-Fit Heterogeneous SpMM framework designed for adaptively parallelizing sparse-dense matrix multiplication on Tensor Core-equipped GPUs. Using a 16-row window as the basic processing granularity, AFH-SpMM adaptively maps local regions to two hardware-efficient computation paths: 16 × 16 dense tiles targeted to Dense Tensor Cores and 16 × 8 row-wise 2:4 structured-sparse tiles targeted to Sparse Tensor Cores. For the sparse computation path, AFH-SpMM further exploits local column proximity to mitigate subsequent memory-access and address-generation overheads. At runtime, the two block types are executed within a single fused kernel, while preserving distinct operand layouts and specialized MMA pipelines for each path. Experiments on 600 SuiteSparse matrices across NVIDIA RTX PRO 6000, H100, and A800 show that AFH-SpMM achieves average speedups of 1.33 × (up to 5.72 ×), and often leads cuSPARSE, ASpT, Sputnik, RoDe, Acc-SpMM, and MP-SpMM, with especially strong gains on medium and large matrices.
Zhi-Rui Chen, Heng Zhang, Kai-Fan Jia· Proceedings of the Internati...· 0 citations
Sparse Matrix-Matrix Multiplication (SpMM) is a fundamental operation in scientific computing and artificial intelligence. However, the inherent sparsity and irregularity of real-world datasets present significant challenges for developing high-performance SpMM kernels on modern GPUs. Existing approaches typically focus on a single type of compute unit, leaving the potential for cooperative parallelism between heterogeneous GPU cores largely under-explored. This paper introduces CoTC-SpMM, a cooperative Tensor–CUDA cores scheme for efficient SpMM on GPUs. Specifically, we first propose the HTC format to partition sparse matrices into dense and sparse components, enabling specialized kernels to leverage the distinct advantages of different computing units and maximize hardware utilization. Moreover, we implement several low-level runtime optimizations, including 1-D resource mapping for load balancing, software pipelining to hide memory latency, and PTX-level instruction tuning to enhance SpMM throughput. Experimental results on NVIDIA A100 and H800 GPUs demonstrate that CoTC-SpMM achieves substantial performance speedups over state-of-the-art implementations.
Qi Du, Shengle Lin, Yuedan Chen et al.· Proceedings of the Internati...· 0 citations
Matrix multiplication is a fundamental computation kernel in many parallel and sequential scientific applications. We target FP32 matrix multiplication on GPUs, a setting required by numerous HPC and scientific workloads. Alternative Basis Matrix Multiplication (ABMM) is a practical Strassen-like algorithm that reduces the number of additions while preserving the same asymptotic exponent and admitting a provable O(n) component-wise error bound. However, optimized GPU support for ABMM remains underexplored. This paper presents BAG (Basis Alternative Matrix Multiplication on GPUs), a GPU-oriented implementation of ABMM for the NVIDIA Ampere architecture. A naive GPU implementation of ABMM suffers from excessive workspace and memory traffic, launch-dominated serialization across heterogeneous steps, and high sensitivity to recursion and blocking parameters. We design fused ABMM kernels to shrink workspace and eliminate redundant global-memory traffic, specialize register usage for different primitive patterns to expose intra/inter-kernel parallelism, and introduce a cost-model-based recursion policy together with a Roofline-guided blocking strategy to stabilize performance across problem sizes and shapes. On an NVIDIA A100, experimental results show that 1-level BAG reaches a break-even point against cuBLAS FP32 GEMM at dimension 1280 for square matrices, and recursive BAG achieves a 1.24 × speedup over cuBLAS FP32 GEMM at dimension 4096. Our code is available at https://doi.org/https://github.com/napleon-liu/bag.
Yao Liu, Ye-Wen Li, Zhonghai Zhang et al.· Proceedings of the Internati...· 0 citations
Sparse GEneral Matrix Multiplication (SpGEMM) is one of the most vital kernels in massive research domains, including bioinformatics, graph analytics, and machine learning. Moreover, with the prosperity of the Big Data era, nonzero elements in sparse matrices of SpGEMM boost rapidly into the magnitude of billions. Thus, accelerating billion-scale SpGEMMs becomes the new spotlight. To reduce both the monetary and energy costs of resource-intensive billion-scale SpGEMMs while enhancing their efficiency, we propose CESpGEMM, an adaptive resource-efficient library for billion-scale SpGEMMs on CPU-GPU heterogeneous servers. We design an Anchor-based Sparsity-aware Data Compression (ASDC) mechanism of high compression ratio and throughput to resolve the bottleneck of data transfer through PCIe. Moreover, given an arbitrary SpGEMM, we develop a sampling-based auto-tuning model to determine the optimal hyperparameter configuration. CESpGEMM also involves a hierarchical workflow that exploits adaptive CPU-GPU collaboration. We evaluate the performance of CESpGEMM using one T4 GPU with state-of-the-art SpGEMM libraries. The results demonstrate that compared to the cutting-edge implementation with 4 T4 GPUs, CESpGEMM outperforms these in terms of memory and communication efficiency, and can achieve the average acceleration rate of 5.42×.
Ming Dun, Cheng Zhang, Shuhan Song et al.· IEEE Transactions on Paralle...· 0 citations
Sparse matrix-dense matrix multiplication (SpMM) is a core operation in scientific computing and deep learning. On multi-GPU platforms, its scalability is limited by communication bottlenecks. To address this, we propose DistSpMM, a co-design framework integrating data layout, pipelining, and communication strategies. DistSpMM introduces HSDMA, a lightweight algorithm that reduces communication by optimizing the dense matrix allocation. DistSpMM features a topology-aware two-stage pipeline that manages the IB/NVLink bandwidth disparity to maximize the overlap of computation and communication. Finally, DistSpMM employs an adaptive selector that uses a performance model to dynamically choose the optimal communication granularity (coarse vs. fine-grained) based on data sparsity and network tier. Experiments on diverse real-world datasets demonstrate the superior performance of our method. It achieves average speedups of 1.6 × to 2.6 × in single-node multi-GPU environments and 4.0 × to 5.1 × in multi-node multi-GPU environments over the baseline. Compared to the best state-of-the-art implementations, our method delivers up to 2.0 × speedup.
Junyu Gu, Jue Wang, Zhikuang Xin et al.· ACM Transactions on Architec...· 0 citations
Sparse Matrix-Sparse Vector Multiplication (SpMSpV) is a core primitive in graph traversal, sparse linear algebra, and sparse model inference. Its input vector is often dynamically sparse, so the best GPU execution path depends on both global sparsity and the local vector-block distribution. Existing GPU SpMSpV methods often bind storage layouts, push/pull traversal, and kernels together, making fine-grained adaptation difficult without extra storage or scheduling overhead. This paper presents DB-SpMSpV, a dual-view blocked SpMSpV framework for dynamic GPU workloads. DB-SpMSpV partitions the matrix into fixed-size 2D blocks, maintains block-level CSR/CSC views at the high level, and reuses a single low-level block payload to support both row-driven pull and column-driven push. At runtime, it selects the global traversal path based on input block sparsity, chooses block microkernels from the local matrix/vector block structure, and uses load balancing, asynchronous prefetching, and hierarchical writeback to reduce irregular memory accesses, writeback conflicts, and load imbalance. We further integrate the framework into DB-BFS and DB-Decoding. We evaluate DB-SpMSpV on NVIDIA A100 and RTX 4090 using SuiteSparse matrices, symmetric graphs, and three open-source LLMs. Across input sparsities, DB-SpMSpV achieves average speedups of 5.48 × –64.34 × over cuSPARSE and 2.36 × –14.01 × over TileSpMSpV on A100, with similar gains on RTX 4090. DB-BFS further improves end-to-end graph traversal by 2.66 × over TileBFS on A100 and 3.60 × on RTX 4090 on average, while DB-Decoding accelerates single-token linear layers by up to 4.50 ×.
Xing Cong, Chen-Hao Xie, Rui Wang et al.· Proceedings of the Internati...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
