METHOD OF FAST MATRIX MULTIPLICATION UNDER ARM ARCHITECTURE USING SIMD INSTRUCTIONS
Keywords:Matrix multiplication, ARM architecture, Vector operations, Matrix transposition
Background. Matrix multiplication is a rather complicated algorithm with a large number of operations. An additional problem is the nonlinear memory traversal of matrices. Matrix multiplication is widely used in various fields, such as neural networks, solutions of linear equation systems, matrix transformations, and so on. Therefore, it is important to develop a method of matrix multiplication, which will take into account the problems of the location of the matrices in memory, and will effectively manage the data when reused.
Objective. The purpose of the paper is to develop a method of fast matrix multiplication of two matrices, as well as multiplying the matrix by the transposed matrix and by a list of vectors (including special case for only one vector), as well as to implement it as a function with optimization for ARM architecture processors. The function must be able to handle different types of data and submatrices. The integer result can be scaled.
Methods. The main ideas of the developed method are simultaneous work with several rows/columns of input matrices and their splitting into blocks, which will allow the algorithm to run on the same memory for a while. The C programming language was chosen for implementation. SIMD instructions were used to increase productivity. We also need to properly organize the memory preloading for effective implementation under the ARM architecture.
Results. A function that performs matrix multiplication by the developed method with the necessary parameters was implemented as a result of the study. Tests on various sizes and types have shown that the implemented function is faster than analogues from the OpenCV2 and Eigen 3 libraries. Testing was done using the vipmed utility for running and measuring features developed for enterprise use at VIT.Conclusions. The proposed matrix multiplication method gives the expected acceleration of matrix multiplication operations, has passed evaluation test for use and meets the target requirements. For further work, it is necessary to study in more detail the influence of the cache at different levels and compare with other existing libraries.
Application of Matrices in Real-Life [Online]. Available: https://www.ukessays.com/essays/mathematics/application-of-matrices-in-real-life-problems.php
Le Gall, François, “Powers of tensors and fast matrix multiplication”, in Proc. 39th Int. Symp. Symbolic and Algebraic Computation, Kobe, Japan, 2014, pp. 157–164.
V. Strassen, “Gaussian elimination is not optimal”, Numer. Math., vol. 13, no. 4, pp. 354–356, 1969.
S. Robinson, “Toward an optimal algorithm for matrix multiplication”, SIAM News, vol. 38, no. 9, 2005.
C.L. Lawson et al., “Basic linear algebra subprograms for FORTRAN usage”, in ACM Trans. Math. Software, 1979, pp. 308–323.
OpenCV official site [Online]. Available: https://opencv.org/
Eigen Official Site [Online]. Available: http://eigen.tuxfamily.org/
ARM Official Site [Online]. Available: https://developer.arm.com/
ARM Information Center [Online]. Available: https://infocenter.arm.com/
Copyright (c) 2020 The Author(s)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under CC BY 4.0 that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work