Minimizing Multiplication of Kernel Computation in Convolutional Neural Networks Using Strassen Algorithm

Dary Mochamad Rifqie; Dewi Fatmarani Surianto; Sudarmanto Jayanegara; Muhammad Fajar B; M Miftach Fakhri

doi:10.26858/jmtik.v6i2.46016

Minimizing Multiplication of Kernel Computation in Convolutional Neural Networks Using Strassen Algorithm

Dary Mochamad Rifqie^(1*), Dewi Fatmarani Surianto⁽²⁾, Sudarmanto Jayanegara⁽³⁾, Muhammad Fajar B⁽⁴⁾, M Miftach Fakhri⁽⁵⁾,

(1) Universitas Negeri Makassar
(2) Universitas Negeri Makassar
(3) Universitas Negeri Makassar
(4) Universitas Negeri Makassar
(5) Universitas Negeri Makassar
(*) Corresponding Author

DOI: https://doi.org/10.26858/jmtik.v6i2.46016

Abstract

Convolution neural networks (CNN) have been widely applied for the computer vision task. However, the success of CNN is limited by the computational complexity of the network, so it is difficult for the model to run the inference process in real time. In this paper, we apply Strassen matrix multiplication to reduce multiplications in convolution operations in CNN, in order to get faster execution for CNN. First, we transform the convolution operation into a matrix multiplication operation using the Toeplitz mapping method, then after that, we apply the Strassen method to these matrices. In the end, we compare the number of arithmetic operations (multiplication and addition) in the convolutional layer using Strassen and the standard algorithm. We apply this algorithm implementation in convolution layers 1 and 3 in LeNet-5 Architecture.

Keywords

Convolutional Neural Network , Strassen Algorithm, Matrix Multiplication , Kernal Computation

Full Text:

PDF

References

Barman, U., Choudhury, R.D., Sahu, D. and Barman, G.G., 2020. Comparison of convolution neural networks for smartphone image based real time classification of citrus leaf disease. Computers and Electronics in Agriculture, 177, p.105661.

Chishti, Syed OwaisAli, Sana Riaz, Muhammad BilalZaib, and Mohammad Nauman. "Self-driving cars using CNN and Q-learning." In 2018 IEEE 21st International Multi-Topic Conference (INMIC), pp. 1-7. IEEE, 2018.

Hedtke, Ivo. "Strassen's Matrix Multiplication Algorithm for Matrices of Arbitrary Order." arXiv preprint arXiv:1007.2117 (2010).

Zhao, Yulin, et al. "A faster algorithm for reducing the computational complexity of convolutional neural networks." Algorithms 11.10 (2018): 159.

LeCun, Yann, et al. "Comparison of learning algorithms for handwritten digit recognition." International conference on artificial neural networks. Vol. 60. No. 1. 1995.

Townsend, Alex, Marcus Webb, and Sheehan Olver. "Fast polynomial transforms based on Toeplitz and Hankel matrices." Mathematics of Computation 87.312 (2018): 1913-1934.

Strassen, Volker. "Gaussian elimination is not optimal." Numerische mathematik 13.4 (1969): 354-356.

WINOGRAD, Shmuel. Arithmetic complexity of computations. Siam, 1980.

Cong, J., and B. Xiao. "Artificial Neural Networks and Machine Learning." Proceedings of the 24th International Conference on Artificial Neural Networks,(ICANN'14). Vol. 8681.

Rifqie, Dary Mochamad, et al. "POST TRAINING QUANTIZATION IN LENET-5 ALGORITHM FOR EFFICIENT INFERENCE." (2022).

Sze, Vivienne, et al. "Efficient processing of deep neural networks: A tutorial and survey." Proceedings of the IEEE 105.12 (2017): 2295-2329.