Source-linked AI summary
Fast Convolutional Nets With fbfft: A GPU Performance Evaluation
Nicolas Vasilache, Jeff Johnson, Michael Mathieu, Soumith Chintala, Serkan Piantino, Yann LeCun
TL;DR
Large-scale CNN training requires efficient convolution on GPUs, where direct and frequency-domain methods occupy different performance regimes. The paper develops cuFFT- and fbfft-based FFT convolutions, finding substantial speedups over cuDNN and cuFFT for supported problem sizes. These gains are bounded by fbfft’s square power-of-two convolution support and remaining hardware bottlenecks.
Problem
CNN convolution was computationally expensive for large-scale learning, motivating evaluation of time-domain and frequency-domain performance on NVIDIA GPUs.
Method
The paper implements FFT convolutions using cuFFT and a from-scratch batched 1-D/2-D FFT system, fbfft, integrated with Torch and optimized for deep-learning problem sizes.
Results
FFT convolution outperforms cuDNN across many common layers, while fbfft is ≥1.4× faster than cuFFT transforms and averages 1.51× faster for targeted convolution sizes.
Takeaways & Limitations
FFT convolution is advantageous for some CNN problem sizes, especially large kernels and targeted deep-learning workloads, but direct convolution remains preferable in other regimes.
Takeaways & Limitations
fbfft supports only square power-of-two convolutions, which can cause excessive padding and increased performance and memory costs.
Abstract
from arXiv · showhide
We examine the performance profile of Convolutional Neural Network training on the current generation of NVIDIA Graphics Processing Units. We introduce two new Fast Fourier Transform convolution implementations: one based on NVIDIA's cuFFT library, and another based on a Facebook authored FFT implementation, fbfft, that provides significant speedups over cuFFT (over 1.5x) for whole CNNs. Both of these convolution implementations are available in open source, and are faster than NVIDIA's cuDNN implementation for many common convolutional layers (up to 23.5x for some synthetic kernel configurations). We discuss different performance regimes of convolutions, comparing areas where straightforward time domain convolutions outperform Fourier frequency domain convolutions. Details on algorithmic applications of NVIDIA GPU hardware specifics in the implementation of fbfft are also provided.
1 INTRODUCTION
CNNs became practical for large-scale learning as GPUs reduced their computational burden, motivating GPU convolution implementations that improve performance across many problem sizes.
- CNNs support applications including image recognition, speech processing, and natural language understanding, but their computational expense limited large-scale use.
- GPUs made training large CNNs with millions of weights and massive datasets tractable.
- The paper introduces FFT convolution implementations within Torch using NVIDIA cuFFT/cuBLAS and evaluates them against cuDNN across over 8,000 configurations.
- The proposed FFT implementations significantly outperform cuDNN and other time-domain convolution implementations across a wide range of problem sizes.
- fbfft is an open-source, from-scratch batched 1-D and 2-D FFT implementation developed for limitations encountered with cuFFT in the application domain.
2 CONVOLUTION
The paper contrasts direct and frequency-domain CNN convolution, describing FFT-based complexity advantages while noting that practical performance depends on layer and implementation conditions.
- CNN forward propagation cross-correlates input feature planes with filter kernels to produce output feature planes across minibatch samples.
- Back-propagation convolves output gradients with kernels, while weight-gradient computation updates kernels using loss gradients.
- The default formulation uses valid-only convolution, with optional zero or mirror padding around input margins.
- Matrix unrolling is widely used because matrix multiplication is a tuned primitive, but direct calculation can be faster for some large-batch cases.
- Frequency-domain convolution multiplies Fourier transforms pointwise and can reduce asymptotic complexity relative to direct computation.
- The FFT formulation has complexity O(Sff′n^2 + (Sf + ff′ + Sf′)n^2 log n) instead of O(Sff′n^2k^2) for the stated square case.
- Strided FFT convolutions are not considered in this paper, despite prior work reporting efficient implementations.
3 CUFFT CONVOLUTION IMPLEMENTATION
The cuFFT implementation transforms padded tensors into the frequency domain, uses transposed layouts for batched complex matrix multiplication, and autotunes FFT dimensions and library strategies.
- Inputs, weights, outputs, and gradients are stored as single-precision 4-D tensors in row-major BDHW layout.
- The forward FFT pipeline applies 2-D FFTs, Cgemm multiplication, and inverse FFTs, with analogous implementations for the other convolution passes.
- Zero-padding handles boundaries, aligns operands to a common Fourier basis, and affects FFT choice and non-FFT operation costs.
- Frequency-domain tensors are transposed from BDHW to HWBD for cuBLAS Cgemm, then transposed back before final output processing.
- The implementation clips padded results to the appropriate output size for forward propagation, back-propagation, and weight-gradient computation.
- FFT efficiency depends on transform size, prime-factor decomposition, and batching; unfavorable sizes can reduce efficiency by an order of magnitude.
- cuFFT uses Cooley-Tukey decomposition with specialized radix kernels for sizes involving factors 2, 3, 5, and 7.
- cuBLAS strategy selection varies with batch and matrix size, using batched calls, repeated host launches, or dynamic parallelism.
4 CUFFT CONVOLUTION PERFORMANCE
The evaluation compares cuFFT convolution with strong cuDNN baselines across 8,232 configurations on a Tesla K40m. FFT performance depends strongly on kernel size and problem regime, with small kernels often favoring cuDNN but larger kernels producing substantial speedups.
- Evaluation scope: 8,232 configurations compare cuDNN and cuFFT-based convolution across the 5-D domain {S, f, f′, n, k}.The domain restricts inputs and filters to square spatial dimensions and evaluates configurations summarized by kernel size.
- Evaluation scope: Figures 1–6 summarize cuFFT versus cuDNN performance on a Tesla K40m across 3 × 3 through 13 × 13 kernels.Performance is averaged across all three convolution passes, with problem size represented by Sff′.
- Kernel-size regimes: 1.84× is the top speedup for 3 × 3 convolution at the largest problem sizes, despite generally poor cuFFT performance relative to cuDNN.Launch overhead, repeated memory streaming, and zero-padding can outweigh FFT’s algorithmic advantage for small kernels.
- Kernel-size regimes: 5.33× is the top speedup for 5 × 5 kernels, indicating increasing dominance of the FFT strategy as kernels grow.The paper reports the same tendency for larger kernel sizes.
- Kernel-size regimes: 23.54× is the maximum cuFFT speedup over cuDNN for 13 × 13 kernels.FFT convolutions make large kernels inexpensive and make the performance of the three convolution passes roughly equal.
- CNN performance: 1.4× to 14.5× are the reported cuFFT speedups over cuDNN for representative layer sizes with all data on the GPU.The comparison uses cuDNN for the strided first layer in cuFFT runs, while other layers use cuFFT.
5 fbfft IMPLEMENTATION
fbfft is a from-scratch, GPU-aware FFT implementation designed to avoid cuFFT’s padding and data-movement costs while exploiting warp-level computation. It outperforms cuFFT across relevant 1-D cases and delivers substantial gains in typical CNN workloads, though 2-D performance varies by size and batch regime.
- Motivation and design: cuFFT’s black-box design requires explicit zero-padding, duplicate larger allocations, and copies that significantly affect latency.fbfft instead supports zero-copy clipping and avoids additional memory allocation for conditional out-of-bounds loads.
- Motivation and design: fbfft implements batched 1-D and 2-D FFTs for sizes 2-256, reaching up to 78% efficiency at 97.5% occupancy.The implementation also includes an IFFT kernel based on its FFT kernel.
- Warp-level implementation: Warp-level FFTs use lockstep data and twiddle-factor exchanges, with register-resident computation and a single warp shuffle for bit reversal when n ≤32.This bulk-synchronous approach treats a warp as a small distributed system and performs each exchange with one warp-wide instruction.
- Warp-level implementation: Twiddle-factor handling balances arithmetic intensity against memory bandwidth; loading factors from memory improves performance by 15% at size 16 and 20% at size 32.The arithmetic pipeline is the bottleneck for these two sizes.
- Larger FFT sizes: fbfft outperforms 1-D cuFFT for n ≤256, while register limits reduce occupancy beyond the application range.The hard register limit occurs at n = 512 for 1-D FFT and at 128 and 256 for 2-D FFT.
- Performance evaluation: At typical CNN sizes, fbfft is 1.5×-5× faster than cuFFT, while 2-D gains are more modest and can reverse at size 128 with small batches.For 32 × 32 2-D FFTs, fbfft reaches 1.6× speedup at 1,024 batches; 1-D performance reaches the same ratio only at 16,384 batches.
- Performance evaluation: The 1-D implementation outperforms cuFFT for all cases of interest and reaches 78% efficiency at 97.5% occupancy for size 64 with batch size 16,384.These cases do not exercise implicit zero-copy padding, so integrating the FFT into convolution is expected to provide additional gains.
6 CURRENT LIMITATIONS AND FUTURE WORK
The section identifies memory, instruction-throughput, and shape constraints in fbfft and describes tiling and other optimizations to address them.
- Current limitations: Shuffle-heavy fbfft kernels use only 60% of available memory bandwidth because load/store instructions compete with shuffles for the LSU.On Kepler, 32-bit floating-point multiply-add throughput is 192 per cycle versus 32 for shuffles.
- Memory overhead: Fourier-domain convolutions require temporary frequency and transposed buffers, creating global memory pressure that motivates buffer reuse.Buffer reuse can forgo reusing two hidden-layer FFT results, which would reduce forward-FFT cost by 33%.
- Memory overhead: cuFFT additionally requires explicit padding and plan-reserved temporary memory, whereas fbfft uses implicit padding but supports only square power-of-two convolutions.Excessive padding can adversely affect fbfft performance and memory consumption.
- Tiling: Tiling decomposes a large convolution into smaller convolutions, reducing the cost from O(n log(n)) to O((n + w/d) log(d + w)).The optimal tile size d is of order w, yielding O(n log(w)); limiting concurrent tiles can also reduce scratch-space memory at a possible efficiency cost.
- Tiling: Gradient accumulation cannot reuse the same strategy because it requires a larger convolution between an input of size n and a kernel of size n − w + 1.The authors nevertheless give a similar formula for this operation.
- Future work: Planned optimizations include in-place register transposition, integrated matrix multiplication, and further work on bit-reversal operations.These changes aim to reduce data movement and CUDA kernel-launch overhead.
7 CONCLUSION
The authors report substantial CNN gains from FFT-based convolution and introduce fbfft to better fit deep-learning problem sizes. They also identify ongoing optimizations intended to extend these advantages to larger convolutions.
- Conclusion: 1.4×−14.5× speedups over cuDNN are achieved by the cuFFT convolution implementation for common sizes.The evaluation covers common convolutional configurations reported in the conclusion.
- Conclusion: fbfft is at least 1.4× faster than cuFFT transforms for the deep-learning problems of interest.The implementation is designed for large batches and small feature planes.
- Conclusion: 1.51× mean speedup over cuFFT is reported for fbfft convolution on the sizes the authors aim to exploit.This result concerns convolution rather than standalone FFT transforms.
- Future work: Further bit-twiddling, transposition, pointwise-multiplication, and tiling work is intended to apply the size 8–64 advantage to larger convolution problems.The authors connect these improvements to reduced training time and larger, deeper CNNs.
8 SUPPLEMENT
The supplement details cuFFT performance accounting, FFT foundations, and GPU-specific implementation constraints. It highlights FFT overhead in one layer and explains how radix structure, warp execution, registers, and shuffles shape fbfft design.
- cuFFT convolution performance breakdown: cuFFT performance breakdowns separate FFT, IFFT, and matrix-multiplication steps, while excluding zero-padding copies and adding synchronizations for isolation.FFT and IFFT consume a significant share of compute resources.
- cuFFT convolution performance breakdown: More than 50% of L1 runtime is spent in FFTs because an 11 × 11 kernel is interpolated to 128 × 128.The 128 × 128 size is the minimum used to compute the input FFT without interpolation loss.
- FFT foundations: The discrete Fourier transform projects functions onto a harmonic orthogonal basis, and radix-2 Cooley–Tukey recursively decomposes its computation.The supplement introduces decimation in time and decimation in frequency as alternate decompositions.
- FFT foundations: For power-of-two sizes, DIT and DIF form balanced recursive trees and differ in operation order and whether input or output order is shuffled.Figure 9 contrasts DIT output ordering with DIF input ordering.
- GPU implementation: fbfft depends heavily on Kepler GPU specifics, including warp-level SIMT execution, finite registers and shared memory, and shuffle instructions.Shuffle instructions exchange registers within a warp without shared- or global-memory round trips.
- GPU implementation: Divergent warp branches serialize execution, potentially reducing computational efficiency to 1/32 when all 32 threads follow different paths.This constraint motivates careful CUDA-kernel control flow.
- GPU implementation: Kepler registers support addressable static arrays, but indirect addressing can spill data to local memory; cyclic register distribution enables dynamic shuffle indexing.The supplement illustrates this mechanism with a three-array example spanning 96 warp elements.