Математическая модель, метод организации параллельно-конвейерной памяти и специализированное вычислительное устройство умножения квадратных бинарных матриц тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Болгак Алексей Владимирович

• Болгак Алексей Владимирович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Болгак Алексей Владимирович

ВВЕДЕНИЕ

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ, АЛГОРИТМОВ И ПРАКТИЧЕСКИХ РЕАЛИЗАЦИЙ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ УМНОЖЕНИЯ БИНАРНЫХ МАТРИЦ С ЦЕЛЬЮ ОПРЕДЕЛЕНИЯ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЯ

1.1 Формализованное представление граф-схем алгоритмов управления

1.2 Постановка задачи оптимального разбиения графа

1.3 Классификация и методы формирования разбиений

1.4 Определение состава бинарных отношений в задачах на графах

1.5 Анализ эффективности и оптимизации программной реализации алгоритмов поиска транзитивного замыкания бинарного отношения, базирующегося на умножении матриц

1.6 Виды современного аппаратного обеспечения для практической реализации матричных вычислений

1.7 Программные и аппаратные подходы к реализации определения состава

бинарных отношений на основе матричных преобразований

Выводы по первой главе

ГЛАВА 2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ И МЕТОДА ОРГАНИЗАЦИИ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ ПАМЯТИ СПЕЦИАЛИЗИРОВАННОГО ВЫЧИСЛИТЕЛЬНОГО УСТРОЙСТВА УМНОЖЕНИЯ КВАДРАТНЫХ БИНАРНЫХ МАТРИЦ

2.1 Понятие матрицы отношений и ее свойства

2.2 Определение состава бинарных отношений вершин граф-схем параллельных алгоритмов

2.3 Алгоритмические подходы к поиску транзитивного замыкания бинарного отношения

2.4 Математическая модель и метод организации параллельно-конвейерной памяти

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

квадратных бинарных матриц

2

Выводы по второй главе

ГЛАВА 3. РАЗРАБОТКА СПЕЦИАЛИЗИРОВАННОГО

ВЫЧИСЛИТЕЛЬНОГО УСТРОЙСТВА УМНОЖЕНИЯ КВАДРАТНЫХ БИНАРНЫХ МАТРИЦ С КОНВЕЙЕРИЗАЦИЕЙ ОПЕРАЦИИ ЧТЕНИЯ ДАННЫХ ИЗ СПЕЦИАЛИЗИРОВАННОЙ МНОГОПОРТОВОЙ ПАМЯТИ

3.1 Специализированное вычислительное устройство умножения квадратных

бинарных матриц на базе многопортовой параллельно-конвейерной памяти

3.2. Структурно-функциональная организация специализированного вычислительного устройства умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти

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

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

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

3.2.4 Этап получения результатов работы специализированного вычислительного

устройства умножения квадратных бинарных матриц

Выводы по третьей главе

ГЛАВА 4. ОЦЕНКИ БЫСТРОДЕЙСТВИЯ И АППАРАТНОЙ СЛОЖНОСТИ СПЕЦИАЛИЗИРОВАННЫХ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ УМНОЖЕНИЯ КВАДРАТНЫХ БИНАРНЫХ МАТРИЦ

4.1 Сравнительная оценка временных затрат программных реализаций алгоритмов матричного умножения в зависимости от плотности и размера умножаемых матриц

4.2 Сравнительная оценка временных затрат на умножение квадратных бинарных

матриц разработанного специализированного вычислительного устройства с

устройством-прототипом и известными вычислительными устройствами

3

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

4.2.2 Оценка временных затрат на умножение квадратных бинарных матриц устройства-прототипа на базе систолических структур

4.2.3 Сравнительная оценка временных затрат на умножение матриц разработанного специализированного вычислительного устройства, устройства-прототипа на базе систолических структур и известных вычислительных устройств

4.3 Оценки аппаратной сложности разработанного специализированного вычислительного устройства и устройства-прототипа

4.3.1 Оценка аппаратной сложности устройства-прототипа на базе систолических структур

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

4.3.3 Анализ результатов, полученных в ходе оценок аппаратной сложности разработанного специализированного вычислительного устройства умножения квадратных бинарных матриц и устройства-прототипа на базе систолических

структур

Выводы по четвертой главе

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

Приложение

Приложение

Приложение

Приложение

Приложение

Приложение

4

Введение диссертации (часть автореферата) на тему «Математическая модель, метод организации параллельно-конвейерной памяти и специализированное вычислительное устройство умножения квадратных бинарных матриц»

ВВЕДЕНИЕ

Актуальность темы исследования. В основе вычислительно сложных научно-практических задач в высокопроизводительных вычислительных системах (ВС) лежит матричное умножение, существенно влияющее на время их решения. В частности, при решении ряда задач в области дискретной математики возникает необходимость в умножении бинарных матриц, подаваемых в ВС как внешние данные. К ним относятся задачи построения матрицы достижимости и контрдостижимости в графах общего вида, а также поиска транзитивного замыкания бинарного отношения, обладающего свойством транзитивности; также при проектировании систем логического управления (СЛУ) в базисе логических мультиконтроллеров (ЛМК) одной из вычислительно сложных задач является задача определения состава бинарных отношений граф-схем параллельных алгоритмов логического управления, в рамках которой в том числе необходимо выполнение транзитивного замыкания бинарного отношения следования для вершин граф-схем параллельных алгоритмов (В.А. Горбатов, И.В. Зотов, А.А. Баркалов, В.Г. Лазарев, А.Д. Закревский, С.И. Баранов, А.А. Шалыто, С.А. Юдицкий, S. Husson, В.И. Варшавский, R. Puri, T. Agerwala и др.); при работе с сетями Петри возникает ряд схожих задач, ориентированных на обработку бинарных отношений.

При практической реализации указанных выше процедур возникает возможность задействовать основные вычислительные ресурсы современных процессоров (CPU) и графических ускорителей (GPU), что позволяет увеличить реальную производительность вычислительной системы и уменьшить временные затраты на решение задачи за счет алгоритмической и высокоуровневой оптимизации соответствующей программной реализации. Для матричных вычислений используются программные реализации с различным набором алгоритмических и высокоуровневых оптимизаций (оптимизация работы кэшпамяти CPU, векторизация, многопоточные программные реализации, CUDA- и OpenCL-ориентированные программные реализации, их комбинации с

использованием инструментариев OpenMP и MPI) в зависимости от имеющегося в распоряжении класса аппаратного обеспечения.

В случае обработки больших (тысячи элементов и более) граф-схем алгоритмов на современных CPU поиск транзитивного замыкания бинарного отношения выполняется неприемлемо долго и достигает нескольких часов и более. Для уменьшения временных затрат на матричные вычисления существуют программно- и аппаратно-ориентированные подходы. При программной реализации возможно применение классического умножения матриц, основанного на трех вложенных циклах и поэлементном вычислении значений результирующей матрицы. Данный подход неэффективен, когда размер матриц превышает объем кэш-памяти CPU. В связи с этим на практике применяются различные алгоритмические подходы, позволяющие снизить число промахов кэш-памяти CPU и за счет этого увеличить реальную производительность вычислительной системы. Так, например, умножение с буферизацией столбца или блочное умножение позволяют эффективно использовать кэш-память CPU. Еще одним известным направлением для снижения временных затрат на выполнение матричных вычислений является умножение матриц на графических процессорах в рамках концепции выполнение неграфических вычислений на графических процессорах (GPGPU). В случае, если на программном уровне время выполнения операции умножения матриц оказывается неприемлемо долгим, то возможен перенос данной операции на аппаратный уровень.

