📄 Fast Algorithms for Convolutional Neural Networks

Summary

Vision convnets are costly to run. Low-latency inference, mobile deployment and distributed training with small per-node batches all need convolution that stays fast with tiny 3×3 filters and small batches. FFT-based convolution suits large filters and big batches, so it fits this regime poorly. Lavin and Gray adapt Winograd's minimal filtering algorithms to convnet layers. Images are split into overlapping tiles, and both tiles and filters are mapped into a transform domain. They are multiplied element-wise there and then mapped back. Summing over input channels before the inverse transform turns most of the arithmetic into dense matrix multiplications, which stay efficient even at batch size 1. The authors derive F(2×2,3×3) and F(4×4,3×3) for the forward pass, plus F(3×3,2×2) for weight gradients, and analyse numeric error. They benchmark a Titan X GPU kernel for F(2×2,3×3) on VGG Network E against cuDNN v3. It wins at every batch size from 1 to 64 and needs little extra memory, showing that algebraic restructuring can substantially accelerate modern convnets.

Key points

• Multiplication savings:
  • F(2×2,3×3) uses 16 multiplications per output tile instead of 36, a 2.25× arithmetic reduction.
  • F(4×4,3×3) uses 36 instead of 144, a 4× reduction.
  • The cost is that transform overhead and numeric error grow with tile size.
• Hardware and metric: The test GPU was a Titan X with 6.96 TFLOPS device peak. Speed is reported as "Effective TFLOPS," meaning direct-convolution FLOPs divided by runtime, so it can exceed peak.
• Speed with fp32:
  • F(2×2,3×3) beats cuDNN by 2.26× at N=1 and 1.48× at N=64.
  • The biggest gains, up to 7.28×, occur at intermediate N, where cuDNN chose a slow FFT path.
  • Throughput at N=16 is 9.49 TFLOPS.
• Speed with fp16: F(2×2,3×3) reaches 10.28 TFLOPS at N=64 and 9.57 TFLOPS at N=8.
• Memory and accuracy:
  • cuDNN's FFT path used up to 2.6 GB of workspace. The fused Winograd kernel needs none, and the external-filter-transform (FX) variant needs at most 16 MB.
  • In fp32, F(2×2,3×3) is slightly more accurate than direct convolution.
  • F(4×4,3×3) has larger error but remains more accurate than direct convolution on fp16 data.

Interesting ideas

• I1. Reduce before the inverse transform. Doing the channel reduction inside the transform domain spreads the inverse-transform cost over all channels. It also turns the core work into batched matrix multiplies. Reorganizing a computation so its heavy part becomes GEMM is a widely reusable trick for getting efficient hardware utilization.
• I2. Measure speed in algorithm-independent units. Normalizing every method by the FLOPs of the naive algorithm makes fast algorithms directly comparable with baselines. It also exposes when an algorithmic saving beats raw hardware peak, which is useful for any benchmark of approximate or fast methods.
• I3. Test accuracy against a high-precision reference. Error was measured on random uniform inputs, with direct convolution in double precision as ground truth. This gives a cheap, model-independent way to check that a numerically riskier method stays within the tolerance a low-precision model already accepts.
• I4. Split one huge convolution into many small ones. The weight gradient would require an impractically large filtering problem. The authors break it into a sum of small tiled convolutions such as F(3×3,2×2), which shows how a size mismatch can be fixed by tiling rather than by a new algorithm.
• I5. Choose the kernel variant per layer. Precomputing the filter transform (FX) or fusing it into the main kernel works better depending on filter and channel counts. Selecting the variant per layer, with workspace size treated as a first-class constraint, is a sensible design habit for performance libraries.