Spada: Accelerating Sparse Matrix Multiplication with Adaptive Dataflow
Zhiyao Li, Jiaxiang Li, Taijie Chen, Dimin Niu, Hongzhong Zheng, Yuan Xie, Mingyu Gao
Abstract
Sparse matrix-matrix multiplication (SpGEMM) is widely used in many scientific and deep learning applications. The highly irregular structures of SpGEMM limit its performance and efficiency on conventional computation platforms, and thus motivate a large body of specialized hardware designs. Existing SpGEMM accelerators only support specific types of rigid execution dataflow such as inner/output-product or row-based schemes. Each dataflow is only optimized for certain sparse patterns and fails to generalize with robust performance to the widely diverse SpGEMM workloads across various domains. We propose Spada, a combination of three novel techniques for SpGEMM accelerators to efficiently adapt to various sparse patterns. First, we describe a window-based adaptive dataflow that can be flexibly adapted to different modes to best match the data distributions and realize different reuse benefits. Then, our hardware architecture efficiently supports this dataflow template, with flexible, fast, and low-cost reconfigurability and effective load balancing features. Finally, we use a profiling-guided approach to detect the sparse pattern and determine the optimized dataflow mode to use, based on the key observations of sparse pattern similarity in nearby matrix regions. Our evaluation results demonstrate that Spada is able to match or exceed the best among three state-of-the-art SpGEMM accelerators, and avoid the performance degradation of the others if data distribution and dataflow mismatch. It achieves an average 1.44× speedup across a wide range of sparse matrices and compressed neural network models.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
16 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- EXION: Exploiting Inter-and Intra-Iteration Output Sparsity for Diffusion Models cites MatRaptor: A Sparse-Sparse Matrix Multiplication Accelerator Based on Row-Wise Product
- EXION: Exploiting Inter-and Intra-Iteration Output Sparsity for Diffusion Models cites SIGMA: A Sparse and Irregular GEMM Accelerator with Flexible Interconnects for DNN Training
- EXION: Exploiting Inter-and Intra-Iteration Output Sparsity for Diffusion Models cites SpArch: Efficient Architecture for Sparse Matrix Multiplication
- LoAS: Fully Temporal-Parallel Dataflow for Dual-Sparse Spiking Neural Networks cites MatRaptor: A Sparse-Sparse Matrix Multiplication Accelerator Based on Row-Wise Product
- LoAS: Fully Temporal-Parallel Dataflow for Dual-Sparse Spiking Neural Networks cites SIGMA: A Sparse and Irregular GEMM Accelerator with Flexible Interconnects for DNN Training
- LoAS: Fully Temporal-Parallel Dataflow for Dual-Sparse Spiking Neural Networks cites SpArch: Efficient Architecture for Sparse Matrix Multiplication
- TileFlow: A Framework for Modeling Fusion Dataflow via Tree-based Analysis cites Interstellar: Using Halide's Scheduling Language to Analyze DNN Accelerators
- MatRaptor: A Sparse-Sparse Matrix Multiplication Accelerator Based on Row-Wise Product cites SpArch: Efficient Architecture for Sparse Matrix Multiplication
- Spatula: A Hardware Accelerator for Sparse Matrix Factorization cites SpArch: Efficient Architecture for Sparse Matrix Multiplication
- SPADE: A Flexible and Scalable Accelerator for SpMM and SDDMM cites SIGMA: A Sparse and Irregular GEMM Accelerator with Flexible Interconnects for DNN Training
Cited by top-tier papers16
- TileFlow: A Framework for Modeling Fusion Dataflow via Tree-based AnalysisSize Zheng, Siyuan Chen, Siyuan Gao, Liancheng Jia et al.MICRO 2023 · 31 citations
- SPADE: A Flexible and Scalable Accelerator for SpMM and SDDMMGerasimos Gerogiannis, Serif Yesil, Damitha Lenadora, Dingyuan Cao et al.ISCA 2023 · 27 citations
- LoAS: Fully Temporal-Parallel Dataflow for Dual-Sparse Spiking Neural NetworksRuokai Yin, Youngeun Kim, Di Wu, Priyadarshini PandaMICRO 2024 · 19 citations
- EXION: Exploiting Inter-and Intra-Iteration Output Sparsity for Diffusion ModelsJaehoon Heo, Adiwena Putra, Jieon Yoon, Sungwoong Yune et al.HPCA 2025 · 9 citations
- Spatula: A Hardware Accelerator for Sparse Matrix FactorizationAxel Feldmann, Daniel SánchezMICRO 2023 · 9 citations
Builds on7
- Movement Pruning: Adaptive Sparsity by Fine-TuningVictor Sanh, Thomas Wolf, Alexander M. RushNeurIPS 2020 · 656 citations
- SIGMA: A Sparse and Irregular GEMM Accelerator with Flexible Interconnects for DNN TrainingEric Qin, Ananda Samajdar, Hyoukjun Kwon, Vineet Nadella et al.HPCA 2020 · 490 citations
- SpArch: Efficient Architecture for Sparse Matrix MultiplicationZhekai Zhang, Hanrui Wang, Song Han, William J. DallyHPCA 2020 · 280 citations
- Interstellar: Using Halide's Scheduling Language to Analyze DNN AcceleratorsXuan Yang, Mingyu Gao, Qiaoyi Liu, Jeff Setter et al.ASPLOS 2020 · 237 citations
- MatRaptor: A Sparse-Sparse Matrix Multiplication Accelerator Based on Row-Wise ProductNitish Kumar Srivastava, Hanchen Jin, Jie Liu, David H. Albonesi et al.MICRO 2020 · 223 citations
Related papers
- Misam: Machine Learning Assisted Dataflow Selection in Accelerators for Sparse Matrix MultiplicationSanjali Yadav, Amirmahdi Namjoo, Bahar AsgariMICRO 2025 · 6 citations
- VSpGEMM: Exploiting Versal ACAP for High-Performance SpGEMM AccelerationKai Shi, Zhe Lin, Xinya Luan, Jianwang Zhai et al.DAC 2025 · 1 citation
- Harmonia: A Unified Hierarchical Scheduling Framework for Sparse Matrix MultiplicationJingkui Yang, Fangxin Liu, Xin Ju, Ning Yang et al.ISCA 2026
- ACES: Accelerating Sparse Matrix Multiplication with Adaptive Execution Flow and Concurrency-Aware Cache OptimizationsXiaoyang Lu, Boyu Long, Xiaoming Chen, Yinhe Han et al.ASPLOS 2024 · 13 citations
- A Hardware-Software Design Framework for SpMV Acceleration with Flexible Access Pattern PortfolioZhenyu Wu, Maolin Wang, Hayden Kwok-Hay SoHPCA 2025 · 1 citation
