A Decomposable Winograd Method for N–D Convolution Acceleration in Video Analysis

Winograd’s minimal filtering algorithm has been widely used in 2-D Convolutional Neural Networks (CNNs) to reduce the number of multiplications for faster processing. However, it is only effective on convolutions with kernel size as $$3$$ and stride as 1, because it suffers from significantly increased FLOPs and numerical accuracy problems for kernel size larger than $$3$$ and fails on convolution with stride larger than 1. Worse, the extension to N–D convolution will intensify the numerical accuracy problem. These problems severely obstruct Winograd’s minimal filtering algorithm’s application to video analysis. In this paper, we propose a novel Decomposable Winograd Method (DWM) for the N–D convolution acceleration, which breaks through the limitation of original Winograd’s minimal filtering algorithm to more general convolutions. DWM decomposes kernels with large size or stride>1 to several small kernels with stride as 1 for further applying Winograd algorithm, so that DWM can reduce the number of multiplications while keeping the numerical accuracy. It enables the fast exploration of larger kernel size, larger stride value, and higher dimensions in CNNs for high performance and accuracy and even the potential for new CNNs. Comparing against the original Winograd algorithm, the proposed DWM is able to support all kinds of N–D convolutions with a speedup of $$1.44\times $$ – $$3.38\times $$ , without affecting the numerical accuracy.