Source-linked AI summary
Fast Algorithms for Convolutional Neural Networks
Andrew Lavin, Scott Gray
TL;DR
Deep convolutional networks are computationally expensive to train and deploy, while important applications require fast inference with small filters and batch sizes. The paper introduces Winograd-based minimal filtering algorithms over small tiles and benchmarks a GPU implementation. The implementation achieves state-of-the-art throughput across batch sizes from 1 to 64, with reduced arithmetic complexity and limited workspace requirements.
Problem
Convolutional networks require substantial computation, while conventional libraries are optimized for large filters and batch sizes despite modern workloads using small filters and sometimes small batches.
Method
The paper uses Winograd minimal filtering algorithms over small tiles, applying the same approach to forward propagation and convolutional gradients.
Results
The GPU implementation achieves state-of-the-art throughput for batch sizes from 1 to 64, including 2.26X speed at N = 1 for fp32 F(2 × 2, 3 × 3).
Takeaways & Limitations
Winograd-based convolution supports high throughput for small filters and small batch sizes while reducing arithmetic complexity and workspace requirements.
Takeaways & Limitations
Large tiles can lose their multiplication savings because transform additions and constant multiplications increase quadratically; GPU on-chip memory also limits efficient multiply dimensions.
Abstract
from arXiv · showhide
Deep convolutional neural networks take GPU days of compute time 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, 3x3 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.
1. Introduction
Convolutional networks deliver strong image-recognition results but impose substantial computational demands, especially for low-latency inference and small-batch, small-filter workloads. The paper introduces Winograd-based algorithms to address these constraints while achieving high GPU throughput.
- Convolutional networks achieve state-of-the-art image-recognition results but can require several days of GPU training and substantial classification resources.Larger datasets and models improve accuracy while increasing computation time.
- Low-latency applications such as pedestrian detection are limited by the speed of classifying a small set of images, potentially a single image.
- Distributed training is constrained because large batch sizes harm convergence, limiting the minimum efficiently computable batch size and therefore cluster size.
- Modern image-recognition architectures favor deep 3 × 3 convolutional layers because they achieve better accuracy with fewer weights than shallow networks using larger filters.
- Fast algorithms are needed for small batch sizes and small filters, whereas conventional convolution libraries operate efficiently with large batches and filters.
- Winograd-based algorithms reduce layer arithmetic complexity by up to 4× and achieve state-of-the-art throughput for batch sizes from 1 to 64.The implementation uses at most 16MB of workspace memory.
2. Related Work
Prior work reduced convolutional complexity using FFT-based methods, fast matrix multiplication, and approximation techniques. This paper positions algebraic-structure methods as distinct from quantization and other approximations.
- FFT-based convolution methods reduce convolutional arithmetic complexity and were refined through implementations such as NVIDIA cuDNN.
- The Strassen algorithm was applied to reduce the number of convolutions in a convnet layer and its total arithmetic complexity.The work also proposed exploring additional arithmetic-complexity techniques for convnets.
- Quantization and other approximation methods are treated as orthogonal and complementary to approaches exploiting algebraic structure, and are outside this paper’s scope.
3. Convolutional Neural Networks
A convolutional neural-network layer correlates a bank of filters with a minibatch of multi-channel images. The paper formalizes this computation for individual outputs and complete image/filter pairs using 2D correlation.
- A convnet layer correlates K filters with C-channel images in a minibatch of N examples.Filters have size R × S, while images have spatial dimensions H × W.
- The layer’s computation produces an individual output element Yi,k,x,y from the corresponding image and filter data.
- The computation can also be written for an entire image/filter pair.
- The operator ∗ in the layer formulation denotes 2D correlation.
4. Fast Algorithms
Winograd minimal filtering algorithms reduce convolution arithmetic by operating on small tiles, while expressing most computation as efficient matrix multiplication. The approach extends to training gradients and offers substantial savings over direct convolution, but larger tiles increase transform cost and reduce numerical accuracy.
- Minimal filtering: Winograd minimal filtering computes m outputs with an r-tap filter using m + r − 1 multiplications, and nesting yields minimal multidimensional algorithms.The construction extends from one-dimensional filters to two-dimensional and multidimensional FIR filters.
- Small-tile algorithms: F(2×2, 3×3) uses 16 multiplications versus 36 for direct convolution, a 2.25-fold arithmetic complexity reduction.The corresponding transforms use 32 data additions, 28 filter-transform floating-point instructions, and 24 inverse-transform additions.
- Practical implementation: The transformed convolution reduces over channels before applying the inverse transform, amortizing inverse-transform cost across channels and yielding a matrix multiplication implementation.Matrix multiplication has efficient implementations on CPU, GPU, and FPGA platforms because of its high computational intensity.
- Training: The same algorithms compute input gradients during backpropagation, while weight gradients are decomposed into smaller convolutions such as F(3 × 3, 2 × 2).For F(3 × 3, 2 × 2), 16 multiplications replace 36 direct-convolution multiplications, again giving a 2.25-fold reduction.
- Larger tiles: F(4×4, 3×3) uses 36 multiplications versus 144 for the standard algorithm, reducing arithmetic complexity by a factor of 4.Its two-dimensional transforms require 156 data-transform, 72 filter-transform, and 100 inverse-transform floating-point instructions.
- Limitations: Transform additions and constant multiplications grow quadratically with tile size, eventually overwhelming multiplication savings; larger transforms also reduce numerical accuracy.The paper notes that convnets may tolerate some numerical inaccuracy and examines F(6 × 6, 3 × 3) in supplementary material.
5. Arithmetic Complexity Analysis
The analysis models arithmetic complexity across multiplication and transform stages, showing why Winograd convolution can reduce computation for small filters while FFT methods face tile and memory trade-offs.
- When m = n = 1, direct convolution is minimal for F(1 × 1, R × S).
- P = NHW/m^2 is the number of tiles per channel in the complexity model.
- Large speedups require low multiplication complexity and transform complexities small relative to K, P, and C.
- For direct convolution, the maximum speedup of a fast algorithm is R^2/α′ because α′ = R^2 and transform complexities are zero.
- FFT direct-CGEMM layers need at least 64 × 64 tiles to match Winograd F(4 × 4, 3 × 3) multiplication complexity, increasing transform overhead and unwanted computation.
- FFT implementations also require larger transformed-data workspaces, which is problematic on GPUs with limited on-chip memory.
6. GPU Implementation
The GPU implementation fuses Winograd stages and uses blocking, memory-layout, and precision strategies to support efficient computation with small tiles and batches.
- The implementation targets F(2 × 2, 3 × 3) on NVIDIA Maxwell GPUs using an NVIDIA Titan X.
- Fused execution combines data and filter transforms, 16 batched GEMMs, and the inverse transform within one block.
- The 16 batched GEMMs compute 32 × 32 outputs while keeping workspace in registers and shared memory with two active blocks per SM.
- CHWN storage and super blocking provide contiguous, aligned loads across images or tiles, including when batch size is below 32.
- L2 cache blocking reuses overlapping image tiles and loads each filter once from DDR memory within groups of up to 128 filters.
- The FX variant stores transformed filters in a workspace requiring 16KC units, equal to 16MB when K = C = 512 with fp32 data.
7. Experiments
Experiments evaluate accuracy and speed on VGG Network E, whose convolutional layers exclusively use 3 × 3 filters, comparing the GPU implementation with cuDNN.
- VGG Network E provides the experimental network and uses 3 × 3 filters exclusively in its convolution layers.
- Accuracy tests use fp32 and fp16 data and filters while performing all arithmetic with fp32 instructions.
- Accuracy is measured as absolute element error against direct convolution using a double-precision accumulator for reductions.
- Speed is measured for F(2 × 2, 3 × 3) on a superclocked NVIDIA Titan X and compared with cuDNN v3.
- Layer speed is reported as Effective TFLOPS, calculated from direct-convolution GFLOPs divided by runtime in milliseconds.
- Network throughput combines depth-weighted GFLOPs and runtime across layers.
8. Results
The Winograd F(2 × 2, 3 × 3) algorithms achieve high throughput across VGG layers and batch sizes while maintaining accuracy comparable to or better than direct convolution. They also reduce memory use and outperform cuDNN broadly, including at small batch sizes.
- Network throughput: 2.26X as fast as cuDNN at N = 1 and 1.48X at N = 64 for fp32 VGG data, with 9.49 TFLOPS at N = 16.For fp16 data, throughput reaches 10.28 TFLOPS at N = 64 and 9.57 TFLOPS at N = 8.
- Network throughput: F(2 × 2, 3 × 3) performs better than cuDNN at every layer and batch size except conv1.1, which contributes less than 0.5% of total network computation.The comparison covers layer throughput across batch sizes, with cuDNN selecting FFT for some layers.
- Implementation behavior: The FX variant generally performs best, except when filter and channel counts are very large because filter transformation is heavily memory bound.Transforming a larger filter bank decreases computational efficiency.
- Layer behavior: Over 5 TFLOPS versus 1.6 TFLOPS for cuDNN on the worst F(2 × 2, 3 × 3) case: 14×14 layers with N = 1.The slowdown arises because the 8×4 superblock crosses the image boundary and computes unwanted pixels.
- Memory use: No global workspace is used by the fused implementation, while the FX variant uses no more than 16 MB versus up to 2.6 GB for cuDNN FFT.The reduced memory requirement contrasts with cuDNN FFT's large global workspace in these experiments.
- Accuracy: F(2 × 2, 3 × 3) is more accurate than direct convolution with fp32 data, while all tested algorithms are equally accurate with fp16 data.F(4 × 4, 3 × 3) has larger error but remains more accurate than direct convolution with fp16 data.