Степень разработанности темы исследования. Существенный вклад в исследования в области оптимизации матричных умножений и вычислительных устройств для быстрого умножения матриц внесли С. Кун, В.М. Курейчик, Б.Я. Штейнберг, Н.А. Лиходед, В.И. Ян, С.В. Михляев, А.Н. Чаплиц, В.Н. Червяцов, А.А. Сердцев, В.П. Якуш, R.M. Rao, K. Barman, C.E. Leiserson, Q.E. Dolecek, Hsiang-Tsung Kung, P. Dighe и др., однако предложенные в существующих работах вычислительные устройства для умножения матриц и решения схожих задач на графах не учитывается специфика обработки бинарных матриц по

временной и аппаратной сложности, что ограничивает сферу практического применения известных аппаратно-программных решений в ВС.

Таким образом, возникает научное противоречие, выражающееся в необходимости повышения производительности специализированных вычислительных устройств и ростом их аппаратной сложности в существующих технических средствах. В связи с этим актуальной научно-технической задачей является разработка математической модели и метода, позволяющего снизить временные затраты на матричные умножения.

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

Для достижения поставленной цели в диссертационной работе сформулированы основные задачи:

1. Анализ существующих методов, алгоритмов и практических реализаций вычислительных устройств умножения бинарных матриц с целью определения направления исследования. Определение места вычислительных устройств умножения бинарных матриц в современных вычислительных системах.

2. Разработка математической модели и метода организации параллельно-конвейерной памяти специализированного вычислительного устройства умножения бинарных матриц.

3. Разработка структурно-функциональной организации специализированного вычислительного устройства умножения бинарных матриц на базе параллельно-конвейерной памяти.

4. Проведение вычислительных экспериментов, оценка быстродействия и аппаратной сложности разработанного специализированного вычислительного устройства умножения квадратных бинарных матриц на базе параллельно-конвейерной памяти.

Объект исследования: аппаратно-программные средства поддержки анализа и планирования параллельных вычислений в вычислительных системах, однородные системы логического управления.

Предмет исследования: алгоритмы и устройства обработки квадратных бинарных матриц.

Методология и методы исследования: методы математической логики, теории множеств и графов, проектирования дискретных систем и устройств ЭВМ, теории проектирования конечных автоматов.

Научная новизна и основные положения, выносимые на защиту:

1. Математическая модель параллельно-конвейерной памяти для быстрого умножения квадратных бинарных матриц, отличающаяся введением конвейеризации при чтении данных из специализированной многопортовой памяти, и позволяющая снизить временные затраты на операцию умножения матриц за счет совмещения обращений к ячейкам многопортовой памяти.

2. Метод организации параллельно-конвейерной памяти вычислительного устройства умножения квадратных бинарных матриц, основанный на многопортовом чтении данных из специализированной памяти, отличающийся введением конвейеризации при чтении данных и позволяющий снизить временные затраты на умножение матриц за счет параллельной обработки различных элементов матриц по ступеням конвейера.

3. Структурно-функциональная организация специализированного вычислительного устройства умножения квадратных бинарных матриц, основанная на использовании систолических вычислительных структур и многопортового матричного запоминающего устройства с двухкоординатной адресацией, отличающаяся введением конвейеризации при чтении данных, позволяющая уменьшить временные затраты на умножение бинарных матриц по сравнению с аналогами.

Теоретическая и практическая значимость результатов работы заключается в том, что реализация разработанных теоретических положений позволила:

снизить временные затраты на операцию умножения квадратных бинарных матриц разработанного специализированного вычислительного устройства на базе многопортовой параллельно-конвейерной памяти в зависимости от размера матриц до 52,4 раза на работу специализированного вычислительного устройства для п < 512; до 1,14 раз на работу с учетом однократной загрузки исходных данных в память специализированного вычислительного устройства, однократного выполнения операции умножения матриц и однократной выгрузку результирующих данных в оперативную память; до 2,25 раза в задаче поиска транзитивного замыкания бинарного отношения, когда загрузка исходных и выгрузка результирующих данных выполняется однократно, а операция умножения матриц выполняется log2« раз;

- разработать специализированное вычислительное устройство умножения квадратных бинарных матриц на базе многопортовой параллельно-конвейерной памяти, которое является наиболее производительным среди известных устройств при умножении квадратных бинарных матриц размером 8 < п < 512;

- применить разработанное специализированное вычислительное устройство умножения квадратных бинарных матриц с параллельно-конвейерной памятью для решения планово-аналитических задач в современных ВС, которые сводятся к операциям матричного умножения (достижимость и контрдостижимость, транзитивное замыкание бинарного отношения).

Реализация результатов работы. Результаты диссертационного исследования используются в образовательном процессе ФГБОУ ВО «Юго-Западный государственный университет» в рамках следующих дисциплин по направлению подготовки 09.03.01 «Информатика и вычислительная техника»: «Основы комбинаторной оптимизации», «Параллельное программирование», «Теоретические основы организации многопроцессорных комплексов и систем», а также внедрены в НИИЦ (г. Курск) ФГУП «18 ЦНИИ» МО РФ, что подтверждается соответствующими актами.

Соответствие паспорту специальности. Согласно паспорту научной

специальности 2.3.2. Вычислительные системы и их элементы (технические науки), научная проблема, рассмотренная в диссертационной работе, соответствует пунктам 5 и 7 паспорта специальности. В части пункта 5 «Разработка научных методов и алгоритмов организации арифметической, логической, символьной и специальной обработки данных, хранения и ввода-вывода информации» разработан метод организации параллельно-конвейерной памяти специализированного вычислительного устройства умножения квадратных бинарных матриц, основанный на многопортовом чтении данных из специализированной памяти, отличающийся введением конвейеризации при чтении данных и позволяющий снизить временные затраты на умножение квадратных бинарных матриц. В части пункта 7 «Разработка научных методов и алгоритмов организации параллельной и распределенной обработки информации, многопроцессорных, многоядерных, многомашинных и специальных вычислительных систем» разработан метод организации параллельно-конвейерной памяти, работающей в составе специализированного вычислительного устройства умножения квадратных бинарных матриц, основанный на многопортовом чтении данных из специализированной памяти, отличающийся введением конвейеризации при чтении данных, позволяющий снизить временные затраты на умножение квадратных бинарных матриц.

Достоверность научных положений, теоретических выводов и практических результатов диссертационной работы подтверждается корректным и обоснованным использованием математического аппарата теории множеств и графов, теории проектирования дискретных систем, соответствием результатов экспериментальных исследований выдвигаемым гипотезам, качественным и количественным результатам предшествующих научных исследований, публикациями в научных рецензируемых изданиях всероссийского и международного уровня.

Апробация результатов исследования. Основные теоретические

положения и научные результаты диссертационной работы докладывались,

обсуждались и получили положительную оценку на Всероссийских и

10

Международных научно-технических конференциях: IV Международная научнотехническая конференция «Облачные и распределенные вычислительные системы в электронном управлении» (г. Переславль-Залесский, 2023 г.); XVII международная научно-техническая конференция «Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений» (г. Курск, 2023 г.). XV Всероссийская межвузовская научная конференция «Наука и образование в развитии промышленной, социальной и экономической сфер регионов России» (г. Муром, 2023 г.); XXVII Международная научно-техническая конференция «Медико-экологические информационные технологии - 2024», посвященная 60-летию ЮЗГУ (г. Курск, 2024 г.); XVII Всероссийская межвузовская научная конференция «Наука и образование в развитии промышленной, социальной и экономической сфер регионов России» (г. Муром, 2025 г.); XVIII Международная научно-техническая конференция «Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений» (г. Курск, 2025 г.); на научно-технических семинарах, проводимых кафедрой вычислительной техники Юго-Западного государственного университета в течение 2022 - 2025 гг.

Личный вклад автора. Все выносимые на защиту научные результаты

получены соискателем лично. В опубликованных работах предложены: в [134]

приведены результаты вычислительных экспериментов и оценки временных затрат

на обработку квадратных бинарных матриц разработанным специализированным

вычислительным устройством; в [136] приведена оценка аппаратной сложности

разработанного вычислительного устройства умножения бинарных матриц; в [129]

