A Fast Algorithm for Convolutional Neural Networks Using Tile-based Fast Fourier Transforms

摘要

State-of-the-art convolution algorithms accelerate training of convolutional neural networks (CNNs) by decomposing convolutions in time or Fourier domain, these decomposition implementations are designed for small filters or large inputs, respectively. We take these two aspects into account, devote to a novel decomposition strategy in Fourier domain and propose a conceptually useful algorithm for accelerating CNNs. We extend the classical Fast Fourier Transform theory to meet the requirements of convolving large inputs with small filters in faster manner. The tile-based decomposition strategy is introduced into Fourier transforms to yield a fast convolution algorithm. The algorithm, called tFFT, is simple to program, implementing tile sized transformations in Fourier domain to minimize convolution time for modern CNNs. tFFT reduces the arithmetic complexity of CNNs by over a factor of 3 compared to FFT-based convolution algorithms. We evaluate the performance of tFFT by implementing it on a set of state-of-the-art CNNs, the experiments show good results at batch sizes from 1 to 128.