A Mathematical Model for Determining the Composition of Binary Relations and an Algorithm for Binary Matrices Multiplication

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.

1. 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.).

2. 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.).

3. 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.

4. 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.).

5. 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.).

6. 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.).

7. 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.

8. 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.).

9. 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.

10. 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.).

11. 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.).

12. 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.).

13. 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.).

14. 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.).

15. 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.

16. 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.

17. 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.

18. Bini D., Capovani M., Lotti G., Romani F. O(n2.7799) complexity for n n  approximate matrix multiplication. Inform. Process. Lett., 1979.

19. Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9:251-280, 1990.

20. 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.).

21. 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.).

22. 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.).

23. 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.).

24. Vatutin 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.).

25. Zykov A. A. Osnovy teorii grafov [Fundamentals of graph theory]. Moscow, Nauka Publ., 1986, 384 p. (In Russ.).

26. 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.

27. Kun S. Matrichnye protsessory na SBIS [Matrix processors on SBIS]. Moscow, 1991. 672 p. (In Russ.).

28. 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.).

29. 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.).

30. 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.).