Fast Algorithms for Convolutional Neural Networks

By Andrew Lavin, Scott Gray. 2015

965 citations recorded by the source corpus.

Deep convolutional neural networks take GPU-days of computation to train on large data sets. Pedestrian detection for self driving cars requires very low latency. Image recognition for mobile phones is constrained by limited processing resources. The success of convolutional neural networks in these situations is limited by how fast we can compute them. Conventional FFT based convolution is fast for large filters, but state of the art convolutional neural networks use small, 3 3 filters. We introduce a new class of fast algorithms for convolutional neural networks using Winograd's minimal filtering algorithms. The algorithms compute minimal complexity convolution over small tiles, which makes them fast with small filters and small batch sizes. We benchmark a GPU implementation of our algorithm with the VGG network and show state of the art throughput at batch sizes from 1 to 64.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Efficiency & Compression

Citations in the corpus

Can Active Memory Replace Attention? (2016, methodology): “At each step of the decoder, a probability distribution over this memory is computed and used to estimate a weighted average encoder representation to be used as input to the next decoder step.”
Rethinking the Inception Architecture for Computer Vision (2015, background): “It is certainly possible to mitigate parts of these issues by applying specialized solutions to target memory use [2], [15] or by optimizing the execution of certain operations via computational tricks [10].”
Neural GPUs Learn Algorithms (2015, methodology): “New work on faster convolutions, e.g., Lavin & Gray (2015), can be directly used in a Neural GPU.”
PyTorch: An Imperative Style, High-Performance Deep Learning Library (2019, background): “massively parallel hardware such as GPUs provided the computing power required by deep learning methods. Specialized libraries such as cuDNN [22], along with a body of academic work (such as [23] and [24]), produced a set of high-performance reusable deep learning kernels that enabled frameworks suc”
TensorFlow: A system for large-scale machine learning (2016, neutral): “The Neon library [56] outperforms TensorFlow on three of the models, by using handoptimized convolutional kernels [44] implemented in assembly language; in principle, we could implement these kernels in TensorFlow, but we have not yet done so.”
Pruning Filters for Efficient ConvNets (2016, background): “Lebedev & Lempitsky (2016) leverage group-sparsity on the convolutional filters to achieve structured brain damage, i.e., prune the entries of the convolution kernel in a group-wise fashion.”
Recent advances in convolutional neural networks (2015, background): “tional lters have become an important component in CNNs such as ResNet [11] and GoogleNet [10], which makes a new approach specialized for small lter sizes: Winograd's minimal ltering algorithms [157]. The insight of Winograd is like FFT, the Winograd convolutions can be reduced across channels”
AMC: AutoML for Model Compression and Acceleration on Mobile Devices (2018, background): “10, 41] and special convolution implementations [36, 48, 29, 3] can also speed up the neural networks.”
Group Equivariant Convolutional Networks (2016, methodology): “Here we present the details for a G-convolution implementation that can leverage recent advances in fast computation of planar convolutions (Mathieu et al., 2014; Vasilache et al., 2015; Lavin & Gray, 2015).”
Gradient Sparsification for Communication-Efficient Distributed Optimization (2017, methodology): “volutional neural networks on the CIFAR10 1 dataset. We implement our method using the neon framework 2 provided by Intel Nervana System. The convolution operator is accelerated by winograd algorithm [11]. We experiment with neural networks using dierent settings. generally, the network consists of ”
Channel Pruning for Accelerating Very Deep Neural Networks (2017, methodology): “Optimized implementation based methods [36, 48, 27, 4] accelerate convolution, with special convolution algorithms like FFT [48].”
EIE: Efficient Inference Engine on Compressed Deep Neural Network (2016, background): “25 × multiplications than naive convolution [33], and for each Winograd patch the 16 M × V can be scheduled on an EIE.”
A ConvNet for the 2020s (2022, methodology): “While large kernel sizes have been used in the past with ConvNets [40,68], the gold standard (popularized by VGGNet [65]) is to stack small kernel-sized (3 × 3) conv layers, which have efﬁcient hardware implementations on modern GPUs [41].”
Scaling Local Self-Attention for Parameter Efficient Visual Backbones (2021, background): “Convolutions have improved over the last decade through changes in (a) the computation of the primitive [4, 25, 34, 52, 56, 28]; (b) the software implementation [5]; (c) the structure of the primitive itself, through for example, grouped convolution [57] and depthwise separable convolution [45].”
Demystifying Parallel and Distributed Deep Learning (2018, methodology): “First proposed by Lavin and Gray [146], the method modifies the original algorithm for multiple filters (as is the case in convolutions), performing the following computation for one tile: yi, j,∗,∗ = A T Cin∑ m=0 Gw j,m,∗,∗G T ◦ BTxi,m,∗,∗B A, with the matrices A,G,B constructed as in Winograd’s al”
BranchyNet: Fast inference via early exiting from deep neural networks (2016, neutral): “(2015) have introduced faster algorithms specifically for 3x3 convolutional filters (which are used extensively in VGGNet and ResNet) [14].”
Sparse GPU Kernels for Deep Learning (2020, methodology): “[51] develop a technique for inducing sparsity in Winograd convolutions [52] and design and efficient implementation for CPUs.”
Learning in the Frequency Domain (2020, methodology): “Extensive efforts need to be taken to optimize the computation efficiency of these FFT-based CNN models [31].”