описана математическая модель и структурно-функциональная организация

параллельно-конвейерной памяти специализированного вычислительного

устройства умножения бинарных матриц; в [130] создано вычислительное

устройство для умножения квадратных бинарных матриц, а также приведена

оценка временных затрат устройства на умножение бинарных матриц; в [113]

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

транзитивного замыкания бинарного отношения, обладающего свойством

11

транзитивности для ЭВМ; в [100] проведен обзор алгоритмов и практических реализаций операций обработки матриц; в [75] приведена оценка реальной производительности процессоров семейства Intel Core различных поколений при решении задачи умножения вещественных матриц для однопоточной программной реализации; в [97] описана алгоритмическая и высокоуровневая оптимизация в задаче умножения плотных квадратных вещественных матриц одинарной точности для однопоточной программной реализации с последующей оценкой реальной производительности; в [98] представлено сравнение реальной производительности вычислительных систем для CPU-ориентированных однопоточных программных реализаций операции умножения целочисленных и вещественных матриц; в [131, 132] предложено специализированное вычислительное устройство для умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти; в [116] представлена сравнительная оценка временных затрат программных реализацией алгоритмов Флойда-Уоршелла и матричного умножения в задаче поиска транзитивного замыкания бинарного отношения.

Публикации. Результаты проведенных диссертационных исследований опубликованы в 12 научных трудах, из них три статьи опубликованы в центральных рецензируемых научных журналах и изданиях по перечню ВАК при Минобрнауки России, 8 работ опубликованы в журналах, индексируемых в РИНЦ. Получено положительное решение о выдаче патента на изобретение (заявка № 2025104287 от 25.02.2025 г.) и 1 свидетельство о государственной регистрации программы для ЭВМ (№ 2025664497 от 04.06.2025 г.).

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 136 наименований. Основная часть работы изложена на 110 страницах машинописного текста и содержит 36 рисунков, 18 таблиц.

ГЛАВА 1. АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ, АЛГОРИТМОВ И ПРАКТИЧЕСКИХ РЕАЛИЗАЦИЙ ВЫЧИСЛИТЕЛЬНЫХ УСТРОЙСТВ УМНОЖЕНИЯ БИНАРНЫХ МАТРИЦ С ЦЕЛЬЮ ОПРЕДЕЛЕНИЯ НАПРАВЛЕНИЯ ИССЛЕДОВАНИЯ

1.1 Формализованное представление граф-схем алгоритмов управления

Необходимость анализа и обработки параллельных алгоритмов возникает в решении различных задач. Одним из способов представления алгоритмов является использование взвешенных ориентированных графов специального типа. В этих графах вершины отображают операции, а дуги - направление передачи управления. У такого класса графов имеются специфические свойства, которые не характерны для графов общего вида. Эти особенности позволяют значительно упростить выполнение преобразований при учете этих свойств в методах, алгоритмах и их практических реализациях.

Для формализации описания параллельных алгоритмов логического управления необходимо разработать их структурированное представление. Согласно работам [1-4], для этого применяется язык графических схем. Данный язык обеспечивает наглядность представления алгоритма в виде графического изображения и позволяет формализовать его через граф. При использовании граф-схем алгоритм можно представить как конечный связный ориентированный граф G = (А, V), где вершины, обозначенные как аг- 6 А, I = 1 , Ы, соответствуют операторам, а дуги щ = а, щ 6 V, V Я А х А, k = 1, М, /, j = 1 , N з адают порядок следования операторов, где N = |А| - количество вершин, а М = V - количество

дуг [5].

Выделим два основных типа вершин, включенных в граф-схему алгоритма:

1. Операторные вершины - имеют одну входящую и одну исходящую дугу, и изображаются в виде прямоугольников.

2. Условные вершины - могут иметь две или более исходящих дуг и одну входящую, и изображаются в виде ромбов.

Приведем детальное описание каждого из типов вершин (см. табл. 1.1).

Таблица 1.1 - Типы вершин, их графическое представление и описание

Тип вершины

Графическое обозначение

Описание

Начальная вершина

Т

Данный тип

вершины имеет только одну

исходящую дугу, обозначаемую (анач)

Конечная вершина

Данный тип

вершины имеет только одну

входящую дугу, обозначаемую (акон)

Операторная вершина

В данной вершине записываются один или несколько

операторов алгоритма, в составе которых может находиться множество микроопераций вида ¥{а1) = , у2 .

Ут}, У1} е ^ I = Ь Г, Т = 1УЩ_

Условная вершина

В данной вершине представлены идентификаторы проверяемых логических условий, содержащие множество логических выражений Х(аг) = {х11, х2, •••, xiS}, х^ еХо, ] = ГГ , 5 =

№,)|_

Продолжение таблицы 1.1

Тип вершины

Графическое обозначение

Описание

Вершина распараллеливания / синхронизации

Имеет две и более исходящих дуг и одну входящую, тогда как вершина синхронизации имеет одну

исходящую и

несколько входящих дуг.

Вершина объединения альтернативных дуг

К

Используется для

однозначной

идентификации

завершения

альтернативных

ветвлений

алгоритма. Такие вершины

встречаются парами с

соответствующими им условными вершинами и имеют две или более входящих дуг и одну исходящую._

Допускаются случаи, когда целесообразно применение объединения нескольких вершин в одну обобщенную, что позволяет уменьшить размерность решаемой задачи. Вершина такого вида может содержать как логические условия, так и микрооперации.

Для описания специального класса параллельных алгоритмов используется язык параллельных граф-схем алгоритмов (ПарГСА) [5-7].

Исходя из вышесказанного следует, что взвешенный ориентированный граф моделируется на основе графической схемы параллельного алгоритма управления G, при этом характеристики дуг и вершин зависят от конкретного типа и набора

параметров. Исходный граф О0 обычно содержит ограниченное количество вложенных структур различных типов, не является цикличным и не имеет верхних ограничений по размеру. Поскольку взвешенный граф не всегда является точной графической схемой параллельного алгоритма, в ходе обработки, его анализ ограничивается рассмотрением подмножества схем, удовлетворяющих требованиям безопасности, живости и устойчивости [8].

1.2 Постановка задачи оптимального разбиения графа

Взвешенный неориентированный граф О представляет собой подходящую и естественную модель для распределения подзадач (в том числе компонентных алгоритмов логического управления) между вычислительными узлами (процессорными элементами, логическими контроллерами и т.п.). Этот граф О = (Л, V) задан множеством рёбер V и множеством вершин А, где каждая вершина отображает задачу, а вес вершины указывает количество операций, необходимых для её выполнения. Вес рёбер, в свою очередь, моделирует затраты на обмен данными между задачами.

В рамках данной модели формируется задача разбиения множества вершин

графа А на непересекающиеся подмножества, что в свою очередь эквивалентно

декомпозиции исходного графа О0 на непересекающиеся подграфы. Каждый из

подграфов данного вида ассоциируется с конкретным процессором, который будет

выполнять задачи, соответствующие вершинам подграфа. Таким образом, из

вышеописанного следует, что задача оптимального распределения

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

разделения графа. Данная задача принадлежит к классу ЫР - полной, что

исключает возможное нахождение оптимального решения за полиномиальное

время для реальных управляющих алгоритмов. Поэтому на практике для её

решения применяются эвристические методы, такие как методы ограниченного

перебора, жадные алгоритмы, случайный и взвешенный случайный перебор,

методы муравьиной и пчелиной колонии, генетические алгоритмы, роевые методы

и метод параллельно-последовательной декомпозиции [9-10]. Для корректной

работы этих методов необходимо учитывать бинарные отношения между

16

вершинами в параллельных граф-схемах алгоритмов управления, что обеспечивает исключение параллельных вершин внутри отдельных блоков разбиения.

