# High Performance Convolution Using Sparsity and Patterns for Inference in Deep Convolutional Neural Networks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 41 references that are in the map.
- First posted on arXiv 16 Apr 2021.

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

- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [Going Deeper with Convolutions](https://mlsanity.com/paper/1409.4842/) (2014)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Identity Mappings in Deep Residual Networks](https://mlsanity.com/paper/1603.05027/) (2016)
- [Inception-v4, Inception-ResNet and the Impact of Residual Connections on Learning](https://mlsanity.com/paper/1602.07261/) (2016)
- [Pruning Filters for Efficient ConvNets](https://mlsanity.com/paper/1608.08710/) (2016)
- [Learning Structured Sparsity in Deep Neural Networks](https://mlsanity.com/paper/1608.03665/) (2016)
- [Sparsity in Deep Learning: Pruning and growth for efficient inference and training in neural networks](https://mlsanity.com/paper/2102.00554/) (2021)
- [Meta Pseudo Labels](https://mlsanity.com/paper/2003.10580/) (2020)
- [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)
- [Dynamic Network Surgery for Efficient DNNs](https://mlsanity.com/paper/1608.04493/) (2016)
- [SCNN: An Accelerator for Compressed-sparse Convolutional Neural Networks](https://mlsanity.com/paper/1708.04485/) (2017)
- [Communication-Efficient Edge AI: Algorithms and Systems](https://mlsanity.com/paper/2002.09668/) (2020)
- [Fast ConvNets Using Group-wise Brain Damage](https://mlsanity.com/paper/1506.02515/) (2015)
- [Faster CNNs with Direct Sparse Convolutions and Guided Pruning](https://mlsanity.com/paper/1608.01409/) (2016)
- [Compressing DMA Engine: Leveraging Activation Sparsity for Training Deep Neural Networks](https://mlsanity.com/paper/1705.01626/) (2017)
- [Accelerating Convolutional Neural Networks via Activation Map Compression](https://mlsanity.com/paper/1812.04056/) (2018)
- [Pre-defined Sparsity for Low-Complexity Convolutional Neural Networks](https://mlsanity.com/paper/2001.10710/) (2020)
- [MEC: Memory-efficient Convolution for Deep Neural Network](https://mlsanity.com/paper/1706.06873/) (2017)
- [Escoin: Efficient Sparse Convolutional Neural Network Inference on GPUs](https://mlsanity.com/paper/1802.10280/) (2018)
- [Speeding up Convolutional Neural Networks By Exploiting the Sparsity of Rectifier Units](https://mlsanity.com/paper/1704.07724/) (2017)
- [Caffe con Troll: Shallow Ideas to Speed Up Deep Learning](https://mlsanity.com/paper/1504.04343/) (2015)

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

- [DataDAM: Efficient Dataset Distillation with Attention Matching](https://mlsanity.com/paper/2310.00093/) (2023)
- [ProbMCL: Simple Probabilistic Contrastive Learning for Multi-label Visual Classification](https://mlsanity.com/paper/2401.01448/) (2024)
- [ATOM: Attention Mixer for Efficient Dataset Distillation](https://mlsanity.com/paper/2405.01373/) (2024)

## Abstract (arXiv)

Deploying deep Convolutional Neural Networks (CNNs) is impacted by their memory footprint and speed requirements, which mainly come from convolution. Widely-used convolution algorithms, im2col and MEC, produce a lowered matrix from an activation map by redundantly storing the map's elements included at horizontal and/or vertical kernel overlappings without considering the sparsity of the map. Using the sparsity of the map, this paper proposes two new convolution algorithms dubbed Compressed Pattern Overlap (CPO) and Compressed Pattern Sets (CPS) that simultaneously decrease the memory footprint and increase the inference speed while preserving the accuracy. CPO recognizes non-zero elements (NZEs) at horizontal and vertical overlappings in the activation maps. CPS further improves the memory savings of CPO by compressing the index positions of neighboring NZEs. In both algorithms, channels/regions of the activation maps with all zeros are skipped. Then, CPO/CPS performs convolution via Sparse Matrix-Vector Multiplication (SpMv) done on their sparse representations. Experimental results conducted on CPUs show that average per-layer time savings reach up to 63% and Compression Ratio (CR) up to 26x with respect to im2col. In some layers, our average per layer CPO/CPS time savings are better by 28% and CR is better by 9.2x than the parallel implementation of MEC. For a given CNN's inference, we offline select for each convolution layer the best convolutional algorithm in terms of time between either CPO or CPS and im2col. Our algorithms were selected up to 56% of the non-pointwise convolutional layers. Our offline selections yield CNN inference time savings up to 9% and CR up to 10x.