# SpArch: Efficient Architecture for Sparse Matrix Multiplication

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

## Key facts

- Cited by 49 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2020.

## Built on by (most cited first, 30 of 49)

- [QuantumNAS: Noise-Adaptive Search for Robust Quantum Circuits](https://mlsanity.com/paper/2107.10845/) (2021)
- [SQuant: On-the-Fly Data-Free Quantization via Diagonal Hessian Approximation](https://mlsanity.com/paper/2202.07471/) (2022)
- [ViTCoD: Vision Transformer Acceleration via Dedicated Algorithm and Accelerator Co-Design](https://mlsanity.com/paper/2210.09573/) (2022)
- [TorchSparse++: Efficient Training and Inference Framework for Sparse Convolution on GPUs](https://mlsanity.com/paper/2311.12862/) (2023)
- [Enable Deep Learning on Mobile Devices: Methods, Systems, and Applications](https://mlsanity.com/paper/2204.11786/) (2022)
- [Dual-side Sparse Tensor Core](https://mlsanity.com/paper/2105.09564/) (2021)
- [QOC: Quantum On-Chip Training with Parameter Shift and Gradient Pruning](https://mlsanity.com/paper/2202.13239/) (2022)
- [Keep the Gradients Flowing: Using Gradient Flow to Study Sparse Network Optimization](https://mlsanity.com/paper/2102.01670/) (2021)
- [S2TA: Exploiting Structured Sparsity for Energy-Efficient Mobile CNN Acceleration](https://mlsanity.com/paper/2107.07983/) (2021)
- [Sparseloop: An Analytical Approach To Sparse Tensor Accelerator Modeling](https://mlsanity.com/paper/2205.05826/) (2022)
- [Oaken: Fast and Efficient LLM Serving with Online-Offline Hybrid KV Cache Quantization](https://mlsanity.com/paper/2503.18599/) (2025)
- [HighLight: Efficient and Flexible DNN Acceleration with Hierarchical Structured Sparsity](https://mlsanity.com/paper/2305.12718/) (2023)
- [Transformer-QEC: Quantum Error Correction Code Decoding with Transferable Transformers](https://mlsanity.com/paper/2311.16082/) (2023)
- [VEGETA: Vertically-Integrated Extensions for Sparse/Dense GEMM Tile Acceleration on CPUs](https://mlsanity.com/paper/2302.08687/) (2023)
- [Reparo: Loss-Resilient Generative Codec for Video Conferencing](https://mlsanity.com/paper/2305.14135/) (2023)
- [No Free Prune: Information-Theoretic Barriers to Pruning at Initialization](https://mlsanity.com/paper/2402.01089/) (2024)
- [LoAS: Fully Temporal-Parallel Dataflow for Dual-Sparse Spiking Neural Networks](https://mlsanity.com/paper/2407.14073/) (2024)
- [Leveraging the true depth of LLMs](https://mlsanity.com/paper/2502.02790/) (2025)
- [SpikingNeRF: Making Bio-inspired Neural Networks See through the Real World](https://mlsanity.com/paper/2309.10987/) (2023)
- [SCATTER: Algorithm-Circuit Co-Sparse Photonic Accelerator with Thermal-Tolerant, Power-Efficient In-situ Light Redistribution](https://mlsanity.com/paper/2407.05510/) (2024)
- [EXION: Exploiting Inter- and Intra-Iteration Output Sparsity for Diffusion Models](https://mlsanity.com/paper/2501.05680/) (2025)
- [GROW: A Row-Stationary Sparse-Dense GEMM Accelerator for Memory-Efficient Graph Convolutional Neural Networks](https://mlsanity.com/paper/2203.00158/) (2022)
- [SGCN: Exploiting Compressed-Sparse Features in Deep Graph Convolutional Network Accelerators](https://mlsanity.com/paper/2301.10388/) (2023)
- [Boosting Pruned Networks with Linear Over-parameterization](https://mlsanity.com/paper/2204.11444/) (2022)
- [DiVa: An Accelerator for Differentially Private Machine Learning](https://mlsanity.com/paper/2208.12392/) (2022)
- [SPADE: Sparse Pillar-based 3D Object Detection Accelerator for Autonomous Driving](https://mlsanity.com/paper/2305.07522/) (2023)
- [MEGA: A Memory-Efficient GNN Accelerator Exploiting Degree-Aware Mixed-Precision Quantization](https://mlsanity.com/paper/2311.09775/) (2023)
- [GPU Semiring Primitives for Sparse Neighborhood Methods](https://mlsanity.com/paper/2104.06357/) (2021)
- [SMASH: Sparse Matrix Atomic Scratchpad Hashing](https://mlsanity.com/paper/2105.14156/) (2021)
- [Towards Memory-Efficient Neural Networks via Multi-Level in situ Generation](https://mlsanity.com/paper/2108.11430/) (2021)

## Abstract (arXiv)

Generalized Sparse Matrix-Matrix Multiplication (SpGEMM) is a ubiquitous task in various engineering and scientific applications. However, inner product based SpGENN introduces redundant input fetches for mismatched nonzero operands, while outer product based approach suffers from poor output locality due to numerous partial product matrices. Inefficiency in the reuse of either inputs or outputs data leads to extensive and expensive DRAM access. To address this problem, this paper proposes an efficient sparse matrix multiplication accelerator architecture, SpArch, which jointly optimizes the data locality for both input and output matrices. We first design a highly parallelized streaming-based merger to pipeline the multiply and merge stage of partial matrices so that partial matrices are merged on chip immediately after produced. We then propose a condensed matrix representation that reduces the number of partial matrices by three orders of magnitude and thus reduces DRAM access by 5.4x. We further develop a Huffman tree scheduler to improve the scalability of the merger for larger sparse matrices, which reduces the DRAM access by another 1.8x. We also resolve the increased input matrix read induced by the new representation using a row prefetcher with near-optimal buffer replacement policy, further reducing the DRAM access by 1.5x. Evaluated on 20 benchmarks, SpArch reduces the total DRAM access by 2.8x over previous state-of-the-art. On average, SpArch achieves 4x, 19x, 18x, 17x, 1285x speedup and 6x, 164x, 435x, 307x, 62x energy savings over OuterSPACE, MKL, cuSPARSE, CUSP, and ARM Armadillo, respectively.