# SMASH: Sparse Matrix Atomic Scratchpad Hashing

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 115 references that are in the map.
- First posted on arXiv 29 May 2021.

## Builds on (most cited first, 20 of 20)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [cuDNN: Efficient Primitives for Deep Learning](https://mlsanity.com/paper/1410.0759/) (2014)
- [Mesh-TensorFlow: Deep Learning for Supercomputers](https://mlsanity.com/paper/1811.02084/) (2018)
- [SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks](https://mlsanity.com/paper/1708.04485/) (2017)
- [N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification](https://mlsanity.com/paper/1802.08888/) (2018)
- [SpArch: Efficient Architecture for Sparse Matrix Multiplication](https://mlsanity.com/paper/2002.08947/) (2020)
- [Deep Learning Inference in Facebook Data Centers: Characterization, Performance Optimizations and Hardware Implications](https://mlsanity.com/paper/1811.09886/) (2018)
- [Parallel Multi Channel Convolution using General Matrix Multiplication](https://mlsanity.com/paper/1704.04428/) (2017)
- [Systolic Tensor Array: An Efficient Structured-Sparse GEMM Accelerator for Mobile CNN Inference](https://mlsanity.com/paper/2005.08098/) (2020)
- [Packing Sparse Convolutional Neural Networks for Efficient Systolic Array Implementations: Column Combining Under Joint Optimization](https://mlsanity.com/paper/1811.04770/) (2018)
- [Architectural Implications of Graph Neural Networks](https://mlsanity.com/paper/2009.00804/) (2020)
- [StrassenNets: Deep Learning with a Multiplication Budget](https://mlsanity.com/paper/1712.03942/) (2017)
- [Bandwidth-Optimized Parallel Algorithms for Sparse Matrix-Matrix Multiplication using Propagation Blocking](https://mlsanity.com/paper/2002.11302/) (2020)
- [Autonomous collision attack on OCSP services](https://mlsanity.com/paper/1609.03047/) (2016)
- [Linear Work Generation of R-MAT Graphs](https://mlsanity.com/paper/1905.03525/) (2019)
- [Synergistic CPU-FPGA Acceleration of Sparse Linear Algebra](https://mlsanity.com/paper/2004.13907/) (2020)
- [Performance Optimization of SU3_Bench on Xeon and Programmable Integrated Unified Memory Architecture](https://mlsanity.com/paper/2103.00571/) (2021)

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

- [MaxK-GNN: Extremely Fast GPU Kernel Design for Accelerating Graph Neural Networks Training](https://mlsanity.com/paper/2312.08656/) (2023)
- [Path Planning using Reinforcement Learning: A Policy Iteration Approach](https://mlsanity.com/paper/2303.07535/) (2023)
- [NeuraChip: Accelerating GNN Computations with a Hash-based Decoupled Spatial Accelerator](https://mlsanity.com/paper/2404.15510/) (2024)

## Abstract (arXiv)

Sparse matrices, more specifically SpGEMM kernels, are commonly found in a wide range of applications, spanning graph-based path-finding to machine learning algorithms (e.g., neural networks). A particular challenge in implementing SpGEMM kernels has been the pressure placed on DRAM memory. One approach to tackle this problem is to use an inner product method for the SpGEMM kernel implementation. While the inner product produces fewer intermediate results, it can end up saturating the memory bandwidth, given the high number of redundant fetches of the input matrix elements. Using an outer product-based SpGEMM kernel can reduce redundant fetches, but at the cost of increased overhead due to extra computation and memory accesses for producing/managing partial products. In this thesis, we introduce a novel SpGEMM kernel implementation based on the row-wise product approach. We leverage atomic instructions to merge intermediate partial products as they are generated. The use of atomic instructions eliminates the need to create partial product matrices. To evaluate our row-wise product approach, we map an optimized SpGEMM kernel to a custom accelerator designed to accelerate graph-based applications. The targeted accelerator is an experimental system named PIUMA, being developed by Intel. PIUMA provides several attractive features, including fast context switching, user-configurable caches, globally addressable memory, non-coherent caches, and asynchronous pipelines. We tailor our SpGEMM kernel to exploit many of the features of the PIUMA fabric. This thesis compares our SpGEMM implementation against prior solutions, all mapped to the PIUMA framework. We briefly describe some of the PIUMA architecture features and then delve into the details of our optimized SpGEMM kernel. Our SpGEMM kernel can achieve 9.4x speedup as compared to competing approaches.