ОЦЕНКА ВРЕМЕННЫХ ЗАТРАТ НА УМНОЖЕНИЕ КВАДРАТНЫХ БИНАРНЫХ МАТРИЦ УСТРОЙСТВА С КОНВЕЙЕРИЗАЦИЕЙ ЧТЕНИЯ ДАННЫХ ИЗ СПЕЦИАЛИЗИРОВАННОЙ МНОГОПОРТОВОЙ ПАМЯТИ
Аннотация
Целью данной работы является оценка временных затрат на умножение квадратных бинарных матриц размером n × n устройства с конвейеризацией операции чтения данных из специализированной многопортовой памяти и ее сравнение с временными затратами прототипа. В данной работе использовались методы математической логики, теории множеств и графов, дискретных систем и устройств ЭВМ, теории проектирования конечных автоматов. В результате исследования было показано, что использование конвейеризации операции чтения данных из специализированной многопортовой памяти позволяет снизить временные затраты на обработку квадратных бинарных матриц размером n ≤ 2048 до 206,3 раза. Из полученных данных видно, что время загрузки и выгрузки исходных и результирующих данных для предложенного устройства существенно выше времени умножения матриц, ввиду чего частые загрузки и выгрузки матриц нецелесообразны. Например, при выполнении операции транзитивного замыкания бинарного отношения, представленного в виде бинарной матрицы, производится однократная загрузка исходной матрицы с последующей серией ее возведения в квадрат, что эффективно реализуется предложенным устройством. На основании полученных результатов можно сделать вывод, что предложенное устройство для умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти обеспечивает существенный выигрыш во времени обработки и умножения квадратных бинарных матриц по сравнению с прототипом. Кроме того, результаты показали, что частые загрузки и выгрузки матриц нецелесообразны для предложенного устройства с конвейеризацией операции чтения из специализированной многопортовой памяти, так как затрачиваемое время на загрузку и выгрузку исходных и результирующих данных существенно превышает время на операцию умножения матриц
Список литературы
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.
