# Rosko: Row Skipping Outer Products for Sparse Matrix Multiplication Kernels

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 46 references that are in the map.
- First posted on arXiv 8 Jul 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Very Deep Convolutional Networks for Large-Scale Image Recognition](https://mlsanity.com/paper/1409.1556/) (2014)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [MobileNets: Efficient Convolutional Neural Networks for Mobile Vision Applications](https://mlsanity.com/paper/1704.04861/) (2017)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks](https://mlsanity.com/paper/1803.03635/) (2018)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Learning Efficient Convolutional Networks through Network Slimming](https://mlsanity.com/paper/1708.06519/) (2017)
- [Rigging the Lottery: Making All Tickets Winners](https://mlsanity.com/paper/1911.11134/) (2019)
- [Learning N:M Fine-grained Structured Sparse Neural Networks From Scratch](https://mlsanity.com/paper/2102.04010/) (2021)
- [Drawing Early-Bird Tickets: Towards More Efficient Training of Deep Networks](https://mlsanity.com/paper/1909.11957/) (2019)
- [Structured Pruning of Deep Convolutional Neural Networks](https://mlsanity.com/paper/1512.08571/) (2015)
- [Sparse GPU Kernels for Deep Learning](https://mlsanity.com/paper/2006.10901/) (2020)
- [Data Movement Is All You Need: A Case Study on Optimizing Transformers](https://mlsanity.com/paper/2007.00072/) (2020)
- [EarlyBERT: Efficient BERT Training via Early-bird Lottery Tickets](https://mlsanity.com/paper/2101.00063/) (2020)
- [SpArch: Efficient Architecture for Sparse Matrix Multiplication](https://mlsanity.com/paper/2002.08947/) (2020)
- [Block-Sparse Recurrent Neural Networks](https://mlsanity.com/paper/1711.02782/) (2017)
- [FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems](https://mlsanity.com/paper/2008.11359/) (2020)
- [Dual-side Sparse Tensor Core](https://mlsanity.com/paper/2105.09564/) (2021)
- [SparseDNN: Fast Sparse Deep Learning Inference on CPUs](https://mlsanity.com/paper/2101.07948/) (2021)

## Abstract (arXiv)

We propose Rosko -- row skipping outer products -- for deriving sparse matrix multiplication (SpMM) kernels in reducing computation and memory access requirements of deep neural networks (DNNs). Rosko allows skipping of entire row computations during program execution with low sparsity-management overheads. We analytically derive sparse CPU kernels that adapt to given hardware characteristics to effectively utilize processor cores and minimize data movement without the need for auto-tuning or search space exploration. Rosko can be integrated with other outer product scheduling methods, allowing them to leverage row skipping by using Rosko's packing format to skip unnecessary computation. Rosko kernels outperform existing auto-tuning and search-based solutions as well as state-of-the-art vendor-optimized libraries on real hardware across a variety of neural network workloads. For matrices with sparsities ranging from 65% to 99.8% typically found in machine learning, Rosko kernels achieve up to a 6.5x runtime reduction on Intel and ARM CPUs.