# Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Oct 2015.

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

- [Sparsity-Aware Communication for Distributed Graph Neural Network Training](https://mlsanity.com/paper/2504.04673/) (2025)
- [A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral Clustering](https://mlsanity.com/paper/2212.04443/) (2022)
- [NeuraChip: Accelerating GNN Computations with a Hash-based Decoupled Spatial Accelerator](https://mlsanity.com/paper/2404.15510/) (2024)
- [AIRES: Accelerating Out-of-Core GCNs via Algorithm-System Co-Design](https://mlsanity.com/paper/2507.02006/) (2025)
- [Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication](https://mlsanity.com/paper/2510.08874/) (2025)

## Abstract (arXiv)

Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdos-Renyi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first ever implementation of the 3D SpGEMM formulation that also exploits multiple (intra-node and inter-node) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.