Таким образом, основная задача оптимального разбиения сводится к представлению исходного параллельного алгоритма логического управления в виде множества взаимосвязанных последовательных блоков, каждый из которых обладает ограниченной вычислительной сложностью и обеспечивает эффективное распределение вычислительной нагрузки и минимизацию межпроцессорного взаимодействия.

Задача оптимального разбиения сопровождается двумя видами ограничений, описанных в таблице 1.2.

Таблица 1.2 - Классификация ограничений и их описание

Ограничение Описание

Технологическое ограничение Каждому блоку разбиения должен соответствовать отдельный контроллер в структуре системы логического управления (СЛУ). В результате, блоки должны соответствовать ограничениям аппаратного обеспечения.

Структурное ограничение В каждом блоке разбиения не могут присутствовать вершины из различных параллельных ветвей, что необходимо для упрощения структуры контроллера, который будет исполнять последовательную микропрограмму.

Аппаратная сложность системы логического управления (СЛУ) напрямую зависит от количества задействованных контроллеров, и её снижение достигается путём оптимизации структуры разбиения алгоритма управления, что приводит к уменьшению числа формируемых блоков.

Комплекс параллельно функционирующих контроллеров, объединённых в мультиконтроллер, обеспечивает реализацию высокоуровневых параллельных алгоритмов управления посредством декомпозиции задачи на вычислительно ограниченные блоки, при этом теоретически допускается неограниченный размер этих блоков.

Эффективность разбиения алгоритма играет ключевую роль в сокращении аппаратных затрат и повышении производительности системы, обеспечивая оптимальный баланс между степенью параллелизма и числом аппаратных модулей.

1.3 Классификация и методы формирования разбиений

Современные методологические подходы и алгоритмические решения для задачи построения разбиений могут быть условно разделены на два основных класса: последовательные и итерационные [9-41].

Методы последовательного типа основываются на формировании единственного решения без полного перебора пространства вариантов. В процессе формирования разбиения алгоритма управления происходит поэтапный отбор вершин, ещё не включённых в существующие блоки, с целью идентификации оптимального кандидата для присоединения к текущему подмножеству. Выбор определяется с применением совокупности частных критериев и эвристических правил, которые в совокупности коррелируют с целевой функцией оптимальности разбиения. Данная процедура продолжается до тех пор, пока все вершины не будут распределены между блоками.

Классическими примерами методов данной категории являются жадные алгоритмы, в частности, предложенные Барановым С.И. [9] и их последующие модификации, а также методы, основанные на принципе параллельно-последовательной декомпозиции. Существенным недостатком этих методов является склонность к фиксации в локальных экстремумах без возможности проведения многошагового прогноза последствий выбора, что негативно сказывается на качестве сформированных разбиений.

Итерационные методы ориентированы на поиск оптимального или

приближенного решения путём систематического исследования множества

18

потенциальных вариантов разбиений в соответствии с заданными эвристическими или стохастическими правилами. Многие из этих алгоритмов требуют начального приближенного решения, формируемого либо случайным образом, либо посредством применения последовательного метода. Завершение работы итерационных алгоритмов происходит при достижении заданного количества итераций или по истечении установленного временного лимита.

Список литературы диссертационного исследования кандидат наук Болгак Алексей Владимирович, 2025 год

СПИСОК ЛИТЕРАТУРЫ

1. Зотов И.В. Организация и синтез микропрограммных мультимикроконтроллеров / Зотов И.В., Колосков В.А., Титов В.С. и др. // Курск: ГУИПП «Курск», 1999. 368 с.

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

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

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

5. Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы) / С.И. Баранов // Л.: Энергия, 1979. 232 с.

6. Лазарев В.Г. Синтез управляющих автоматов / В.Г. Лазарев, Е.И. Пийль // М.: Энергоатомиздат, 1989. 328 с.

7. Варшавский В.И. Автоматное управление асинхронными процессами в ЭВМ и дискретных системах / под ред. В.И. Варшавского // М.: Наука, 1986. 400 с.

8. Закревский А.Д. Декомпозиция параллельных алгоритмов логического управления по заданному разбиению множества предложений / Закревский А.Д., Поттосин Ю.В. // А и ВТ. 1985. № 4. С. 65-72.

9. Баранов, С.И. Обобщенный метод декомпозиции граф-схем алгоритмов / С.И. Баранов, Л.Н. Журавина, В.А. Песчанский // А и ВТ. 1982. №5. С. 43-51.

10. Ватутин Э.И. Библиотека функций построения разбиений методом С.И. Баранова с жадным последовательным формированием блоков / Ватутин Э.И. // Свидетельство о государственной регистрации программы для ЭВМ №2010612902 от 28.04.10

11. Ватутин Э.И. Метод формирования субоптимальных разбиений параллельных управляющих алгоритмов / Ватутин Э.И., Зотов И.В. // Труды II международной конференции «Параллельные вычисления и задачи управления» РАСО '04 памяти Е.Г. Сухова. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2004. С. 884-917.

12. Ватутин Э.И., Зотов И.В. Параллельно-последовательный метод формирования субоптимальных разбиений параллельных управляющих алгоритмов / Ватутин Э.И., Зотов И.В. // Свидетельство об официальной регистрации программы для ЭВМ № 2005613091 от 28.11.05.

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

14. Ватутин Э.И. Анализ эффективности и программная оптимизация методов синтеза разбиений параллельных алгоритмов логического управления в среде РАЕ / Ватутин Э.И. // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. Курск, изд-во ЮЗГУ, 2012. № 2. Ч. 1. С. 191-195.

15. Ватутин Э.И. Анализ узких мест программной реализации метода параллельно-последовательной декомпозиции граф-схем параллельных алгоритмов / Ватутин Э.И. // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2013). Курск, изд-во ЮЗГУ, 2013. С. 235-237.

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

17. Шумаков В.А. Разбиение алгоритмов логического управления на блоки методом полного перебора / Шумаков В.А., Ватутин Э.И. // Тезисы докладов XXXVI межвузовской научно-технической конференции студентов и аспирантов в области научных исследований «Молодежь и XXI век». Ч. 1. Курск: изд-во КурскГТУ, 2008. С. 53-54.

18. E.I. Vatutin Comparison of Methods for Getting Separation of Parallel Logic Control Algorithms / E.I. Vatutin, J.N. Abdel-Jalil, M.H. Najajra, I.V. Zotov // Information and Telecommunication Technologies in Intelligent Systems (ITTIS'06). Katania, Italy, 2006. PP. 92-94.

19. Ватутин Э.И. Методология сравнительной оценки методов нахождения разбиений параллельных алгоритмов логического управления при синтезе логических мультиконтроллеров / Ватутин Э.И. // Информационно-математические технологии в экономике, технике и образовании. Екатеринбург, 2007. С. 259-261.

20. Ватутин Э.И. Сравнительная оценка методов нахождения разбиений параллельных алгоритмов логического управления в условиях присутствия технологических ограничений / Ватутин Э.И. // Информационно-математические технологии в экономике, технике и образовании. Екатеринбург, 2007. С. 261-263.

21. Ватутин Э.И. Комплексная сравнительная оценка методов выбора разбиений при проектировании логических мультиконтроллеров / Ватутин Э.И., Волобуев С.В., Зотов И.В. // Труды VII международной конференции «Идентификация систем и задачи управления» SICPR0'08. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2008. С. 1917-1940.

22. Ватутин Э.И. Анализ тенденций изменения значений критериев качества разбиений с ростом размера алгоритмов управления / Ватутин Э.И., Кобзарь Е.Ю. // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2008). Ч. 1. Курск: изд-во КурскГТУ, 2008. С. 89-90.

23. Ватутин Э.И. Комплексный сравнительный анализ качества разбиений

при синтезе логических мультиконтроллеров в условиях присутствия

99

технологических ограничений / Ватутин Э.И., Волобуев С.В., Зотов И.В. // Труды четвертой международной конференции «Параллельные вычисления и задачи управления» PACO'08. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2008. С. 643-685.

