# Design Principles for Sparse Matrix Multiplication on the GPU

arXiv: https://arxiv.org/abs/1803.08601 · HTML: https://mlsanity.com/paper/1803.08601/

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Mar 2018.

## Built on by (most cited first, 19 of 19)

- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [SparseTIR: Composable Abstractions for Sparse Compilation in Deep Learning](https://mlsanity.com/paper/2207.04606/) (2022)
- [Accel-GCN: High-Performance GPU Accelerator Design for Graph Convolution Networks](https://mlsanity.com/paper/2308.11825/) (2023)
- [An Efficient Sparse Kernel Generator for O(3)-Equivariant Deep Networks](https://mlsanity.com/paper/2501.13986/) (2025)
- [Do We Need Anisotropic Graph Neural Networks?](https://mlsanity.com/paper/2104.01481/) (2021)
- [SparseDNN: Fast Sparse Deep Learning Inference on CPUs](https://mlsanity.com/paper/2101.07948/) (2021)
- [Exploiting Sparsity in Pruned Neural Networks to Optimize Large Model Training](https://mlsanity.com/paper/2302.05045/) (2023)
- [BitGNN: Unleashing the Performance Potential of Binary Graph Neural Networks on GPUs](https://mlsanity.com/paper/2305.02522/) (2023)
- [PopSparse: Accelerated block sparse matrix multiplication on IPU](https://mlsanity.com/paper/2303.16999/) (2023)
- [PyGim: An Efficient Graph Neural Network Library for Real Processing-In-Memory Architectures](https://mlsanity.com/paper/2402.16731/) (2024)
- [Accelerating SpMM Kernel with Cache-First Edge Sampling for Graph Neural Networks](https://mlsanity.com/paper/2104.10716/) (2021)
- [On the Interaction of Compressibility and Adversarial Robustness](https://mlsanity.com/paper/2507.17725/) (2025)
- [SUBP: Soft Uniform Block Pruning for 1xN Sparse CNNs Multithreading Acceleration](https://mlsanity.com/paper/2310.06218/) (2023)
- [Optimization of GNN Training Through Half-precision](https://mlsanity.com/paper/2411.01109/) (2024)
- [Plexus: Taming Billion-edge Graphs with 3D Parallel Full-graph GNN Training](https://mlsanity.com/paper/2505.04083/) (2025)
- [GeoT: Tensor Centric Library for Graph Neural Network via Efficient Segment Reduction on GPU](https://mlsanity.com/paper/2404.03019/) (2024)
- [HopFormer: Sparse Graph Transformers with Explicit Receptive Field Control](https://mlsanity.com/paper/2602.02268/) (2026)
- [Scalable Optimal Transport Algorithm for Network Alignment](https://mlsanity.com/paper/2607.11952/) (2026)
- [Beyond Masked Sparsity: SNACK Enables Truly Sparse Neural Networks on GPU](https://mlsanity.com/paper/2610.04093/) (2026)

## Abstract (arXiv)

We implement two novel algorithms for sparse-matrix dense-matrix multiplication (SpMM) on the GPU. Our algorithms expect the sparse input in the popular compressed-sparse-row (CSR) format and thus do not require expensive format conversion. While previous SpMM work concentrates on thread-level parallelism, we additionally focus on latency hiding with instruction-level parallelism and load-balancing. We show, both theoretically and experimentally, that the proposed SpMM is a better fit for the GPU than previous approaches. We identify a key memory access pattern that allows efficient access into both input and output matrices that is crucial to getting excellent performance on SpMM. By combining these two ingredients---(i) merge-based load-balancing and (ii) row-major coalesced memory access---we demonstrate a 4.1x peak speedup and a 31.7% geomean speedup over state-of-the-art SpMM implementations on real-world datasets.