Математическая модель определения состава бинарных отношений и алгоритм умножения бинарных матриц

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

1. Метод случайного перебора в задаче построения разбиений граф-схем параллельных алгоритмов / Э.И. Ватутин, Д.В. Колясников, И.А. Мартынов, В.С. Титов // Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов. Барнаул: Барнаул, 2014. С. 115–125.

2. Метод взвешенного случайного перебора для решения задач дискретной комбинаторной оптимизации / Э.И. Ватутин, Е.Н. Дремов, И.А. Мартынов, В.С. Титов // Известия ВолГТУ. Серия: Электроника, измерительная техника, радиотехника и связь. 2014. № 10 (137). Вып. 9. C. 59–64.

3. Метод взвешенного случайного перебора для построения разбиений граф-схем параллельных алгоритмов при проектировании логических мультиконтроллеров / Э.И. Ватутин, В.С. Панищев, С.Н. Гвоздева, В.С. Титов // Известия Юго-Западного государственого университета. 2017. Т. 21. № 6 (75). С. 6–21. https://doi.org/10.21869/2223-1560-2017-21-6-6-21.

4. Ватутин Э.И., Титов В.С. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений // Известия Южного федерального университета. Технические науки. 2014. № 12 (161). С. 111–120.

5. Ватутин Э.И., Зотов И.В. Повышение качества разбиения алгоритмов при синтезе логических мультиконтроллеров с использованием метода параллельнопоследовательной декомпозиции // Перспективы развития систем управления оружием: сборник докладов IV научно-практической конференции (Курск, 19-20 сентября 2007 г.). М.: Изд-во «Бедретдинов и Ко», 2007. С. 84–92.

6. Ватутин Э.И., Титов В.С. Алгоритмическая оптимизация программной реализации метода параллельно-последовательной декомпозиции граф-схем параллельных алгоритмов // Известия высших учебных заведений. Приборостроение. 2013. Т. 56. № 6. С. 23–29.

7. Пшеничных А.О., Ватутин Э.И. Анализ результатов применения метода пчелиной колонии в задаче раскраски графов общего вида // Известия Юго-Западного государственного университета. 2020; 24(4): 126-145. https://doi.org/10.21869/2223-1560-2020-24-4-126-145.

8. Параллельные вычисления на GPU. Архитектура и программная модель CUDA / А.В. Боресков, А.А. Харламов, Н.Д. Марковский [и др.]. М.: Изд-во Московского университета, 2012. 336 с.

9. Затолокин Ю.А., Ватутин Э.И., Титов В.С. Алгоритмическая оптимизация программной реализации алгоритмов умножения плотных вещественных матриц на графических процессорах с поддержкой технологии OpenCL // Известия Юго-Западного государственного университета. 2017. Т. 21. № 5 (74). С. 6–15. https://doi.org/10.21869/2223-1560-2017-21-5-06-15.

10. Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2013. № 4. С. 11–20.

11. Ватутин Э.И., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации с использованием расширения SSE (часть 1) // Известия Юго-Западного государственного университета. 2015. № 4 (61). С. 26–35.

12. Ватутин Э.И., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации с использованием расширения SSE (часть 2) // Известия Юго-Западного государственного университета. 2015. № 5 (62). С. 8–16.

13. А.с. СССР 1781679 МПК G06F1/04, G06F15/347. Устройство для умножения квадратных матриц картин-изображений / Красиленко В.Г., Заболотная Н.И. Заявл. 07.07.1989. Опубл. 15.12.1992.

14. А. с. СССР 647687 МПК G06F17/16. Устройство для операций над матрицами / Гладкий В.С., Гук Л.Б. Заявл. 21.12.1976. Опубл. 15.02.1979.

15. Патент США № 8924455. Multiplication of matrices using systolic arrays / Kaushik Barman, Parag Dighe, Ragahavendar M. Rao. Заявл. 25.02.2011. Опубл. 30.12.2014.

16. Strassen V. Gaussian Elimination is not Optimal // Numer. Math / Springer-Verlag, 1969. Vol. 13, is. 4. P. 354–356. doi: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. Организация и синтез микропрограммных мультимикроконтроллеров / И.В. Зотов, В.А. Колосков, В.С. Титов [и др.]. Курск, 1999. 368 с.

21. Емельянов С.Г., Зотов И.В., Титов В.С. Архитектура параллельных логических мультиконтроллеров. М: Высшая школа, 2009. 233 с.

22. Комбинаторно-логические задачи синтеза разбиений параллельных алгоритмов логического управления при проектировании логических мультиконтроллеров Э.И. Ватутин, И.В. Зотов, В.С. Титов [и др.]. Курск, 2010. 200 с.

23. Ватутин Э.И. Проектирование логических мультиконтроллеров. Синтез разбиений параллельных граф-схем алгоритмов. Saarbrücken: Lambert Academic Publishing, 2011. 292 с.

24. Ватутин Э.И., Зотов И.В. Построение матрицы отношений в задаче оптимального разбиения параллельных управляющих алгоритмов // Известия Курского государственного технического университета. 2004. № 2. С. 85–89

25. Зыков А. А. Основы теории графов. М.: Наука, 1986. 384 с.

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

27. Кун С. Матричные процессоры на СБИС: [пер. с англ.]. М.: Мир, 1991. 672 с.

28. Мартынов И.А., Ватутин Э.И., Титов В.С. Аппаратно-ориентированная реализация операции транзитивного замыкания бинарных отношений // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание – 2015). Курск, 2015. С. 244–247.

29. Пат. на изобретение № 2744239. Устройство для возведения бинарной матрицы в квадрат / Гвоздева С.Н., Ватутин Э.И., Титов В.С. Заявка № 2020122205 от 05.07.2020. Опубл. 04.03.2021г. Бюл.№7.

30. Гвоздева С.Н., Ватутин Э.И. Оценка аппаратной сложности устройства для возведения бинарной матрицы в квадрат // Медико-экологические информационные технологии -2020: сборник научных статей по материалам XXIII Международной научно-технической конференции: в 2ч. / редкол.: Н.А. Кореневский (отв.ред.) [и др.]; Юго-Зап.гос.ун-т. Курск, 2020. Ч.2. С. 62-65.