24. Ватутин Э.И. Анализ качества блочных разбиений при синтезе логических мультиконтроллеров / Ватутин Э.И., Зотов И.В. // Информационно-измерительные и управляющие системы. № 10, Т. 6. М.: «Радиотехника», 2008. С. 32-38.

25. Ватутин Э.И. Сравнение методов синтеза разбиений параллельных алгоритмов логического управления с использованием двухпараметрических диаграмм / Ватутин Э.И., Титов В.С. // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2012). Курск: изд-во ЮЗГУ, 2012. С. 138-140.

26. Ватутин Э.И. Сравнение методов синтеза разбиений граф-схем параллельных алгоритмов с использованием двумерных диаграмм / Ватутин Э.И., Титов В.С. // Известия Юго-Западного государственного университета. Курск, изд-во ЮЗГУ, 2012. № 3 (42), 2012. С. 66-74.

27. Ватутин Э.И. Использование добровольных распределенных вычислений на платформе BOINC для анализа качества разбиений граф-схем параллельных алгоритмов / Ватутин Э.И., Титов В.С. // Параллельные вычисления и задачи управления (PACO'12). М.: ИПУ РАН, 2012. Т. 2. С. 37-54.

28. Ватутин Э.И. Расчетный модуль для построения разбиений параллельных алгоритмов логического управления с использованием добровольных распределенных вычислений / Ватутин Э.И., Валяев С.Ю. // Свидетельство о государственной регистрации программы для ЭВМ №2 2013618013 от 28.08.13.

29. Ватутин Э.И. Анализ результатов применения метода случайного перебора в задаче поиска разбиений граф-схем параллельных алгоритмов / Ватутин Э.И., Колясников Д.В., Титов В.С. // Известия Южного федерального университета.

Технические науки. 2014. № 12 (161). С. 102-110.

100

30. Ватутин Э.И. Анализ областей качественного превосходства последовательных эвристических методов синтеза разбиений при проектировании логических мультиконтроллеров / Ватутин Э.И., Титов В.С. // Известия высших учебных заведений. Приборостроение. 2015. Т. 58. № 2. С. 115-122. DOI: 10.17586/0021-3454-2015-58-2-115-122.

31. Титов В.С. Анализ вероятности получения субоптимальных решений при использовании смежной жадной стратегии синтеза разбиений / Титов В.С., Ватутин Э.И., Валяев С.Ю., Андреев А.Л. // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2015). Курск, 2015. С. 363-365.

32. Vatutin E.I. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing / Vatutin E.I., Valyaev S.Yu., Titov V.S. // BOINC: FAST, 2015.

33. Ватутин Э.И. Псевдослучайное разбиение параллельных управляющих алгоритмов / Ватутин Э.И., Евглевский К.О. // Тезисы докладов XXXIII вузовской научно-технической конференции студентов и аспирантов в области научных исследований «Молодежь и XXI век». Ч. 1. Курск: изд -во КурскГТУ, 2005. С. 2425.

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

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

36. Dorigo M. Optimization, Learning and Natural Algorithms / Dorigo M. // PhD thesis. Politecnico di Milano, Italie, 1992.

37. D. Dervis K. An Idea Based On Honey Bee Swarm for Numerical Optimization / D. Dervis K. // Technical Report-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 2005.

38. Гладков Л.А. Генетические алгоритмы / Гладков Л.А., Курейчик В.В., Курейчик В.М. // 2-е изд., испр. и доп. М.: Физматлит, 2006. 320 с.

39. Kirkpatrick, S. Optimization by Simulated Annealing / Kirkpatrick, S., Gelatt Jr, C. D., Vecchi, M. P. // 1983. Science 220 (4598): 671-680. DOI: 10.1126/science.220.4598.671.

40. Ватутин Э.И. Расчетный модуль для тестирования комбинаторных оптимизационных алгоритмов в задаче поиска кратчайшего пути в графе с использованием добровольных распределенных вычислений / Ватутин Э.И., Валяев С.Ю., Дремов Е.Н., Мартынов И.А., Титов В.С. // Свидетельство о государственной регистрации программы для ЭВМ № 2014619797 от 22.09.14.

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

42. «Связный граф» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ra.wikipedia.org/wiki/Связный_граф (дата обращения: 23.09.2023 г.)

43. «Связность графов» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/Связность_графов (дата обращения: 23.09.2023 г.)

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

45. «Алгоритм Ли» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/Алгоритм_Ли (дата обращения: 23.09.2023 г.)

46. «Поиск в ширину» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/Поиск_в_ширину (дата обращения: 23.09.2023 г.)

47. Патент РФ № 2371766, МПК8 G06N7/00, G06F17/00. Устройство для исследования графов / Ватутин Э.И., Зотов И.В. Опубл. 27.10.2009, бюл. № 30.

48. А. с. 304604 СССР, МКИ3 G06G 7/48. Устройство для определения характеристик связности вероятностного графа / А.Н. Чаплиц, В.В. Епихин, В.И. Ян. Опубл. 1971, Бюл. № 17.

49. А. с. 314214 СССР, МКИ3 G06G 7/48. Устройство для исследования вероятностных графов / В.В. Епихин, А.Н. Чаплиц, В.И. Ян. Опубл. 1971, Бюл. 27.

50. А. с. 433504 СССР, МКИ3 G06G 7/48. Устройство для определения характеристик связности вероятностного графа / Р.В. Тверицкий. Опубл. 1974, Бюл. № 23.

51. А. с. 468244 СССР, МКИ3 G06F 15/20. Устройство для исследования связности вероятностного графа / В.В. Епихин. Опубл. 1975, Бюл. № 15.

52. А. с. 637822 СССР, МКИ3 G06F 15/20. Устройство для исследования связности вероятностного графа / В.В. Епихин. Опубл. 1978, Бюл. № 46.

53. «Компонента связности графа» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ra.wikipedia.org/wiki/Компонента_связности_графа (дата обращения: 05.10.2023 г.).

54. А. с. 1101834 СССР, МКИ3 G06F 15/20. Устройство для определения характеристик графа / В.М. Глушань, В.М. Курейчик, Л.И. Щербаков, Ю.Е. Шведенко, В.Н. Гуров. Опубл. 1984, Бюл. № 25.

55. А. с. 1304033 СССР, МКИ3 G06F 15/20. Устройство для исследования характеристик вероятностных графов / В.М. Глушань, И.Н. Сердюков. Опубл. 1987, Бюл. № 14.

56. А. с. 1377867 СССР, МКИ3 G06F 15/20. Устройство для моделирования графов / В.В. Васильев, В.Л. Баранов. Опубл. 1988, Бюл. № 8.

57. А. с. 1418736 СССР, МКИ3 G06F 15/20. Устройство для анализа параметров графа / В.В. Васильев, В.Л. Баранов. Опубл. 1988, Бюл. № 31.

58. А. с. 1658171 СССР, МКИ3 G06F 15/419. Устройство для решения задач

на графах / В.В. Васильев, В.Л. Баранов. Опубл. 1991, Бюл. №23.

103

59. А. с. 1765832 СССР, МКИ3 G06F 15/419. Устройство для решения задач на графах / С.А. Ильин, С.В. Листровой, В.Я. Певнев [и др.]. Опубл. 1992, Бюл. № 36.

60. А. с. 2100838 СССР, МКИ3 G06F 15/173. Устройство для решения задач на графах / В.М. Игнатьев, Н.Ю. Афанасьева, А.Н. Крючков. Опубл. 1997, Бюл. № 32.

61. А. с. 877552 СССР, МКИ3 G06F 15/20. Устройство для исследования графов / А.П. Германюк, В.А. Калашников, В.А. Литвиненко [и др.]. Опубл. 1981, Бюл. № 40.

62. Dijkstra E. W. A note on two problems in connexion with graphs // Numerische Mathematik. V. 1 (1959), P. 269-271.

63. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87-90, 1958.

64. L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

65. Floyd, Robert W. Algorithm 97: Shortest Path. Communications of the ACM 5 (6): 345. June 1962. DOI:10.1145/367766.368168.

66. Warshall, Stephen. A theorem on Boolean matrices. Journal of the ACM 9 (1): 11-12. January 1962. DOI:10.1145/321105.321107.

67. Rosen, K.H. 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.

68. «Компонента сильной связности в орграфе» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/Компонента_сильноИ_связности_в_орграфе (дата обращения: 12.10.2023 г.).

69. Ватутин Э.И. Выявление тел циклов при обработке граф-схем параллельных алгоритмов с использованием компонент сильной связности / Ватутин Э.И. // Оптико-электронные приборы и устройства в системах

распознавания образов, обработки изображений и символьной информации (Распознавание - 2015). Курск, 2015. С. 83-85.

70. Седжвик Р. Алгоритмы на графах / Седжвик Р. // 3-е изд. СПб: «ДиаСофтЮП», 2002. 496 с.

71. В.В. Воеводин Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. // СПб.: БХВ-Петербург, 2002. 608 с.

72. Каляев И.А. Децентрализованные системы компьютерного управления / Каляев И.А., Мельник Э.В. // Ростов на Дону: изд-во ЮНЦ РАН, 2011. 196 с.

73. Кожин А.С Методы оптимизации времени доступа в общий кэш многоядерного микропроцессора / Кожин А.С, Недбайло Ю.А. // Вопросы радиоэлектроники. - 2017. - № 3. - С. 27-32.

74. Егунов В.А. О влиянии кэш-памяти на эффективность программной реализации базовых операций линейной алгебры / Егунов В.А. // Прикаспийский журнал: управление и высокие технологии. - 2018. - № 3. - C. 88-96.

75. Болгак А.В. Оценка реальной производительности процессоров семейства Intel Core различных поколений в задаче умножения вещественных матриц для однопоточной программной реализации / Болгак А.В., Ватутин Э.И. // Облачные и распределенные вычислительные системы в электронном управлении. ОРВС - 2023 : сборник трудов 4-й международной научно-технической конференции (28 ноября - 1 декабря 2023 года) / ред. кол.: И.И. Курочкин [и др.] ; ИПС РАН. Переславль-Залесский. - Курск: Изд-во ЗАО «Университетская книга». - 2024. - С. 98-100.

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

77. Ватутин Э.И. Оценка реальной производительности современных

процессоров в задаче умножения матриц для однопоточной программной

реализации с использованием расширения SSE (часть 2) / Ватутин Э.И., Титов В.С.

105

// Известия Юго-Западного государственного университета. 2015. Т. 1. № 5 (62). С. 8-16.

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

79. Старовойтов И.Н Параллельные вычисления на графических процессорах / Старовойтов И.Н, Ревняков Е.Н., Полякова Е.Н. // Первая Международная научная конференция по проблемам цифровизации: EDCRUNCH URAL - 2020: материалы конференции (Екатеринбург, 29-30 сентября 2020 г.); М-во науки и высш. образования РФ. - Екатеринбург: Изд-во Урал. ун-та, 2020. С. 314-319. URL: https://elar.urfu.ru/bitstream/10995/94924/1/978-5-7996-3118-5_2020_037.pdf.

80. Ватутин Э.И. Оценка реальной производительности современных видеокарт с поддержкой технологии CUDA в задаче умножения матриц / Ватутин Э.И., Мартынов И.А., Титов В.С. // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2014. № 2. С. 8-17.

81. Volker S. Gaussian Elimination is not Optimal // Numerische Mathematik. Springer Science+Business Media. - 1969. - Vol. 13, Iss. 4. - P. 354-356.

82. Don C., Shmuel W. Matrix Multiplication via Arithmetic Progressions // Journal of Symbolic Computation. - 1990, P. 251-280.

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

84. Bini D., Capovani M., Lotti G., Romani F. - O(n27799) complexity for approximate matrix multiplication. - Inform. Process. Lett., 1979.

85. Schonhage A. Partial and total matrix multiplication. - SIAM J. Comput., 1981.

86. «BOINC» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/BOINC (дата обращения: 08.11.2023 г.).

87. Ватутин Э.И. Добровольный метакомпьютинг: современное состояние и перспективы развития / Ватутин Э.И. // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2010). Курск: изд-во КурскГТУ, 2010. С. 164-166.

88. «GPGPU» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/GPGPU (дата обращения: 10.11.2023 г.).

89. «Intel MIC» [Электронный ресурс]: Википедия. Свободная энциклопедия. - URL: https://ru.wikipedia.org/wiki/Intel_MIC (дата обращения: 12.11.2023 г.).

90. Каляев И.А. Реконфигурируемые мультиконвейерные вычислительные структуры / Каляев И.А., Левин И.И., Семерников Е.А., Шмойлов В.И. // Ростов на Дону: изд-во ЮНЦ РАН, 2008. 320 с.

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

92. Курейчик В.М. Комбинаторные аппаратные модели и алгоритмы в САПР / В.М. Курейчик, В.М. Глушань, Л.И. Щербаков // М.: Радио и связь, 1990. 216 с.

93. Thoma F. MORPHEUS: Heterogeneous Reconfigurable Computing /

Thoma F., Kuhnle M., Bonnot P., Panainte E.M., Bertels K., Goller S., Schneider A., Gu

etant S., Schuler E., Müller-Glaser K.D., Becker J. // Field Programmable Logic and

Applications, 2007. FPL 2007. P. 409-414. DOI: 10.1109/FPL.2007.4380681

107

94. Тасит Мурки Закон Мура против нанометров / Тасит Мурки // iXBT, 2011. URL: http://www.ixbt.com/cpu/microelectronics.shtml.

95. «Параллельные методы матричного умножения» [Электронный ресурс]: Национальный Открытый Университет «ИНТУИТ». - URL: http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=1 (дата обращения: 21.11.2023 г.).

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

97. Болгак А.В. Алгоритмическая и высокоуровневая оптимизация в задаче умножения плотных квадратных вещественных матриц одинарной точности для однопоточной программной реализации с последующей оценкой реальной производительности / Болгак А.В., Ватутин Э.И. // Наука и образование в развитии промышленной, социальной и экономической сфер регионов России. XV Всероссийские научные Зворыкинские чтения: сб. тез. докл. Всероссийской научной конференции. Муром, 3 февр. 2023 г.- Муром: МИ ВлГУ, 2023. - 494 с.: ил.- [Электронный ресурс]: 1 электрон. опт. диск (CD-ROM). ISSN 2220-8763 (CD-ROM) ISSN 2222-2979 (Online). Режим доступа: https://www.mivlgu.ru/conf/zvorykin2023/pdf/sec11_full.pdf.

98. Болгак А.В. Сравнение реальной производительности вычислительных систем для CPU-ориентированных однопоточных программных реализаций операции умножения целочисленных и вещественных матриц / Болгак А.В., Ватутин Э.И., Яхья А.З.Б. // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений. Сборник материалов XVII международной научно-технической конференции. Курск, 2023. С. 73-75.

99. L.E. Cannon A cellular computer to implement the Kalman Filter Algorithm / L.E. Cannon // Technical report. Ph.D. Thesis. - Montana State University. - 14.07.1969.

100. Болгак А.В. История развития операций и алгоритмов обработки матриц / Болгак А.В., Ватутин Э.И. // Исторические, философские, методологические проблемы современной науки: сборник статей 6-й Международной научной конференции молодых ученых, 19 мая 2023 г. / редкол.: И. А. Асеева (отв. ред.) [и др.]; Минобрнауки России, Юго-Западный гос. ун-т. -Курск: ЮЗГУ, 2023. - 452 с. ISBN: 978-5-7681-1644-6.

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

