Convolution is the core operation for many deep neural networks. The Winograd convolution algorithms have been shown to accelerate the widely-used small convolution sizes. Quantized neural networks can effectively reduce model sizes and improve inference speed, which leads to a wide variety of kernels and hardware accelerators that work with integer data. The state-of-the-art Winograd algorithms pose challenges for efficient implementation and execution by the integer kernels and accelerators. We introduce a new class of Winograd algorithms by extending the construction to the field of complex and propose optimizations that reduce the number of general multiplications. The new algorithm achieves an arithmetic complexity reduction of @math x over the direct method and an efficiency gain up to @math over the rational algorithms. Furthermore, we design and implement an integer-based filter scaling scheme to effectively reduce the filter bit width by @math without any significant accuracy loss.
The Winograd convolution algorithm was first used to accelerate convnets by @cite_10 . The authors derived several small fixed-size algorithms over the field of rationals based on the minimal filtering algorithm proposed by Winograd @cite_21 , which achieve arithmetic complexity reductions ranging from @math x to @math x for the popular filter sizes.
@cite_21 @cite_10
2907172645 1846148069
Convolution is the core operation for many deep neural networks. The Winograd convolution algorithms have been shown to accelerate the widely-used small convolution sizes. Quantized neural networks can effectively reduce model sizes and improve inference speed, which leads to a wide variety of kernels and hardware accelerators that work with integer data. The state-of-the-art Winograd algorithms pose challenges for efficient implementation and execution by the integer kernels and accelerators. We introduce a new class of Winograd algorithms by extending the construction to the field of complex and propose optimizations that reduce the number of general multiplications. The new algorithm achieves an arithmetic complexity reduction of @math x over the direct method and an efficiency gain up to @math over the rational algorithms. Furthermore, we design and implement an integer-based filter scaling scheme to effectively reduce the filter bit width by @math without any significant accuracy loss. For short data sequences, Winograd's convolution algorithms attaining the minimum number of multiplications also attain a low number of additions, making them very efficient. However, for longer lengths they require a larger number of additions. Winograd's approach is usually extended to longer lengths by using a nesting approach such as the Agarwal-Cooley (1977) or Split-Nesting algorithms. Although these nesting algorithms are organizationally quite simple, they do not make the greatest use of the factorability of the data sequence length. The algorithm we propose adheres to Winograd's original approach more closely than do the nesting algorithms. By evaluating polynomials over simple matrices we retain, in algorithms for longer lengths, the basic structure and strategy of Winograd's approach, thereby designing computationally refined algorithms. This tactic is arithmetically profitable because Winograd's approach is based on a theory of minimum multiplicative complexity. >