Improving the Accuracy of the Winograd Convolution for Deep Neural Networks - Barabasz, Barbara Maria (Trinity College Dublin. School of Computer Science & Statistics. Discipline of Computer Science, 2022)
This thesis is focused on Winograd’s fast algorithms calculating discrete convolutions. More precisely, on the most optimal in terms of the number of operations subclass of them, that is Toom-Cook algorithms. These algorithms reduce the number of operations in a calculation process from O(n2) to O(n). That means the larger input data is taken the bigger reduction in number of operations we have and in a consequence the greater speed up is obtained. However, the accuracy of computations declines as the input size increases. We undertake this dichotomy in our thesis. The problem is very essential because calculating discrete convolutions is a one of the main bottleneck in convolutional neural networks (CNNs) computations. The time required to train and use CNNs is challenging even for modern computers. In our thesis we formulate algorithms to construct transformation matrices used in Toom-Cook convolutional algorithms. After analysing the mathematical background of these algorithms we prove that the error of Toom-Cook convolution computations grows exponentially with the input data size. This is caused by poor numerical properties of the transformation matrices. We also demonstrate that the error of the so called modified Toom-Cook algorithm is smaller than the error of the original one although it still grows exponentially. Then we identify the components of a numerical error of these convolution algorithms. We propose some techniques that improve the accuracy of the Toom-Cook convolution computations and verify them empirically for the wide range of input data sizes. We find that we can tune not only input data size but also the number, degree and root points of polynomials used to construct transformation matrices (real valued Vandermonde matrices). We investigate ways of choosing root points of polynomials which determine properties of the transformation matrices. We construct sets of optimal root points for various input tile sizes both in a single and a mixed precision. We find that the Chebyshev points which work very good for bigger sizes real valued Vandermonde matrices do not work properly for smaller sizes used in DNNs. We propose and test the canonical summation order, based on the idea of Huffman coding, to further reduce the error in the dot product computations. All proposed methods result in about 50% reduction in floating point error of the final computations. Finally, we come back to the general case of Winograd algorithms. We present the algorithm for the construction of Winograd transformation matrices. We present a method, using superlinear polynomials, which improves floating point accuracy. The presented version of the Winograd algorithm offers a larger space of trade-offs between computation complexity and accuracy using higher order polynomials. Thus, it allows us to find an attractive solutions that are not available when using Toom-Cook algorithms.
APPROVED