102. Ватутин, Э.И. Вспомогательные операции перебора сечений в задаче оптимального разбиения параллельного управляющего алгоритма / Э.И. Ватутин // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2003): сб. матер. / Курск. гос. техн. ун-т. 2003. Т. 2. С. 238-239.

103. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес // М.: Мир, 1978. 432 с.

104. Евстигнеев, В.А. Применение теории графов в программировании / В.А. Евстигнеев // М.: Наука, 1983. 354 с.

105. Берж, К. Теория графов и ее применения / К. Берж // М.: Изд-во иностр. лит., 1962. 320 с.

106. Асанов, М.О. Дискретная математика: графы, матроиды, алгоритмы / М.О. Асанов, В.А. Баранский, В.В. Расин // Ижевск: НИЦ «РХД», 2001. 288 с.

107. Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман // М.: Мир, 1984. 454 с.

108. Оре, О. Теория графов / О. Оре // М.: Наука, 1980. 336 с.

109. Уилсон, Р. Введение в теорию графов / Р. Уилсон // М.: Мир, 1977. 208

с.

110. Татт, У. Теория графов / У. Татт // М.: Мир, 1988. 424 с.

111. Харари, Ф. Теория графов / Ф. Харари // М.: Мир, 1973. 300 с.

109

112. Майника, Э. Алгоритмы оптимизации на сетях и графах / Э. Майника // М.: Мир, 1981. 324 с.

113. Болгак А.В. Программа для умножения бинарных матриц при поиске транзитивного замыкания бинарного отношения / Болгак А.В., Ватутин Э.И. // Свидетельство о государственной регистрации программы для ЭВМ № 2025664497. Заявл. 15.05.2025 г.; зарегистрировано 04.06.2025 г.

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

672 с.

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

116. Болгак А.В. Сравнительная оценка временных затрат программных реализацией алгоритмов Флойда-Уоршелла и матричного умножения в задаче поиска транзитивного замыкания бинарного отношения / Болгак А.В., Ватутин Э.И. // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений. Распознавание - 2025: сборник материалов XVIII Международной научно-технической конференции, 9-12 сентября 2025 года / ред. кол.: С. Г. Емельянов [и др.]; Минобрнауки России, Юго-Западный гос. ун-т.

- Курск: ЮЗГУ, 2025. - 302 с. ISBN 978-5-7681-1736-8.

117. Штейнберг Б.Я. Блочно-рекурсивное параллельное перемножение матриц / Штейнберг Б.Я. // Известия ВУЗов. Приборостроение. - Т. 52, №10. - 2009.

- С. 33-41.

118. Егунов В.А. О влиянии кэш-памяти на эффективность программной реализации базовых операций линейной алгебры / Егунов В.А. // Прикаспийский журнал: управление и высокие технологии. - 2018. - № 3. - C. 88-96.

119. Юшин А.М. Справочник. Оптоэлектронные приборы и их зарубежные аналоги // Издательство «РадиоСофт». - Москва, 2000. - Т.1. - 512 с.

120. Белов П.А., Беспалов В.Г., Васильев В.Н., Козлов С.А., Павлов А.В., Симовский К.Р., Шполянский Ю.А. Оптические процессоры: достижения и новые идеи // В кн.: Проблемы когерентной и нелинейной оптики. - СПб, 2006. - С. 6-36.

121. Плаксиенко В.С., Плаксиенко Н.Е., Плаксиенко С.В. Устройства приема и обработки сигналов: Учебное пособие для вузов // М.: Учебно-методический издательский центр «Учебная литература». - 2004. - 376 с.: ил.

122. Лобач В.Т., Потипак М.В. Основы проектирования цифровых устройств радиоэлектронных систем: учебное пособие // Южный федеральный университет. Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета. - 2020. - 140 с.

123. Сырямкин В.И. Интеллектуальные системы 4-й промышленной революции: сборник материалов IV Международного форума, г. Томск, 15-16 декабря 2021 г. // Томск : STT. - 2022. - 104 с.

124. Одинец А.И., Науменко А.П. Цифровые устройства: АЦП и ЦАП: Учеб. пособие // Омск : Изд-во ИРСИД. - 2006. - 48 с.

125. Gumu§kaya Haluk, Orencik Bulent A parallel pipelined computer architecture for digital signal processing // Turkish Journal of Electrical Engineering and Computer Sciences. - 1998. - Vol. 6. - No. 2. - Article 4. - P. 107-130.

126. Строгонов А.В. Основы цифровой обработки сигналов // Воронеж : ФГБОУ ВПО «Воронежский государственный технический университет». - 2014.

127. Гвоздева С.Н. Устройство для умножения бинарных матриц / Гвоздева С.Н., Ватутин Э.И., Пшеничных А.О., Титов В.С. // Патент РФ на полезную модель № 193927. Заявл. 26.06.2019, опубл. 21.11.2019.

128. Гвоздева С.Н. Оценка быстродействия устройства с систолической структурой для умножения бинарных матриц / Гвоздева С.Н., Ватутин Э.И., Титов В.С. // Телекоммуникации. - Т. 3. - 2020. - С. 2-10.

129. Болгак А.В. Математическая модель и структурно-функциональная организация параллельно-конвейерной памяти устройства для быстрого умножения квадратных бинарных матриц / А.В. Болгак, Э.И. Ватутин // XXI век:

итоги прошлого и проблемы настоящего плюс. - 2025. - Т. 14. - № 2(70). - С. 2734. - EDN: EKKWZP.

130. Болгак А.В. Устройство для умножения бинарных матриц / Болгак А.В., Ватутин Э.И. // Положительное решение о выдаче патента на изобретение. Заявл. № 2025104287 от 25.02.2025 г.

131. Болгак А.В. Систолическое устройство для быстрого умножения квадратных бинарных матриц / Болгак А.В., Ватутин Э.И. // Медико-экологические информационные технологии - 2024. Сборник научных статей по материалам XXVII Международной научно-технической конференции. Курск, 2024. С. 7-11. -ISBN 978-5-7681-1704-7.

132. Болгак А.В. Устройство для умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти / Болгак А.В., Ватутин Э.И. // Наука и образование в развитии промышленной, социальной и экономической сфер регионов России. XVI Всероссийские научные Зворыкинские чтения: сб. тез. докл. Всероссийской научной конференции. Муром, 31 янв. 2025 г.- Муром: МИ ВлГУ, 2025. - 416 с.: ил.- [Электронный ресурс]: 1 электрон. опт. диск (CD-ROM). ISSN 2220-8763 (CD-ROM) ISSN 2222-2979 (Online). Режим доступа: https://www.mivlgu.ru/conf/zvorykin2025/pdf/sec01_full.pdf.

133. Мартынов И.А., Ватутин Э.И., Титов В.С. Устройство для умножения матриц // Патент РФ на полезную модель № 157948. Заявл. 08.07.2015, опубл. 20.12.2015. Бюл. № 35.

134. Болгак А.В. Оценка временных затрат на умножение квадратных бинарных матриц устройства с конвейеризацией чтения данных из специализированной многопортовой памяти / А.В. Болгак, Э.И. Ватутин, Д.А. Трокоз // Известия ЮФУ. Технические науки. - 2025. № 4(246). - С. 6-20. - DOI 10.18522/2311-3103-2025-4-6-20.

135. Гвоздева С.Н. Оценка аппаратной сложности устройства умножения квадратных бинарных матриц размером n n х / Гвоздева С.Н.,

Ватутин Э.И. // Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений (Распознавание - 2019): сборник материалов XV международной научно-технической конференции / ред. кол.: С.Г. Емельянов [и др.]; Юго-Зап. гос. ун-т. Курск, 2019. С. 66-68.

136. Болгак А.В. Оценка аппаратной сложности устройства для умножения квадратных бинарных матриц с конвейеризацией операции чтения данных из специализированной многопортовой памяти / А.В. Болгак, Э.И. Ватутин // Труды МАИ. - 2025. - № 143. - URL: https://trudymai.ru/published.php?ID=185649. - EDN: DMRNDE.

