# A Theory of I/O-Efficient Sparse Neural Network Inference

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 38 references that are in the map.
- First posted on arXiv 3 Jan 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [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)
- [In-Datacenter Performance Analysis of a Tensor Processing Unit](https://mlsanity.com/paper/1704.04760/) (2017)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Efficient Processing of Deep Neural Networks: A Tutorial and Survey](https://mlsanity.com/paper/1703.09039/) (2017)
- [EIE: Efficient Inference Engine on Compressed Deep Neural Network](https://mlsanity.com/paper/1602.01528/) (2016)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [Demystifying Parallel and Distributed Deep Learning: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/1802.09941/) (2018)
- [Data Movement Is All You Need: A Case Study on Optimizing Transformers](https://mlsanity.com/paper/2007.00072/) (2020)
- [Dissecting the NVIDIA Volta GPU Architecture via Microbenchmarking](https://mlsanity.com/paper/1804.06826/) (2018)
- [SparCML: High-Performance Sparse Communication for Machine Learning](https://mlsanity.com/paper/1802.08021/) (2018)
- [EDEN: Enabling Energy-Efficient, High-Performance Deep Neural Network Inference Using Approximate DRAM](https://mlsanity.com/paper/1910.05340/) (2019)
- [Memory- and Communication-Aware Model Compression for Distributed Deep Learning Inference on IoT](https://mlsanity.com/paper/1907.11804/) (2019)
- [CHAOS: A Parallelization Scheme for Training Convolutional Neural Networks on Intel Xeon Phi](https://mlsanity.com/paper/1702.07908/) (2017)
- [Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs](https://mlsanity.com/paper/1707.06343/) (2017)
- [Communication-Optimal Convolutional Neural Nets](https://mlsanity.com/paper/1802.06905/) (2018)

## Abstract (arXiv)

As the accuracy of machine learning models increases at a fast rate, so does their demand for energy and compute resources. On a low level, the major part of these resources is consumed by data movement between different memory units. Modern hardware architectures contain a form of fast memory (e.g., cache, registers), which is small, and a slow memory (e.g., DRAM), which is larger but expensive to access. We can only process data that is stored in fast memory, which incurs data movement (input/output-operations, or I/Os) between the two units. In this paper, we provide a rigorous theoretical analysis of the I/Os needed in sparse feedforward neural network (FFNN) inference. We establish bounds that determine the optimal number of I/Os up to a factor of 2 and present a method that uses a number of I/Os within that range. Much of the I/O-complexity is determined by a few high-level properties of the FFNN (number of inputs, outputs, neurons, and connections), but if we want to get closer to the exact lower bound, the instance-specific sparsity patterns need to be considered. Departing from the 2-optimal computation strategy, we show how to reduce the number of I/Os further with simulated annealing. Complementing this result, we provide an algorithm that constructively generates networks with maximum I/O-efficiency for inference. We test the algorithms and empirically verify our theoretical and algorithmic contributions. In our experiments on real hardware we observe speedups of up to 45× relative to the standard way of performing inference.