izvestswsuИзвестия Юго-Западного государственного университетаProceedings of the Southwest State University2223-15602686-6757ЮЗГУ10.21869/2223-1560-2021-25-2-65-82izvestswsu-882Research ArticleИнформатика, вычислительная техника и управлениеComputer science, computer engineering and IT managmentМатематическая модель определения состава бинарных отношений и алгоритм умножения бинарных матрицA Mathematical Model for Determining the Composition of Binary Relations and an Algorithm for Binary Matrices MultiplicationГвоздеваС. Н.GvozdevaS. N.

Гвоздева Светлана Николаевна, преподаватель кафедры вычислительной техники 

ул. 50 лет Октября 94, г. Курск 305040

Svetlana N. Gvozdeva, Lecturer, Computer Engineering Department 

50 Let Oktyabrya str. 94, Kursk 305040

svetka-gvozdeva@yandex.ruЮго-Западный государственный университетSouthwest State University2021190820212526582Copyright © Гвоздева С.Н., 20212021Гвоздева С.Н.Gvozdeva S.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://izvestswsu.elpub.ru/jour/article/view/882

Цель исследования. Необходимость разработки математической модели определения состава бинарных отношений и аппаратно-ориентированного алгоритма умножения бинарных матриц, позволяющих обеспечить организацию параллельной обработки данных при определении состава бинарных отношений.Методы. Процедура определения состава бинарных отношений заключается в следующем: на первом этапе выполняется определение отношения следования, для этого производится его транзитивное замыкание; определение отношения связи происходит после выяснения отношения следования; затем происходит выяснение отношения альтернативы; на завершающем этапе определения состава бинарных отношений выполняется выяснение отношения параллельности.Результаты. В данной работе разработана математическая модель определения состава бинарных отношений и алгоритм умножения бинарных матриц. Новизной математической модели является введение бинарных отношений связи, альтернативы и параллельности вершин граф-схем параллельных алгоритмов в дополнение к отношению следования, известному в теории графов. Новизной алгоритма умножения бинарных матриц является сокращение числа итераций внутреннего цикла (по переменной k) при получении единичного значения на одной из итераций нахождения скалярного произведения двоичных векторов.Заключение. Разработанная математическая модель бинарных отношений следования и связи вершин граф-схем параллельных алгоритмов позволяет обеспечить организацию параллельной обработки данных при определении состава бинарных отношений. На базе математической модели определения состава бинарных отношений разработан аппаратно-ориентированный алгоритм для умножения бинарных матриц, позволяющий перенести вычислительно сложные процедуры умножения бинарных матриц на аппаратный уровень. Разработанная математическая модель и алгоритм позволяют осуществить практическую реализацию устройств для умножения бинарных матриц с прерыванием внутреннего цикла.

Purpose of research. The need for the development of a mathematical model for determining the composition of binary relations and a hardware-oriented algorithm for multiplying binary matrices that allow organizing parallel data processing when determining the composition of binary relations.Methods. The procedure for determining the composition of binary relations is as follows: at the first stage, the definition of the sequence relation is performed, for this purpose its transitive closure is performed; the definition of the connection relation occurs after clarifying the sequence relation; then the alternative relation is clarified; at the final stage of determining the composition of binary relations, the parallelism relation is clarified.Results. In this paper, a mathematical model for determining the composition of binary relations and an algorithm for multiplying binary matrices are developed. The novelty of the mathematical model is the introduction of binary relations of connection, alternative and parallelism of the vertices of flowgraphs of parallel algorithms in addition to the sequence relation known in the graph theory. The novelty of the binary matrix multiplication algorithm is the reduction of the number of iterations of the inner cycle (with respect to the variable k) when obtaining a single value at one of the iterations of determining the scalar product of binary vectors.Conclusion. The developed mathematical model of binary relations of the sequence and connection of the vertices of flowgraphs of parallel algorithms allows for the organization of parallel data processing when determining the composition of binary relations. Based on the mathematical model for determining the composition of binary relations, a hardware-oriented algorithm for multiplying binary matrices was developed which allows transferring computationally complex procedures for multiplying binary matrices to the hardware level. The developed mathematical model and algorithm allow for the practical implementation of devices for multiplying binary matrices with an interruption of the internal cycle.

