E.I. Goncharov, P.L. Iljin, V.I. Munerman, T.A. Samoylova

Smolensk State University (Smolensk, Russia)

Most modern high-availability information systems are either based on systems that are classified as artificial intelligence, or to a large extent include them as components. The solution of many problems of artificial intelligence is based on the use of algorithms that implement the convolution operation (for example, algorithms for training neural networks). The article proposes an approach that, on the one hand, provides a strict formalization of this operation based on the algebra of multidimensional matrices, and on the other hand, due to this, it provides such practical advantages as simplifying and reducing the cost of developing such information systems, as well as reducing the execution time of queries to them. due to the simplicity of the development of parallel algorithms and programs and the efficient use of parallel computing systems. Convolution is an indispensable operation for solving many scientific and technical problems, such as machine learning, data analysis, signal processing, image processing filters. An important role is played by multidimensional convolutions, which are widely used in various subject areas. At the same time, due to the complexity of the algorithms that implement them, in practice even three-dimensional convolutions are used much less frequently than one- and two-dimensional ones. Replacing a multidimensional convolution operation with a sequence of convolution operations of lower dimensions significantly increases its computational complexity. The main reason for this lies in the absence of a unified strict definition of the operation and overload in mathematics of the term «convolution». Therefore, the article discusses a multidimensional-matrix computation model, which allows one to effectively formalize problems whose solution uses multidimensional convolution operations, and to implement an effective solution to these problems due to the natural parallelism inherent in the operations of the algebra of multidimensional matrices.

Goncharov E.I., Iljin P.L., Munerman V.I., Samoylova T.A. The approach to increasing the efficiency of convolution algorithms in modern highavailability systems. Highly Available Systems. 2021. V. 17. № 1. P. 15−24. DOI: https://doi.org/10.18127/j20729472-202101-02. (in Russian)

1. Kolmogorov A.N., Fomin S.V. Elementy teorii funktsii i funktsionalnogo analiza. M.: Fizmatlit. 2004. (in Russian)
2. Rabiner L., Gould B. Teoriya i primenenie tsifrovoi obrabotki signalov. Glava 2. Teoriya lineinykh diskretnykh sistem. M.: Mir. 1978. 848 s. (in Russian)
3. Blahut R. Fast algorithms and multidimensional convolutions. Fast Algorithms for Signal Processing. Cambridge: Cambridge University Press. 2010. P. 345−383. DOI: 10.1017/CBO9780511760921.012.
4. Rakhuba M.V., Oseledets I.V. Bystryi algoritm vychisleniya mnogomernoi svertki na osnove tenzornykh approksimatsii i ego primenenie dlya rascheta elektronnoi struktury molekul. Trudy 56-i nauchnoi konf. MFTI. 2013. (in Russian)
5. Fernandez Joseph, Kumar Vijaya Multidimensional Overlap-Add and Overlap-Save for Correlation and Convolution. 2013. P. 509−513. DOI: 10.1109/ICIP.2013.6738105.
6. Mostafa Naghizadeh and Mauricio D. Sacchi Multidimensional convolution via a 1D convolution algorithm. The Leading Edge. 2009. № 28. P. 1336−1337. https://doi.org/10.1190/1.3259611.
7. Kim C.E. and Strintzis M.G. High-Speed Multidimensional Convolution. IEEE Transactions on Pattern Analysis and Machine Intelligence. May 1980. Vol. PAMI-2. № 3. P. 269−273. DOI: 10.1109/TPAMI.1980.4767017.
8. Bleikhut R. Bystrye algoritmy tsifrovoi obrabotki signalov: Per. s angl. M.: Mir. 1989. 448 s. (in Russian)
9. Altman E.A., Vaseeva T.V., Aleksandrov A.V. Kesh-orientirovannyi algoritm dlya vychisleniya mnogomernoi korrelyatsii. Materialy III Mezhdunar. nauchno-tekhnich. konf. «Problemy mashinovedeniya. Chast II». Omsk. 23−24 aprelya 2019 g. Omsk: OmGTU. 2019. S. 385−389. (in Russian)
10. D. Li, Zhang J., Zhang Q. and Wei X. Classification of ECG signals based on 1D convolution neural network. 2017 IEEE 19th International Conference on e-Health Networking, Applications and Services (Healthcom). Dalian. 2017. P. 1−6. DOI: 10.1109/HealthCom.2017.8210784.
11. Semyanistyi V.I. O nekotorykh integralnykh preobrazovaniyakh v evklidovom prostranstve. Doklady Akademii nauk. Rossiiskaya akademiya nauk. 1960. T. 134. № 3. S. 536−539. (in Russian)
12. Lo S.C.B. et al. Artificial convolution neural network techniques and applications for lung nodule detection. IEEE transactions on medical imaging. 1995. V. 14. № 4. P. 711−718. DOI: 10.1109/42.476112.
13. Winkler A. What is convolution? [Elektronnyi resurs]: URL = https://www.quora.com/What-is-convolution (data obrashcheniya  20.01.2021).
14. Sokolov N.P. Vvedenie v teoriyu mnogomernykh matrits. Kiev: Naukova Dumka. 1972. (in Russian)
15. Munerman V.I. Postroenie arkhitektur programmno-apparatnykh kompleksov dlya povysheniya effektivnosti massovoi obrabotki dannykh. Sistemy vysokoi dostupnosti. 2014. T. 10. № 4. S. 3−16. (in Russian)
16. Zakharov V.N., Munerman V.I. Parallelnaya realizatsiya obrabotki intensivno ispolzuemykh dannykh na osnove algebry mnogomernykh matrits. XVII Mezhdunar. konf. DAMDID/RCDLXVII Mezhdunar. konf. DAMDID/RCDL «Analitika i upravlenie dannymi v oblastyakh s intensivnym ispolzovaniem dannykh». 2015. S. 217−223. (in Russian)