Popular deep neural networks (DNNs) spend the majority of their execution
time computing convolutions. The Winograd family of algorithms can greatly
reduce the number of arithmetic operations required and is present in many DNN
software frameworks. However, the performance gain is at the expense of a
reduction in floating point (FP) numerical accuracy. In this paper, we analyse
the worst case FP error and prove the estimation of norm and conditioning of
the algorithm. We show that the bound grows exponentially with the size of the
convolution, but the error bound of the \textit{modified} algorithm is smaller
than the original one. We propose several methods for reducing FP error. We
propose a canonical evaluation ordering based on Huffman coding that reduces
summation error. We study the selection of sampling "points" experimentally and
find empirically good points for the most important sizes. We identify the main
factors associated with good points. In addition, we explore other methods to
reduce FP error, including mixed-precision convolution, and pairwise summation
across DNN channels. Using our methods we can significantly reduce FP error for
a given block size, which allows larger block sizes and reduced computation.

本研究分析了深度神经网络中卷积计算的 numerical accuracy，以 Winograd algorithm 为基础设计了限制误差的 modified algorithm，并提出了 Huffman 编码和 mixed-precision convolution 等多种方法，能显著降低误差并提高计算效率。