бинарные отношенияматрица отношенийотношение следованияотношение связипрерывание внутреннего циклаотношение альтернативыграф-схема алгоритмаотношение параллельностиумножение бинарных матрицbinary relationsrelational matrixsequence relationconnection relationinterruption of the internal cyclealternative relationalgorithm flowgraphparallelism relationmultiplication of binary matricesReferencesМетод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов / Э.И. Ватутин, Д.В. Колясников, И.А. Мартынов, В.С. Титов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. Барнаул: Барнаул, 2014. С. 115–125.Vatutin E.I., Kolyasnikov D.V., Martynov I.A., Titov V.S. [The method of random search in the problem of constructing partitions of graph schemes of parallel algorithms]. Mnogoyadernye protsessory, parallel'noe programmirovanie, PLIS, sistemy obrabotki signalov [Multi-core processors, parallel programming, PLIS, signal processing systems]. Barnaul, Barnaul Publ., 2014, pp. 115-125 (In Russ.).Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации / Э.И. Ватутин, Е.Н. Дремов, И.А. Мартынов, В.С. Титов // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. 2014. № 10 (137). Вып. 9. C. 59–64.Vatutin E.I., Dremov E.N., Martynov I.A., Titov V.S. Metod vzveshennogo sluchainogo perebora dlya resheniya zadach diskretnoi kombinatornoi optimizatsii [Method of weighted random search for solving problems of discrete combinatorial optimization]. Izvestiya VolGTU. Seriya: Elektronika, izmeritel'naya tekhnika, radiotekhnika i svyaz' = Izvestia Volga State Technical University. Series: Electronics, Measuring Equipment, Radio Engineering and Communications, 2014, № 10 (137). is. 9, pp. 59–64 (In Russ.).Метод взвешенного случайного перебора для построения разбиений граф-схем параллельных алгоритмов при проектировании логических мультиконтроллеров / Э.И. Ватутин, В.С. Панищев, С.Н. Гвоздева, В.С. Титов // Известия Юго-Западного государственого университета. 2017. Т. 21. № 6 (75). С. 6–21. https://doi.org/10.21869/2223-1560-2017-21-6-6-21.Vatutin E.I., Panishchev V.S., Gvozdeva S.N., Titov V.S. Metod vzveshennogo sluchainogo perebora dlya postroeniya razbienii graf-skhem parallel'nykh algoritmov pri proektirovanii logicheskikh mul'tikontrollerov [Weighed Random Selection Method for Construction of Partitioning of Parallel Algorithms Flowgraphs for Logic Multicontrollers Designing]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. = Proceedings of the Southwest State University, 2017, vol. 21, no. 6 (75), pp. 6-21 (In Russ.). https://doi.org/10.21869/2223-1560-2017-21-6-6-21.Ватутин Э.И., Титов В.С. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 111–120.Vatutin E.I., Titov V.S. Analiz rezul'tatov primeneniya algoritma murav'inoi kolonii v zadache poiska puti v grafe pri nalichii ogranichenii [Analysis of the results of the application of the ant colony algorithm in the problem of finding a path in the graph in the presence of restrictions]. Izvestiya Yuzhnogo federal'nogo universiteta. Tekhnicheskie nauki = Izvestia of the Southern Federal University. Technical sciences, 2014, no. 12 (161), pp. 111-120 (In Russ.).Ватутин Э.И., Зотов И.В. Повышение качества разбиения алгоритмов при синтезе логических мультиконтроллеров с использованием метода параллельнопоследовательной декомпозиции // Перспективы развития систем управления оружием: сборник докладов IV научно-практической конференции (Курск, 19-20 сентября 2007 г.). М.: Изд-во «Бедретдинов и Ко», 2007. С. 84–92.Vatutin E.I., Zotov I.V. [Improving the quality of algorithm splitting during the synthesis of logical multicontrollers using the parallel-sequential decomposition method]. Perspektivy razvitiya sistem upravleniya oruzhiem. Sbornik dokladov IV nauchno-prakticheskoi konferentsii [Prospects for the development of weapons control systems. Collection of reports of the IV scientific and practical conference]. Moscow, Publishing house "Bedretdinov and Co," Publ., 2007, pp. 84-92 (In Russ.).Ватутин Э.И., Титов В.С. Алгоритмическая оптимизация программной реализации метода параллельно-последовательной декомпозиции граф-схем параллельных алгоритмов // Известия высших учебных заведений. Приборостроение. 2013. Т. 56. № 6. С. 23–29.Vatutin E.I., Titov V.S. Algoritmicheskaya optimizatsiya programmnoi realizatsii metoda parallel'no-posledovatel'noi dekompozitsii graf-skhem parallel'nykh algoritmov [Algorithmic optimization of the program implementation of the method of parallel-sequential decomposition of graph schemes of parallel algorithms]. Izvestiya vysshikh uchebnykh zavedenii. Priborostroenie = News of Higher Educational Institutions. Instrument Making, 2013, vol. 56, no. 6, pp. 23-29 (In Russ.).Пшеничных А.О., Ватутин Э.И. Анализ результатов применения метода пчелиной колонии в задаче раскраски графов общего вида // Известия Юго-Западного государственного университета. 2020; 24(4): 126-145. https://doi.org/10.21869/2223-1560-2020-24-4-126-145.Pshenichnykh А. O., Vatutin E. I. Analysis of the Results of Applying the Bee Colony Method in the Problem of Coloring General Graphs. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2020; 24(4): 126- 145 (In Russ.). https://doi.org/10.21869/2223-1560-2020-24-4-126-145.Параллельные вычисления на GPU. Архитектура и программная модель CUDA / А.В. Боресков, А.А. Харламов, Н.Д. Марковский [и др.]. М.: Изд-во Московского университета, 2012. 336 с.Boreskov A.V., Kharlamov A.A. Markovsky N.D. and others. Parallel'nye vychisleniya na GPU. Arkhitektura i programmnaya model' CUDA [Parallel calculations on the GPU. Architecture and software model CUDA]. Moscow, Moscow University Publ., 2012. 336 p. (In Russ.).Затолокин Ю.А., Ватутин Э.И., Титов В.С. Алгоритмическая оптимизация программной реализации алгоритмов умножения плотных вещественных матриц на графических процессорах с поддержкой технологии OpenCL // Известия Юго-Западного государственного университета. 2017. Т. 21. № 5 (74). С. 6–15. https://doi.org/10.21869/2223-1560-2017-21-5-06-15.Zatolokin Y.A., Vatutin E.I., Titov V.S. Algoritmicheskaya optimizatsiya programmnoi realizatsii algoritmov umnozheniya plotnykh veshchestvennykh matrits na graficheskikh protsessorakh s podderzhkoi tekhnologii OpenCL [Algorithmic optimization of software implementation of algorithms for multiplying dense real matrices on graphics processors with OpenGL technology support]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University, 2017, no. 5, pp. 6-15 (In Russ.). https://doi.org/10.21869/2223-1560-2017-21-5-06-15.Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2013. № 4. С. 11–20.Zatolokin Yu.A., Vatutin E.I., Titov V.S. Otsenka real'noi proizvoditel'nosti sovremennykh protsessorov v zadache umnozheniya matrits dlya odnopotochnoi programmnoi realizatsii [Algorithmic optimization of software implementation of algorithms for multiplying dense real matrices on graphics processors with support for OpenCL technology]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika, informatika. Meditsinskoe priborostroenie = Proceedings of the Southwest State University. Series: Control, Computing Engineering, Information Science. Medical Instruments Engineering, 2013, no. 4, pp. 11-20 (In Russ.).Ватутин Э.И., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации с использованием расширения SSE (часть 1) // Известия Юго-Западного государственного университета. 2015. № 4 (61). С. 26–35.Vatutin E.I., Titov V.S. Otsenka real'noi proizvoditel'nosti sovremennykh protsessorov v zadache umnozheniya matrits dlya odnopotochnoi programmnoi realizatsii s ispol'zovaniem rasshireniya SSE (chast' 1) [Assessment of the real performance of modern processors in the task of multiplying matrices for a single-stream software implementation using the SSE extension (part 1 )]. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University, 2015, no. 4 (61), pp. 26-35 (In Russ.).Ватутин Э.И., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации с использованием расширения SSE (часть 2) // Известия Юго-Западного государственного университета. 2015. № 5 (62). С. 8–16.Vatutin E.I., Titov V.S. Otsenka real'noi proizvoditel'nosti sovremennykh protsessorov v zadache umnozheniya matrits dlya odnopotochnoi programmnoi realizatsii s ispol'zovaniem rasshireniya SSE (chast' 1) [Assessment of the real performance of modern processors in the task of multiplying matrices for a single-stream 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 (In Russ.).А.с. СССР 1781679 МПК G06F1/04, G06F15/347. Устройство для умножения квадратных матриц картин-изображений / Красиленко В.Г., Заболотная Н.И. Заявл. 07.07.1989. Опубл. 15.12.1992.Krasilenko V.G., Zabolotnaya N.I.. Ustroistvo dlya umnozheniya kvadratnykh matrits kartin-izobrazhenii [A device for multiplying square matrices of picture-images]. A.S. USSR 1781679 IPC G06F1 / 04, G06F15 / 347. Appl. 07.07.1989. Publ. 12/15/1992 (In Russ.).А. с. СССР 647687 МПК G06F17/16. Устройство для операций над матрицами / Гладкий В.С., Гук Л.Б. Заявл. 21.12.1976. Опубл. 15.02.1979.Gladkiy V.S., Guk L.B. Ustroistvo dlya operatsii nad matritsami [A device for operations on matrices]. A.S. USSR 647687 IPC G06F17 / 16. Appl. 12/21/1976. Publ. 02/15/1979 (In Russ.).Патент США № 8924455. Multiplication of matrices using systolic arrays / Kaushik Barman, Parag Dighe, Ragahavendar M. Rao. Заявл. 25.02.2011. Опубл. 30.12.2014.Kaushik Barman, Parag Dighe, Ragahavendar M. Rao. Multiplication of matrices using systolic arrays]. US Patent No. 8,924,455. Appl. 02/25/2011. Publ. 12/30/2014.Strassen V. Gaussian Elimination is not Optimal // Numer. Math / Springer-Verlag, 1969. Vol. 13, is. 4. P. 354–356. doi:10.1007/BF02165411.Strassen V. Gaussian Elimination is not Optimal. Numer. Math. Springer-Verlag, 1969, vol. 13, is. 4, pp. 354–356. https://doi.org/10.1007/BF02165411.Pan V. Ya, Strassen’s algorithm is not optimal – trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations. Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978.Pan V. Ya. Strassen’s algorithm is not optimal – trilinear technique of aggregating uniting and canceling for constructing fast algorithms for matrix operations. Proc. 19th Annual Symposium on Foundations of Computer Science, Ann Arbor, Mich., 1978.Bini D., Capovani M., Lotti G., Romani F. O(n2.7799) complexity for n n approximate matrix multiplication. Inform. Process. Lett., 1979.Bini D., Capovani M., Lotti G., Romani F. O(n2.7799) complexity for n n  approximate matrix multiplication. Inform. Process. Lett., 1979.Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.Организация и синтез микропрограммных мультимикроконтроллеров / И.В. Зотов, В.А. Колосков, В.С. Титов [и др.]. Курск, 1999. 368 с.Zotov I.V., Koloskov V.A., Titov V.S. and others. Organizatsiya i sintez mikroprogrammnykh mul'timikrokontrollerov [Organization and synthesis of firmware multimicrocontrollers]. Kursk, 1999. 368 p. (In Russ.).Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мультиконтроллеров. М: Высшая школа, 2009. 233 с.Emelyanov S.G., Zotov I.V., Titov V.S. Arkhitektura parallel'nykh logicheskikh mul'tikontrollerov [Architecture of parallel logical multicontrollers]. Moscow, Vysshaya shkola Publ., 2009. 233 p. (In Russ.).Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров Э.И. Ватутин, И.В. Зотов, В.С. Титов [и др.]. Курск, 2010. 200 с.Vatutin E.I., Zotov I.V., Titov V.C. et al. Kombinatorno-logicheskie zadachi sinteza razbienii parallel'nykh algoritmov logicheskogo upravleniya pri proektirovanii logicheskikh mul'tikontrollerov [Combinatorial and Logical Problems of Synthesis of Sections of Parallel Logic Control Algorithms in the Design of Logical Multi-Controllers]. Kursk, 2010. 200 p. (In Russ.).Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrücken: Lambert Academic Publishing, 2011. 292 с.Vatutin E.I. Proektirovanie logicheskikh mul'tikontrollerov. Sintez razbienii parallel'nykh graf-skhem algoritmov [Design of logical multi-controllers. Synthesis of partitions of parallel graph schemes of algorithms]. Saarbrücken, Lambert Academic Publ., 2011, 292 p. (In Russ.).Ватутин Э.И., Зотов И.В. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов // Известия Курского государственного технического университета. 2004. № 2. С. 85–89Vatutin E.I., Zotov I.V. Postroenie matritsy otnoshenii v zadache optimal'nogo razbieniya parallel'nykh upravlyayushchikh algoritmov [Constructing a matrix of relations in the problem of optimal separation of parallel control algorithms]. Izvestiya Kurskogo gosudarstvennogo tekhnichekogo universiteta = Proceedings of the Kursk State Technical University, 2004, no. 2, pp. 85-89 (In Russ.).Зыков А. А. Основы теории графов. М.: Наука, 1986. 384 с.Zykov A. A. Osnovy teorii grafov [Fundamentals of graph theory]. Moscow, Nauka Publ., 1986, 384 p. (In Russ.).Handbook of discrete and combinatorial mathematics / K.H. Rosen, J.G. Michaels, J.L. Gross, J.W. Grossman, D.R. Shier. N. Y.: CRC Press, 2000. 1183 p.Rosen K.H., Michaels J.G., Gross J.L., Grossman J.W., Shier D.R.. Handbook of discrete and combinatorial mathematics. N. Y.: CRC Press, 2000, 1183 p.Кун С. Матричные процессоры на СБИС: [пер. с англ.]. М.: Мир, 1991. 672 с.Kun S. Matrichnye protsessory na SBIS [Matrix processors on SBIS]. Moscow, 1991. 672 p. (In Russ.).Мартынов И.А., Ватутин Э.И., Титов В.С. Аппаратно-ориентированная реализация операции транзитивного замыкания бинарных отношений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2015). Курск, 2015. С. 244–247.Martynov I.A., Vatutin E.I., Titov V.S. [Hardware-oriented implementation of transitive closure of binary relations]. Optiko-elektronnye pribory i ustroistva v sistemakh raspoznavaniya obrazov, obrabotki izobrazhenii i simvol'noi informatsii (Raspoznavanie – 2015) [Optical-electronic devices and devices in image recognition, image processing and symbolic information systems (Recognition - 2015)]. Kursk, 2015, pp. 244-247 (In Russ.).Пат. на изобретение № 2744239. Устройство для возведения бинарной матрицы в квадрат / Гвоздева С.Н., Ватутин Э.И., Титов В.С. Заявка № 2020122205 от 05.07.2020. Опубл. 04.03.2021г. Бюл.№7.Gvozdeva S.N., Vatutin E.I., Titov V.C. Ustroistvo dlya vozvedeniya binarnoi matritsy v kvadrat [ Device for squaring a binary matrix]. Patent RF No. 2744239. Application No. 2020122205 dated 05.07.2020 (In Russ.).Гвоздева С.Н., Ватутин Э.И. Оценка аппаратной сложности устройства для возведения бинарной матрицы в квадрат // Медико-экологические информационные технологии -2020: сборник научных статей по материалам XXIII Международной научно-технической конференции: в 2ч. / редкол.: Н.А. Кореневский (отв.ред.) [и др.]; Юго-Зап.гос.ун-т. Курск, 2020. Ч.2. С. 62-65.Gvozdeva S.N., Vatutin E.I. [Assessment of the hardware complexity of the device for squaring the binary matrix]. Mediko-ekologicheskie informatsionnye tekhnologii -2020. Sbornik nauchnykh statei po materialam XXIII Mezhdunarodnoi nauchno-tekhnicheskoi konferentsii = Medical and environmental information technologies -2020: a collection of scientific articles on materials of the XXIII International Scientific and Technical Conference]. Kursk, 2020, pp. 62-65 (In Russ.).

The authors declare that there are no conflicts of interest present.