ESTIMATION OF TIME SPENT ON MULTIPLICATION OF SQUARE BINARY MATRICES OF A DEVICE WITH PIPELINING OF DATA READING FROM SPECIALIZED MULTIPORT MEMORY
Abstract
The purpose of this work is to estimate the time costs for multiplying square binary matrices of size n × n by a device with pipelining the operation of reading data from a specialized multiport memory and compare it with the time costs of the prototype. This work used methods of mathematical logic, set and graph theory, discrete systems and computer devices, and finite state machine design theory. As a result of the study, it was shown that the use of pipelining the operation of reading data from specialized multiport memory reduces the time spent on processing square binary matrices with a size of n ≤ 2048 up to 206.3 times. It can be seen from the data obtained that the loading and unloading time of the source and result data for the proposed device is significantly higher than the matrix multiplication time, which makes frequent loading and unloading of matrices impractical. For example, when performing the operation of transitive closure of a binary relation represented as a binary matrix, the initial matrix is loaded once, followed by a series of squaring, which is effectively implemented by the proposed device. Based on the obtained results, it can be concluded that the proposed device for multiplying square binary matrices with
References
1. Shteynberg B.Ya. Blochno-rekursivnoe parallel'noe peremnozhenie matrits [Block-recursive parallel ma-trix multiplication], Izvestiya VUZov. Priborostroenie [Proceedings of Higher Education Institutions. In-strumentation], 2009, Vol. 52, No. 10, pp. 33-41.
2. Kozhin A.S, Nedbaylo Yu.A. Metody optimizatsii vremeni dostupa v obshchiy kesh mnogoyadernogo mikroprotsessora [Methods for optimizing access time to the shared cache of a multicore microproces-sor], Voprosy radioelektroniki [Questions of radio electronics], 2017, No. 3, pp. 27-32.
3. Egunov V.A. O vliyanii kesh-pamyati na effektivnost' programmnoy realizatsii bazovykh operatsiy lineynoy algebry [On the effect of cache memory on the effectiveness of software implementation of basic linear algebra operations], Prikaspiyskiy zhurnal: upravlenie i vysokie tekhnologii [Caspian Jour-nal: Management and High Technologies], 2018, No. 3, pp. 88-96.
4. Bolgak A.V., Vatutin E.I. Otsenka real'noy proizvoditel'nosti protsessorov semeystva Intel Core razlich-nykh pokoleniy v zadache umnozheniya veshchestvennykh matrits dlya odnopotochnoy programmnoy realizatsii [Evaluation of the real performance of Intel Core processors of various generations in the task of multiplying real matrices for single-threaded software implementation], Oblachnye i raspredelennye vychislitel'nye sistemy v elektronnom upravlenii. ORVS – 2023: Sb. trudov 4-y mezhdunarodnoy nauch-no-tekhnicheskoy konferentsii (28 noyabrya – 1 dekabrya 2023 goda) [Cloud and distributed computing systems in electronic control. ORVS – 2023: Proceedings of the 4th International Scientific and Tech-nical Conference (November 28 – December 1, 2023)], ed. by I.I. Kurochkin [et al.]; IPS RAS. Pereslavl-Zalessky. Kursk: Izd-vo ZAO «Universitetskaya kniga». – 2024, pp. 98-100.
5. Starovoytov I.N., Revnyakov E.N., Polyakova E.N. Parallel'nye vychisleniya na graficheskikh protsesso-rakh [Parallel computing on graphics processors], Pervaya Mezhdunarodnaya nauchnaya konferentsiya po problemam tsifrovizatsii: EDCRUNCH URAL – 2020: Mater. konferentsii (Ekaterinburg, 29–30 sentyabrya 2020 g.) [The First International Scientific Conference on Digitalization: EDCRUNCH URAL – 2020: conference proceedings (Yekaterinburg, September 29-30, 2020)]; Ministry of Science and Higher Education. education of the Russian Federation. Ekaterinburg: Izd-vo Ural. un-ta, 2020, pp. 314-319.
6. Tumakov D.N., Chikrin D.E., Egorchev A.A., Golousov S.V. Tekhnologiya programmirovaniya CUDA: ucheb. posobie [CUDA programming technology: a textbook]. Kazan': Kazanskiy gosudarstvennyy uni-versitet, 2017, 112 p.
7. Vatutin E.I., Martynov I.A., Titov V.S. Otsenka real'noy proizvoditel'nosti sovremennykh videokart s podderzhkoy tekhnologii CUDA v zadache umnozheniya matrits [Evaluation of the actual performance of modern graphics cards with support for CUDA technology in the matrix multiplication problem], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie [Proceedings of the Southwest State University. Series: Management, computer engineering, computer science. Medical instrumentation], 2014, No. 2, pp. 8-17.
8. Boreskov A.V., Kharlamov A.A. Markovskiy N.D. i dr. Parallel'nye vychisleniya na GPU. Arkhitektura i programmnaya model' CUDA [Parallel computing on the GPU. CUDA architecture and software mod-el]. Moscow: Izd-vo Moskovskogo universiteta, 2012, 336 p.
9. Volker S. Gaussian Elimination is not Optimal, Numerische Mathematik. Springer Science+Business Media, 1969, Vol. 13, Iss. 4, pp. 354-356.
10. Don C., Shmuel W. Matrix Multiplication via Arithmetic Progressions, Journal of Symbolic Computa-tion, 1990, pp. 251-280.
11. Yushin A.M. Spravochnik. Optoelektronnye pribory i ikh zarubezhnye analogi [Handbook. Optoelectron-ic devices and their foreign analogues]. Moscow: Izd-vo «RadioSoft»2000, Vol. 1, 512 p.
12. Belov P.A., Bespalov V.G., Vasil'ev V.N., Kozlov S.A., Pavlov A.V., Simovskiy K.R., Shpolyanskiy Yu.A. Opticheskie protsessory: dostizheniya i novye idei [Optical processors: achievements and new ideas], V kn.: Problemy kogerentnoy i ne-lineynoy optiki [Problems of Coherent and Nonlinear Optics]. Saint Pe-tersburg, 2006, pp. 6-36.
13. Plaksienko V.S., Plaksienko N.E., Plaksienko S.V. Ustroystva priema i obrabotki signalov: ucheb. posobie dlya vuzov [Signal reception and processing devices: A textbook for universities]. Moscow: Uchebno-metodicheskiy izdatel'skiy tsentr «Uchebnaya literatura», 2004, 376 p.
14. Lobach V.T., Potipak M.V. Osnovy proektirovaniya tsifrovykh ustroystv radioelektronnykh sistem: ucheb. posobie [Fundamentals of designing digital devices of radioelectronic systems: a textbook]. Ros-tov-on-Don; Taganrog: Izd-vo YuFU, 2020, 140 p.
15. Syryamkin V.I. Intellektual'nye sistemy 4-y promyshlennoy revolyutsii: Sb. materialov IV Mezhdu-narodnogo foruma, g. Tomsk, 15-16 dekabrya 2021 g. [Intelligent systems of the 4th industrial revolu-tion: collection of materials of the IV International Forum, Tomsk, December 15-16, 2021]. Tomsk: STT, 2022, 104 p.
16. Odinets A.I., Naumenko A.P. Tsifrovye ustroystva: ATSP i TSAP: ucheb. posobie [Digital devices: ADC and DAC: textbook]. Omsk: Izd-vo IRSID, 2006, 48 p.
17. Gümüşkaya Haluk, Örencik Bülent. A parallel pipelined computer architecture for digital signal pro-cessing, Turkish Journal of Electrical Engineering and Computer Sciences, 1998, Vol. 6, No. 2, Article 4, pp. 107-130.
18. Strogonov A.V. Osnovy tsifrovoy obrabotki signalov [Fundamentals of digital signal processing]. Voro-nezh: FGBOU VPO «Voronezhskiy gosudarstvennyy tekhnicheskiy universitet», 2014.
19. Zykov A.A. Osnovy teorii grafov [Fundamentals of graph theory]. Moscow: Nauka, 1986, 384 p.
20. Vatutin E.I., Zotov I.V. Postroenie matritsy otnosheniy v zadache optimal'nogo razbieniya parallel'nykh upravlyayushchikh algoritmov [Construction of a matrix of relations in the problem of optimal partition-ing of parallel control algorithms], Izvestiya Kurskogo gosudarstvennogo tekhnicheskogo universiteta [Proceedings of the Kursk State Technical University], 2004, No. 2, pp. 85-89.
21. Aleskerov F.T., Khabina E.L., Shvarts D.A., Egorova L.G. Binarnye otnosheniya, grafy i kollektivnye resheniya. Primery i zadachi: ucheb. posobie dlya vuzov [Binary relations, graphs and collective solu-tions. Examples and tasks: a textbook for universities]. Moscow: Izd-vo Yurayt, 2021, 458 p.
22. Bobonova E.N. Metody matematicheskoy obrabotki dannykh: ucheb. posobie [Methods of mathematical data processing: textbook]. Moscow; Vologda: Infrainzheneriya, 2024, 116 p.
23. Martynov I.A., Vatutin E.I., Titov V.S. Patent RF na poleznuyu model' № 157948. Ustroystvo dlya um-nozheniya matrits [Patent of the Russian Federation for utility model No. 157948. Device for matrix multiplication]. Claimed 08.07.2015, publ. 20.12.2015. Bul. No. 35.
24. Gvozdeva S.N., Vatutin E.I., Pshenichnykh A.O., Titov V.S. Patent RF na poleznuyu model' № 193927. Ustroystvo dlya umnozheniya binarnykh matrits [Patent of the Russian Federation for utility model No. 193927. Device for multiplying binary matrices]. Claimed 26.06.2019, publ. 21.11.2019.
25. Gvozdeva S.N., Vatutin E.I., Titov V.S.Patent RF № 2744239. Ustroystvo dlya vozvedeniya binarnoy matritsy v kvadrat [Patent of the Russian Federation No. 2744239. Device for squaring a binary matrix]. Claimed 07.05.2020, publ. 03.04.2021.
26. Yakush V.P., Sedukhin S.G., Avgul' L.B., Lenev A.A. A.s. SSSR 1429127 MPK G06F17/16. Ustroystvo dlya matrichnykh operatsiy [A.S. USSR 1429127 IPC G06F17/16. Device for matrix operations]. Claimed 03.04.1987. publ. 10.07.1988.
27. Gvozdeva S.N., Vatutin E.I., Titov V.S. Otsenka bystrodeystviya ustroystva s sistolicheskoy strukturoy dlya umnozheniya binarnykh matrits [Evaluation of the performance of a device with a systolic structure for multiplying binary matrices], Telekommunikatsii [Telecommunications], 2020, Vol. 3, pp. 2-10.
28. Vatutin E.I., Martynov I.A., Titov V.S. Otsenka real'noy proizvoditel'nosti sovremennykh protsessorov v zadache umnozheniya matrits dlya odnopotochnoy programmnoy realizatsii [Evaluation of the real per-formance of modern processors in the task of matrix multiplication for single-threaded software imple-mentation], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislit-el'naya tekhnika, informatika. Meditsinskoe priborostroenie [Proceedings of the Southwest State Uni-versity]. Series: Management, computer engineering, computer science. Medical instrumentation], 2013, No. 4, pp. 11-20.
29. Vatutin E.I., Titov V.S. Otsenka real'noy proizvoditel'nosti sovremennykh protsessorov v zadache um-nozheniya matrits dlya odnopotochnoy programmnoy realizatsii s ispol'zovaniem ras-shireniya SSE (chast' 1) [Evaluation of the real performance of modern processors in the matrix multiplication problem for single-threaded software implementation using the SSE extension (part 1)], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [Proceedings of the Southwest State University], 2015, Vol. 1, No. 4 (61), pp. 26-35.
30. Vatutin E.I., Titov V.S. Otsenka real'noy proizvoditel'nosti sovremennykh protsessorov v zadache um-nozheniya matrits dlya odnopotochnoy programmnoy realizatsii s ispol'zovaniem rasshireniya SSE (chast' 2) [Evaluation of the real performance of modern processors in the matrix multiplication problem for single-threaded software implementation using the SSE extension (part 2)], Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta [Proceedings of the Southwest State University], 2015, Vol. 1, No. 5 (62), pp. 8-16.