ПРИЛОЖЕНИЕ

Приложение 1

Временные затраты алгоритма Флойда-Уоршелла и известных программных реализаций для умножения квадратных бинарных матриц в зависимости от размера матриц и их плотности в задаче поиска транзитивного замыкания бинарного отношения, обладающего свойством транзитивности (свидетельство о государственной регистрации программы для ЭВМ №2025664497. Заявл. 15.05.2025 г.; зарегистрировано 04.06.2025 г.).

Вычислительные эксперименты проводились на базе процессора 12th Gen Intel® Core™ i7-12700K 3,60 GHz, используемый компилятор - Microsoft Visual

Studio 2017.

Классическое умножение Размер матриц, n х n Время, с Плотность, %

8 0,000002236 0,1

16 0,000011732 0,1

32 0,000107558 0,1

64 0,00165274 0,1

128 0,0080923 0,1

256 0,086138 0,1

512 0,772466 0,1

1024 6,66009 0,1

2048 54,4885 0,1

Классическое умножение с прерыванием Размер матриц, n х n Время, с Плотность, %

8 0,000002316 0,1

16 0,000009492 0,1

32 0,000026712 0,1

64 0,000225936 0,1

128 0,000574814 0,1

256 0,00226305 0,1

512 0,0109204 0,1

1024 0,0582017 0,1

2048 0,206746 0,1

Буферизованное умножение Размер матриц, п х п Время, с Плотность, %

8 0,00000227 0,1

16 0,000012296 0,1

32 0,00009226 0,1

64 0,00118756 0,1

128 0,00483464 0,1

256 0,0375762 0,1

512 0,299495 0,1

1024 2,39387 0,1

2048 20,169 0,1

Буферизованное умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,00000271 0,1

16 0,000015312 0,1

32 0,000038292 0,1

64 0,00024816 0,1

128 0,00055276 0,1

256 0,002299 0,1

512 0,00893469 0,1

1024 0,0340064 0,1

2048 0,118716 0,1

Блочное умножение Размер матриц, п х п Время, с Плотность, %

8 0,000003332 0,1

16 0,000018678 0,1

32 0,0001551 0,1

64 0,00251532 0,1

128 0,0114797 0,1

256 0,0903341 0,1

512 0,741135 0,1

1024 5,98102 0,1

2048 30,1325 0,1

Блочное умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000003202 0,1

16 0,00001885 0,1

32 0,000145498 0,1

64 0,00220158 0,1

128 0,0109657 0,1

256 0,0909152 0,1

512 0,738499 0,1

1024 6,04028 0,1

2048 3,43135 0,1

Алгоритм Флойда-Уоршелла Размер матриц, п х п Время, с Плотность, %

8 0,000006002 0,1

16 0,000036606 0,1

32 0,000226016 0,1

64 0,00149741 0,1

128 0,0101829 0,1

256 0,0729454 0,1

512 0,551778 0,1

1024 4,30086 0,1

2048 34,1813 0,1

Классическое умножение Размер матриц, п х п Время, с Плотность, %

8 0,000001746 0,5

16 0,000016 0,5

32 0,00012485 0,5

64 0,00104354 0,5

128 0,0243739 0,5

256 0,215091 0,5

512 1,9008 0,5

1024 16,0154 0,5

2048 129,348 0,5

Классическое умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000000566 0,5

16 0,000002394 0,5

32 0,000021438 0,5

64 0,000040952 0,5

128 0,000157398 0,5

256 0,000670412 0,5

512 0,00265607 0,5

1024 0,0101951 0,5

2048 0,0414399 0,5

Буферизованное умножение Размер матриц, п х п Время, с Плотность, %

8 0,000002158 0,5

16 0,000013578 0,5

32 0,000096324 0,5

64 0,00065944 0,5

128 0,0062689 0,5

256 0,0481695 0,5

512 0,385606 0,5

1024 3,13956 0,5

2048 26,0251 0,5

Буферизованное умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000000796 0,5

16 0,00000278 0,5

32 0,000011008 0,5

64 0,000034078 0,5

128 0,000126376 0,5

256 0,00050945 0,5

512 0,00217323 0,5

1024 0,00823223 0,5

2048 0,0337148 0,5

Блочное умножение Размер матриц, п х п Время, с Плотность, %

8 0,000001648 0,5

16 0,000004596 0,5

32 0,000034484 0,5

64 0,000232892 0,5

128 0,00130996 0,5

256 0,0139894 0,5

512 0,0807403 0,5

1024 0,635944 0,5

2048 5,07637 0,5

Блочное умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000002038 0,5

16 0,00000446 0,5

32 0,000037184 0,5

64 0,000283094 0,5

128 0,000259242 0,5

256 0,00172049 0,5

512 0,0139683 0,5

1024 0,100832 0,5

2048 0,813822 0,5

Алгоритм Флойда-Уоршелла Размер матриц, п х п Время, с Плотность, %

8 0,000005952 0,5

16 0,000031182 0,5

32 0,000181616 0,5

64 0,00118346 0,5

128 0,00885361 0,5

256 0,0688162 0,5

512 0,530162 0,5

1024 4,17844 0,5

2048 33,0205 0,5

Классическое умножение Размер матриц, п х п Время, с Плотность, %

8 0,000001924 0,9

16 0,000013962 0,9

32 0,000112 0,9

64 0,00096999 0,9

128 0,00874422 0,9

256 0,0845335 0,9

512 0,76054 0,9

1024 6,61102 0,9

2048 53,4949 0,9

Классическое умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000000404 0,9

16 0,000001832 0,9

32 0,000006738 0,9

64 0,000023702 0,9

128 0,000094416 0,9

256 0,00036501 0,9

512 0,00145907 0,9

1024 0,00585599 0,9

2048 0,0249808 0,9

Буферизованное умножение Размер матриц, п х п Время, с Плотность, %

8 0,000001802 0,9

16 0,000012722 0,9

32 0,000089548 0,9

64 0,000641778 0,9

128 0,00503133 0,9

256 0,039757 0,9

512 0,33926 0,9

1024 2,58486 0,9

2048 21,0637 0,9

Буферизованное умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000000386 0,9

16 0,000001898 0,9

32 0,000006462 0,9

64 0,000025812 0,9

128 0,000093942 0,9

256 0,000373968 0,9

512 0,00166596 0,9

1024 0,00681206 0,9

2048 0,0265929 0,9

Блочное умножение Размер матриц, п х п Время, с Плотность, %

8 0,000002922 0,9

16 0,000019674 0,9

32 0,000159986 0,9

64 0,000761468 0,9

128 0,00810598 0,9

256 0,0579558 0,9

512 0,564335 0,9

1024 4,70528 0,9

2048 38,0324 0,9

Блочное умножение с прерыванием Размер матриц, п х п Время, с Плотность, %

8 0,000002254 0,9

16 0,000015074 0,9

32 0,000120758 0,9

64 0,000067084 0,9

128 0,000298976 0,9

256 0,00177606 0,9

512 0,00663807 0,9

1024 0,05261 0,9

2048 0,387962 0,9

Размер матриц, п х п Время, с Плотность, %

8 0,000002732 0,9

16 0,00001587 0,9

Алгоритм Флойда-Уоршелла 32 0,000133382 0,9

64 0,00103043 0,9

128 0,00816924 0,9

256 0,0657347 0,9

512 0,517888 0,9

1024 4,13344 0,9

2048 32,8864 0,9

Приложение 2

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

бинарных матриц на базе параллельно-конвейерной памяти.

Итерационное устройство умножения матриц (патент на изобретение № 2744239) Размер матриц, п х п Время, с

8 0,0000039

16 0,0000243

32 0,000175

64 0,001314

128 0,010073

256 0,0814

512 0,6563

1024 4,895