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

• Гвоздева Светлана Николаевна
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Гвоздева Светлана Николаевна

ВВЕДЕНИЕ

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

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

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

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

1.4 Задачи на графах, требующие определения состава бинарных отношений

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

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

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

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

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

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

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

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

2.4 Алгоритмы построения транзитивного замыкания построения бинарных отношений

2.5 Аппаратно-ориентированный алгоритм определения состава бинарных

отношений

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

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

3.1 Матричное запоминающее устройство для хранения битовых признаков

отношения следования

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

3.2.1 Этап загрузки исходных данных в запоминающее устройство

3.2.2 Этап инициализации

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

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

базе систолических структур

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

3.3.1 Начало работы

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

3.3.3 Этап работы устройства обработки бинарных матриц на базе аппаратной

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

3.3.3.1 Чтение информации из блока коэффициентов матрицы

3.3.4 Этап умножения 1-й строки на ]-й столбец устройства обработки бинарных матриц на базе аппаратной реализации алгоритмов классического умножения матриц

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

классического умножения матриц

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

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ

Приложение

Приложение

Приложение

Приложение

Приложение

Приложение

Приложение

Приложение

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

Введение

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

Построение разбиений при ограниченных временных затратах на их получение приводит к необходимости переноса вычислительно сложных процедур, одной из которых является определение состава бинарных отношений вершин (в том числе - отношения параллельности) заданной граф-схемы алгоритма управления, с программного уровня на аппаратный путем разработки специализированных устройств-акселераторов, адаптированных к особенностям решаемой задачи. Одной из наиболее трудоемких операций при определении состава бинарных отношений вершин является задача транзитивного замыкания бинарного отношения следования, которая допускает сведение к задаче умножения бинарных матриц. Существующие устройства для умножения матриц и решения схожих задач на графах (С. Кун, В.М. Курейчик, Н.А. Лиходед, P. Dighe и др.)

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

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

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

Работа выполнена при поддержке гранта Президента РФ для поддержки молодых ученых - кандидатов наук «Разработка эвристических методов, алгоритмов и аппаратно-программных средств с параллельной архитектурой для решения задач дискретной комбинаторной оптимизации при проектировании однородных многомодульных мультисистем» (МК-9445.2016.8, 2016-2017 гг.) и гранта РФФИ «Разработка и анализ эффективности эвристических итерационных методов при проектировании логических мультиконтроллеров с использованием грид-систем на добровольной основе» (РФФИ 17-07-00317-а, 2017-2019 гг.).

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

В соответствии с целью работы сформулированы следующие основные задачи:

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

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

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

4. Оценка аппаратной сложности разработанного устройства обработки бинарных матриц.

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

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

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

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

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

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

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

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

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

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

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

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

Соответствие паспорту специальности. Согласно паспорту специальности 05.13.05 - Элементы и устройства вычислительной техники и систем управления, научная проблема, рассмотренная в диссертационной работе, соответствует пунктам 1 и 2 паспорта специальности:

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

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

ориентированного алгоритма, устройства обработки бинарных матриц, обеспечивающего снижение аппаратной сложности.

Апробация результатов исследования. Основные положения диссертационной работы докладывались и получили положительную оценку на всероссийских и международных конференциях: XV Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов и обработки изображений» (г. Курск, 2019 г.); Всероссийской научно - технической конференции «Интеллектуальные и информационные системы» (г. Тула, 2019 г.); XXIII Международной научно-технической конференции «Медико-экологические информационные технологии -2020» (г. Курск, 2020); на научно-технических семинарах, проводимых кафедрой «Вычислительная техника» Юго-Западного государственного университета в течение 2016-2020 гг.

Личный вклад автора. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных работах предложены: в [160, 152, 156] разработано устройство для умножения бинарных матриц, приведены результаты оценки быстродействия и аппаратная сложности; в [181] представлено описание математической модели определения состава бинарных отношений и алгоритма умножения бинарных матриц; в [162,163] приведено описание особенностей использования метода взвешенного случайного перебора в задаче поиска субоптимальных разбиений граф-схем параллельных алгоритмов, программной реализации жадного метода в задаче поиска хроматического числа графа; в [164,167] представлены результаты изучения и анализа эффективности эвристических итерационных методов на базе модификации существующих решений в тестовой задаче поиска кратчайшего пути в графе с целью оценки потенциала их использования при построении разбиений; в [165] реализована программа, предназначенная для построения разбиений граф-схем параллельных алгоритмов логического управления методом взвешенного случайного перебора, в [166] - программа для умножения плотных вещественных матриц на GPU с поддержкой технологии OpenCL; в [153, 157] создано устройство для возведения

бинарной матрицы в квадрат и приведена оценка его аппаратной сложности; в [168] представлена схемотехническая реализация операции булева умножения двух квадратных бинарных матриц на базе схемы умножения i-й строки на j-й столбец матрицы; в [169] представлены результаты вычислительного эксперимента по выбору начального цвета первой вершины эвристических методов случайного перебора в задаче поиска квазиоптимальной раскраски неориентированного графа при построении разбиений.

Публикации. Результаты проведенных диссертационных исследований опубликованы в 14 научных трудах, из них пять статей (3 опубликованы в центральных рецензируемых научных журналах и изданиях по перечню ВАК при Минобрнауки России, 1 опубликована в журнале, индексируемом в Scopus). Получено 2 патента РФ (на полезную модель № 193927, от 21 ноября 2019 г.; на изобретение №2744239, от 04.03.2021) и 2 свидетельства о государственной регистрации программы для ЭВМ (№ 2019613452 от 18 марта 2019 г.; № 2019611362 от 01 февраля 2018 г.).

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 181 наименование, изложена на 131 странице.

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

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

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

Для описания класса параллельных алгоритмов логического управления необходимо построить их формализованное представление. На основании работ [1 -4], для построения используется язык графических схем. Он сохраняет свойство наглядности при построения графического изображения алгоритма управления вместе с формализацией его представления в виде графа. При использовании языка граф схем алгоритм представляет собой конечный связный ориентированный граф

С = (Д V), в котором вершины данного графа а1 <Е А, / = 1,Л/ соответствуют операторам, а дуги ук — апа] еУ, УСАхЛ, к = 1,М, /,./' = задают порядок

следования вершин (операторов), где N = |А| - число вершин графа, М = |у| - число дуг [5].

На данный момент, существует два основных типа вершин, включенных в граф-схему алгоритма: (рисунок 1.1):

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

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

Рисунок 1.1 - Типы вершин параллельных алгоритмов логического управления. Рассмотрим более подробно каждую из вершин:

операторная вершина (рис.1.а) - записывается один или несколько операторов алгоритма, в ее составе содержится множество микроопераций

У а, = у^, х-2Угт , У V 7 = 1, Г, Г =

У а;

- условная вершина (рис.1.б) - помещает идентификаторы проверяемых логических условий, в ее составе - множество логических условий

X О,- = X; ,Х; , X; (Е X г, , 7 = 1, Б , Б = X О,-

I J 1-1 J J I ^ J I j и' ' ' I

- начальная вершина (рис.1.в) - имеет только одну выходящую дугу (а

нач

конечная вершина (рис. 1.г) - имеет только одну входящую дугу (а ); вершина распараллеливания/синхронизации (рис.1.д) - имеет две и более исходящих и одну входящую дугу, а вершина синхронизации - одну исходящую и две и более входящих;

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

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

Описание параллельных алгоритмов широкого класса происходит на основании предложенного язык параллельных граф-схем алгоритмов (ПарГСА) [57].

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

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

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

Взвешенный неориентированный граф 0 является адекватной и естественной моделью распределения задач по процессорам кластера. Граф 0 задан множеством рёбер и: 0(У, Е) и множеством вершин У. Причем, каждая вершина этого графа представляет собой одну из задач, а вес этой вершины представляет собой число операций, которые выполняются при решении этой задачи. Коммуникационные затраты на обмен данными между задачами моделирует вес ребер соответствующих вершин.С помощью этой модели возможно разбиение множества вершин графа У на непересекающиеся подмножества, которое, в свое время, производит разбиение графа 0(У,Е) на непересекающиеся подграфы. При этом каждый подграф возможно ассоциировать с некоторым процессором, который будет использоваться для решения всех задач, соответствующих вершинам этого подграфа. Таким образом, оптимальное распределение вычислительной нагрузки между доступными процессорами сводится к оптимальному разделению графа 0(У, Е).

Задача оптимального разделения графа является № - сложной и не допускает получение оптимального решения за приемлемое время для управляющих

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

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

Существует два вида ограничений:

1. Технологическое - каждому блоку разбиения соответствует отдельный контроллер в составе СЛУ. На основании этого, блоки должны удовлетворять ограничениям аппаратного обеспечения.

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

Снижение аппаратной сложности происходит из-за минимизации числа контроллеров в составе СЛУ, что достигается путем минимизации числа блоков разбиений.

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

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

Существующие методы и алгоритмы поиска построения разбиений можно разделить на два класса, представленные в таблице 1.1 [9-41].

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

Методы По след о е д те ль н ые Итерационные

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

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

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

Не зависимо от выбора метода построения разбиений необходимо обязательное присутствие проверки бинарных отношений. Это необходимо для гарантии отсутствия параллельных вершин в составе блоков разбиения. Также возникает необходимость определение состава и других отношений. Для этого необходимо построение матрицы отношений Мк. Существенное время от общего времени построения разбиений занимает заполнение матрицы отношения. Это показывает важность данной структуры данных в контексте рассматриваемой задачи.

1.4 Задачи на графах, требующие определения состава бинарных отношений

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

В ряде задач необходимо удостовериться, является ли неориентированный граф С = [А,У), заданный матрицей смежности, связным [42^-4]. При этом

необходимо ввести понятие бинарного отношения связности вершин а., а. ,

/, / = 1,\А\, I ^ ] которое может быть применено на все возможные пары вершин и

обладает свойством транзитивности. Алгоритм проверки связности строится на следующих подходах:

- на построении ^-кратных отображений начиная с некоторой опорной вершины;

- на волновом подходе (поиск в ширину) [45, 46].

На данный момент известны его аппаратные реализации, которые представлены в работах [47-52].

В некоторых задачах, помимо определения связности, необходимо определить число и/или состав компонента связности [53]. С этой целью можно применять ранее обсуждавшиеся подходы. Их аппаратные решения отражены в работах [54-

В ориентированных графах известна задача проверки достижимости вершины а. из вершины а{. Под достижимостью будем понимать присутствие пути

, aj

между указанной парой вершин, в которых не присутствуют

запрещенные (отсутствующие) дуги. Данный путь может быть построен следующими алгоритмами, которые выбираются в зависимости от спицифики поставленной задачи: использованием алгоритмов Дейкстры [62], Беллмана-Форда [63, 64], Флойда-Уоршалла [65, 66], поисковыми алгоритмами (поиск в глубину или в ширину).

Проверка контрдостижимости основана на требовании взаимной достижимости пары вершин aj и at. Данная проверка позволяет произвести

разбиение графа на компоненты сильной связности и применяется в ориентированных графах [67, 68]. Примером использования контрдостижимости можно считать выделение циклических фрагментов в графических схемах параллельных алгоритмов [69, 170]. Решение данной задачи возможно как при помощи специализированного алгоритма, например алгоритма Косарайю-Габова-Тарьяна [70], так и при помощи алгоритмов, указанных выше.

Существуют также задачи, которые изначально не являются графовыми, но могут сводиться к ним. При планировании запуска подпрограмм в соответствии с графами зависимостей по данным и по управлению, так и при крупноблочном распараллеливании программ необходимы: учет связности и параллельности подпрограмм и объем передаваемых данных [71]. При проектировании центральных систем важной задачей является обеспечение отказоустойчивости, при условии сохранения умеренного роста аппаратной сложности, балансировки нагрузки и приемлемого быстродействия [72].

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

Внедрение программного обеспечения операции матричного умножения, которые ориентированы на широкораспространенные CPU семейства x86,

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

Первая из них это «наивная» универсальная программная реализация, используемая обычно в процессе изучения (обучения) основам программирования. Дня нее характерны следующие преимущества:

- за счет разницы в тактовых частотах и микроархитектурных улучшений ядра (при сравнении Haswell и Allendale) производительность обработки процессоров отличается приблизительно в три раза;

- существенно лимитирует реальную производительность скорость поступления исходных данных;

- при этом используется неэффективно для матриц большой размерности.

Реализация выполнения данной программной реализации выглядит

Список литературы диссертационного исследования кандидат наук Гвоздева Светлана Николаевна, 2021 год

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

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, J.N. Abdel-Jalil, M.H. Najajra, I.V. Zotov. Comparison of Methods for Getting Separation of Parallel Logic Control Algorithms // Information and Telecommunication Technologies in Intelligent Systems (ITT IS'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. Ватутин Э.И., Волобуев С.В., Зотов И.В. Комплексный сравнительный анализ качества разбиений при синтезе логических мультиконтроллеров в условиях присутствия технологических ограничений // Труды четвертой международной конференции «Параллельные вычисления и задачи управления» РАС0'08. М.: Институт проблем управления им. В.А. Трапезникова РАН, 2008. С. 643-685.

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

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

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

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

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

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

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., Valyaev S.Yu., Titov V.S. Comparison of Sequential Methods for Getting Separations of Parallel Logic Control Algorithms Using Volunteer Computing // BOINC:FAST, 2015. Accepted for publication

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

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

35. Ватутин Э.И., Дремов Е.Н., Мартынов И.А., Титов В.С. Метод взвешенного случайного перебора для решения задач дискретной

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

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

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

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

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

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

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

42. https: //ru.wikipedia. о^/шМ/Связный_граф

43. https://ru.wikipedia.org/wiki/Связность_графов

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

45. https: //ru.wikipedia. о^/шМ/Алгоритм_Ли

46. https: //ru.wikipedia. о^/шкШоиск_в_ширину

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. https://ru.wikipedia.org/wiki/Компонента_связности_графа

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.

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. https://ru.wikipedia.org/wiki/Компонента_сильной_связности_в_ор

графе

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

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

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

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

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

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

74. Мартынов И.А. Метод, аппаратно-ориентированные алгоритмы и устройство классификации бинарных отношений вершин граф-схем параллельных алгоритмов // Диссертация на соискание ученой степени кандидата технических наук, 2016 год.

75. Intel 64 and IA-32 Architectures Software Developer's Manual. Volume 1: Basic Architecture. Order number 253665-021

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

77. https://ru.wikipedia.org/wiki/BOINC

78. Ватутин Э.И. Добровольный метакомпьютинг: современное состояние и перспективы развития // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и

символьной информации (Распознавание - 2010). Курск: изд-во КурскГТУ, 2010. С. 164-166

79. https ://ru.wikipedia.org/wiki/GPGPU

80. https://ru.wikipedia.org/wiki/Intel_MIC

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

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

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

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

85. Thoma F., Kuhnle M., Bonnot P., Panainte E.M., Bertels K., Goller S., Schneider A., Guyetant S., Schuler E., Müller-Glaser K.D., Becker J. MORPHEUS: Heterogeneous Reconfigurable Computing // Field Programmable Logic and Applications, 2007. FPL 2007. P. 409-414. DOI: 10.1109/FPL.2007.4380681

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

87. Параллельные методы матричного умножения // http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=1

88. Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц

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

89. Блочное умножение матриц // https://ru.wikipedia.org/wiki/Блочная_матрица#.D0.91.D0.BB.D0.BE.D1.87.D0. BD.D0.BE.D0.B5_.D1.83.D0.BC.D0.BD.D0.BE.D0.B6.D0.B5.D0.BD.D0.B8.D0. B5_.D0.BC.D0.B0.D1.82.D1.80.D0.B8.D1.86

90. Lynn Elliot Cannon. A cellular computer to implement the Kalman Filter Algorithm // Technical report. Ph.D. Thesis. Montana State University. 14 July 1969

91. Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной производительности современных процессоров и видеокарт с поддержкой технологии CUDA в задаче умножения матриц // CUDA альманах (май 2015). 2015. С. 9-10. http://www.nvidia.ru/docs/Ю/141194/CШA-альманах-may-2015.pdf

92. Ватутин Э.И., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации с использованием расширения SSE (часть 1) // Известия Юго-Западного государственного университета. Принята к опубликованию

93. Ватутин Э.И., Титов В.С. Оценка реальной производительности современных процессоров в задаче умножения матриц для однопоточной программной реализации с использованием расширения SSE (часть 2) // Известия Юго-Западного государственного университета. Принята к опубликованию

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

95. А. с. СССР № 588548, кл. G 06 G 9/00, 1976. Оптическое устройство для умножения матриц / Михляев С.В., Твердохлеб П.Е., Чугуй Ю.В. Заявл. 08.07.1976. Опубл. 15.01.1978

96. А. с. СССР 1427394 МПК G06G9/00. Оптическое устройство для вычисления произведения трех матриц / Михляев С.В., Твердохлеб П.Е. Заявл. 20.03.1987. Опубл. 30.09.1988

97. Патент РФ 2022334 МПК G06F 1/04, G06F 15/347. Устройство для перемножения числовых матриц / Красиленко В.Г., Заболотная Н.И. Заявл. 21.10.1991. Опубл. 30.10.1994

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

99. Патент РФ 2018916, МПК G06E 1/04, G06F 15/347. Устройство для умножения матриц картин-изображений / Красиленко В.Г., Заболотная Н.И., Евтихиев Н.Н. Заявл. 04.06.1991. Опубл. 30.08.1994

100. А. с. СССР 264797 МПК G06G7/16. Устройство для перемножения алгебраических матриц / Н.И. Денисенко, А.А. Лор. Опубл. 01.01.1970

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

102. А. с. СССР 1056192 МПК G06F7/70. Вероятностное устройство для умножения матриц / Яковлев В.В., Мальченкова О.С., Яковлев А.В. Заявл. 28.07.1982. Опубл. 23.11.1983

103. А. с. СССР 1345211 МПК G06F17/16. Устройство для операций над матрицами / Якуш В.П., Мищенко В.А., Соболевский П.И., Авгуль Л.Б., Лазаревич Э.Г. Заявл. 15.04.1986. Опубл. 15.10.1987

104. А. с. СССР 1418749 МПК G06F17/16. Устройство для умножения матриц / Обод И.И. Заявл. 23.01.1987. Опубл. 23.08.1988

105. А. с. СССР 1444819 МПК 006Р17/16. Устройство поклеточного умножения матриц / Вышинский В.А., Рабинович З.Л., Тихонов Б.М., Фесенко Н.Б. Заявл. 22.12.1986. Опубл. 15.12.1988

106. А. с. СССР 1471201 МПК 006И7/16. Устройство для умножения матриц / Грищенков В.А., Калалб А.Д., Царев А.П. Заявл. 19.08.1987. Опубл. 07.04.1989

107. А. с. СССР 1807499 G06F15/347. Устройство для умножения матриц / Аванесян Г.Р., Антоненков В.Б., Айдаров Г.А. Заявл. 13.03.1991. Опубл. 07.04.1993

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

109. А. с. СССР 1226484 МПК 006И7/16. Устройство умножения матрицы на вектор / Выжиковска А.В., Выжиковски Р., Каневский Ю.С., Лозинский В.И.. Заявл. 23.10.1984. Опубл. 23.04.1986

110. А. с. СССР 1236500 МПК в06Р17/16. Однородная параллельная вычислительная структура для вычисления произведения матрицы на вектор / Гуляев В.А., Стасюк А.И., Чаплыга В.М., Спиченков Ю.Н. Заявл. 30.11.1984. Опубл. 07.06.1986

111. А. с. СССР 1388897 МПК G06F17/16. Устройство для выполнения матричных операций / Якуш В.П., Седухин С.Г., Мищенко В.А., Авгуль Л.Б., Подрубный О.В. Заявл. 15.10.1986. Опубл. 15.04.1988

112. А. с. СССР 1429127 МПК 006И7/16. Устройство для матричных операций / Якуш В.П., Седухин С.Г., Авгуль Л.Б., Ленев А.А. Заявл. 04.03.1987. Опубл. 07.10.1988

113. А. с. СССР 1534471 МПК G06F17/16. Устройство для умножения ленточной матрицы на полную матрицу / Кричмара А.А., Сердцев А.А., Романовский П.Г. Заявл. 15.01.1988. Опубл. 07.01.1990

114. А. с. СССР 1552200 МПК G06F 17/16. Устройство для перемножения матриц / Якуш В.П., Седухин С.Г., Соболевский П.И., Лиходед Н.А. Заявл. 29.07.1988. Опубл. 23.03.1990

115. . с. СССР 1619304 МПК G06F15/347. Устройство для умножения матриц / Якуш В.П., Косьянчук В.В., Соболевский П.И., Лиходед Н.А. Заявл. 06.02.1989. Опубл. 07.01.1991

116. А. с. СССР 1619305 МПК G06F15/347. Устройство для умножения матриц / Якуш В.П., Косьянчук В.В., Соболевский П.И., Лиходед Н.А. Заявл. 06.02.1989. Опубл. 07.01.1991

117. А. с. СССР 1677709 МПК G06F17/16. Устройство для умножения матриц / Якуш В.П., Косьянчук В.В., Соболевский П.И., Лиходед Н.А. Заявл.

10.05.1989. Опубл. 15.09.1991

118. А. с. СССР 1705836 МПК G06F15/347. Устройство для перемножения матриц / Выжиковски Р., Каневский Ю.С., Клименко М.К., Овраменко С.Г. Заявл. 17.10.1989. Опубл. 15.01.1992

119. А. с. СССР 1774347 МПК G06F15/347. Устройство для умножения матриц / Якуш В.П., Лиходед Н.А., Косьянчук В.В., Соболевский П.И. Заявл. 28.04.1990. Опубл. 07.11.1992

120. А. с. СССР 1779180 МПК G06F17/16. Устройство для умножения матриц / Якуш В.П., Лиходед Н.А., Косьянчук В.В., Тиунчик А.А. Заявл.

30.07.1990. Опубл. 27.05.1995

121. А. с. СССР 1793446 МПК G06F15/347. Устройство для умножения матриц / Якуш В.П., Косьянчук В.В., Лиходед Н.А., Соболевский П.И. Заявл. 28.04.1990. Опубл. 07.02.1993

122. А. с. СССР 1801224 G06F15/347. Устройство для умножения матриц / Выжиковски Р., Каневский Ю.С., Клименко М.К., Овраменко С.Г., Юн Сен Чер. Заявл. 05.03.1991. Опубл. 07.03.1993

123. Патент РФ 2006937 G06F 15/347. Устройство для перемножения матриц / Выжиковски Р., Каневский Ю.С., Клименко М.К., Овраменко С.Г. Заявл. 19.10.1990. Опубл. 30.01.1994

124. Патент РФ 2011221 МПК G06F 15/347. Устройство для умножения матриц / Якуш В.П., Лиходед Н.А., Соболевский П.И., Косьянчук В.В. Заявл. 03.07.1991. Опубл. 15.04.1994

125. Патент США № 4922418. Method for controlling propogation of data and transform through memory-linked wavefront array processor / Quentin E. Dolecek. Заявл. 15.01.1988. Опубл. 01.05.1990

126. Патент США № 4493048. Systolic array apparatuses for matrix computations / Hsiang-Tsung Kung, Charles E. Leiserson. Заявл. 16.05.1983. Опубл. 08.01.1985

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

128. А.с. СССР № 1363247 МПК G06F 17/16. Устройство для перемножения матриц / Якуш В.П., Седухин С.Г., Козюминский В.Д., Авгуль Л.Б. Заявл. 25.07.1986. Опубл. 30.12.1987

129. А.с. СССР № 1649126 МПК G06F 15/347. Устройство для умножения матриц / Лозбенев В.Ю., Шилов А.К., Горбунов С.П., Ушаков Е.Г. Заявл. 16.05.1989, опубл. 15.05.1991

130. Орлов С., Цилькер Б. Организация ЭВМ и систем. СПб.: Питер, 2011. 688 с

131. http: //ru.wikipedia.org/wiki/Отношение_(математика)

132. http://ru.wikipedia.org/wiki/Бинарное_отношение

133. http://ru.wikipedia.org/wiki/Рефлексивное_отношение

134. http://ru.wikipedia.org/wiki/Симметричное_отношение

135. http://ru.wikipedia.org/wiki/Транзитивное_отношение

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

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

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

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

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

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

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

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

208 с.

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

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

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

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

148. Ватутин Э.И. Объединение линейных участков в задаче нахождения субоптимальных разбиений параллельных управляющих алгоритмов // Молодежь и XXI век: тезисы докладов XXXII вузовской научно-технической конференции студентов и аспирантов в области научных исследований. Курск: изд-во КурскГТУ, 2004. Ч. 1. С. 22-23.

149. http : //m.wikipedia.org/wiki/Замыкание_отношения

150. Intel Pentium 4 and Intel Xeon Processor Optimization Reference Manual. Order number 248966-05.

151. Software Optimization Guide for AMD Athlon 64 and AMD Opteron Processors. Publication number 25112.

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

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

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

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

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

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

158. Martynov I.A., Vatutin E.I., Titov V.S. Hardware oriented classification of binary relations of graph-schemes of parallel algorithms // Eighth

World Conference on Intelligent Systems for Industrial Automation (WCIS -2014). Tashkent, 2014. p. 70-73.

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

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

161. Закревский А. Д. О корректности параллельных алгоритмов логического управления // Известия АН СССР. Техническая кибернетика. — 1987. — № 4. — С. 106—112.

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

163. Гвоздева С.Н. О влиянии порядка рассмотрения вершин при поиске раскрасок графов общего вида с использованием жадного алгоритма / Пшеничных А.О., Ватутин Э.И., Гвоздева С.Н. // Высокопроизводительные вычислительные системы и технологии. Т. 3., № 1, 2019. С. 101-106.

164. Vatutin E., Panishchev V., Gvozdeva S., Titov V. Comparison of Decisions Quality of Heuristic Methods Based on Modifying Operations in the Graph Shortest Path Problem // Problems of Information Technology. No. 1. 2020. pp. 3-15. DOI: 10.25045/jpit.v11.i1.01.

165. Гвоздева С.Н. Программа для построения разбиений граф-схем параллельных алгоритмов логического управления методом взвешенного случайного перебора / Ватутин Э.И., Панищев В.С., Гвоздева С.Н. // Свидетельство об официальной регистрации программы для ЭВМ

№2018611362 Российская Федерация, заявл. 04.12.2017; зарегистрировано 01.02.2018.

166. Гвоздева С.Н. Программа для умножения плотных вещественных матриц на GPU с поддержкой технологии OpenCL / Ватутин Э.И., Затолокин Ю.А., Гвоздева С.Н., Титов В.С. // Свидетельство об официальной регистрации программы для ЭВМ №2019613452 Российская Федерация, заявл. 28.02.2019; зарегистрировано 18.03.2019.

167. Gvozdeva S.N. Comparison of Decisions Quality of Heuristic Methods Based on Modifying Operations in the Graph Shortest Path Problem / Vatutin E.I., Panishchev V.S., Titov V.S., Gvozdeva S.N. // IX International Conference on Optimization Methods and Applications "Optimization and Applications (0PTIMA-2018)", Book of Abstracts. Moscow, Petrovac, 2018. P. 171.

168. Гвоздева С.Н. Последовательное устройство для умножения бинарных матриц / Гвоздева С.Н., Мартынов И.А., Ватутин Э.И. // Интеллектуальные и информационные системы. Труды Всероссийской научно-технической конференции. Тула: Изд-во ТулГУ, 2019, 422 с. - C. 3743.

169. Гвоздева С.Н. О влиянии вероятности выбора минимально допустимого или случайного цвета для метода случайного перебора эвристической оценки хроматического числа графа / Пшеничных А.О., Гвоздева С.Н., Панищев В.С., Ватутин Э.И. // Интеллектуальные и информационные системы. Труды Всероссийской научно-технической конференции. Тула: Изд-во ТулГУ, 2019. С. 59-63

170. Ватутин Э.И., Зотов И.В. Идентификация и разрыв последовательных циклов в задаче субоптимального разбиения параллельных управляющих алгоритмов // Известия ТулГУ. Серия: Вычислительная техника. Информационные технологии. Системы управления. Т. 1. Вып. 3. Вычислительная техника. Тула: изд-во ТулГУ, 2004. С. 51-55.

171. Ватутин Э.И., Титов В.С., Емельянов С.Г. Основы дискретной комбинаторной оптимизации. М.: АРГАМАК-МЕДИА, 2016. 270 с.

172. Штейнберг Б.Я. БЛОЧНО-РЕКУРСИВНОЕ ПАРАЛЛЕЛЬНОЕ ПЕРЕМНОЖЕНИЕ МАТРИЦ // Известия высших учебных заведений. Приборостроение. 2009. Т. 52. № 10. С. 33-41.

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

174. Bini D., Capovani M., Lotti G., Romani F. — O(nA{2.7799|) complexity for approximate matrix multiplication. — Inform. Process. Lett., 1979

175. Schonhage A. Partial and total matrix multiplication. — SIAM J. Comput., 1981

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

177. Strassen V. Gaussian Elimination is not Optimal // Numer. Math / Springer-Verlag, 1969. — Vol. 13, Iss. 4. — P. 354—356. doi:10.1007/BF02165411

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

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

180. Наджаджра М.Х., Мартынов И.А., Ватутин Э.И. Схемотехническая реализация операции умножения битовых векторов при

классификации бинарных отношений граф-схем параллельных алгоритмов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации (Распознавание - 2015). Курск, 2015. С. 275-277.

181. Гвоздева С.Н. Математическая модель определения состава бинарных отношений и алгоритм умножения бинарных матриц / Гвоздева С.Н. // Известия ЮЗГУ. 2021. № 2 (75). С. 81-98.

Приложение 1.

Графики зависимости (3 от плотности матриц {й) при разных значениях п График зависимости (3 от плотности матриц {й) при п = 4

1

0,95 0,9 0,85 0,8 0,75 0,7 0,65 0,6 0,55 0,5 0,45 0,4 0,35 0,3 0,25 0,2 0,15 0,1 0,05

□ " ■ ■ □□ пи

ши * ..Л_______■

В 13 вш в □□ с

□ а .я. Я шс в р

0,1

0,2

0,3

0,4

0,5 ё

0,6 0,7 0,8

График зависимости |3 от плотности матриц (с1) при п = 8

0.9

:>г Ы Г ■

в В

□ ч □ Чр □

■: ■ * • ■■ ■ ■ ■ ■ ■■ *: ■■

■

в ■ □ у___ ■

■■ > „V ......V..... ................

. • •• . » " □ 1010 □

. ■■■ ... * ■

■ ■ .. А ... □

Лл А ■. Л- ...■ V □

■■ . : ■ ■

0,95 0,9 0,85 0,8 0,75 0,7 0,65 0,6 0,55 0,5 0,45 0,4 0,35 0,3 0,25 0,2 0,15 0,1 0,05

0,1

0,2

0,3

0.4

0.5

0.6

0.7

0.8

0.9

V;

■■ * ш □ □ □ 1

\

.■...-..«..... ................

■ ■

■ ■

■«. . ■ V) ъ.Л . " . _____

..........■■ 1, . ...........

ж " ■ ■ й и

■ _ 1 .■■,........................................

3,гк£по£°=п ................................

■

0,1

0,2

0,3

0,4

0,5 сI

0,6

0,7

0,8

0,9

0,1

--- --- --- -й- --- - та --- -- --- --- 13 □ □ □ а

'и Г ■ . ......................... ■■ ■ ..................

■ . " - ■ ■■■■ ■ . ! ...................... , Г "........■...... ................

. ■ -«И

п П 13 ° □ Г ВП п ■ м ■■

/5 Л.

в1

■СП

0,2

0,3

0,4

0.5

0,6

0,7

0,8

0,9

0,001

0,0009

0,0008

0,0007

0,0006

. 0,0005

0,0004

0,0003

0,0002

0,0001

'•г \

\..............................

0,1

0.2

0.3

0.4

0.5 с/

0.6

0.7

0.8

0.9

Оценка быстродействия устройства для возведения бинарной матрицы в

квадрат

1923 clocks 1825 clocks 1610 clocks 1429 clocks 1264 clocks 849 clocks = 685 clocks = 520 clocks = 438 clocks = 398 clocks = 275 clocks =

0.0019230000 mks 0.0018247600 mks O.00161OO4OO mks O.0014286OOO mks 0.0012638OOO mks 0.0008494000 mks O.0006846OOO mks O.0005198OOO mks 0.0004382000 mks O.0003982OOO mks O.000275OOOO mks

а)

б)

в)

г)

д)

N = 256

d = 0. 0 = 13271433219 clocks = 13271 .43321901

d = 0. 1 ■ 103868898 clocks = 103.8688982320 I

d = 0. 2 95936733 clocks = 95 .9367329072 ms

d = 0. 3 90648657 clocks = 90 .6486568240 ms

d = 0. 4 85360581 clocks = 85 .3605807408 ms

d = 0. 5 81394549 clocks = 81 .3945492784 ms

d = 0. 6 77428518 clocks = 77 .4285178160 ms

d = 0. 7 70818397 clocks = 70 .8183971120 ms

d = 0. 8 64208276 clocks = 64 .2082764080 ms

d = 0. 9 57598156 clocks = 57 .5981557040 ms

d = 1 . 0 50988035 clocks = 50 .9880350000 ms

OK

е)

N = 512

d = 0 .0 : 20938253926T clocks = 209382.5392670000

d = 0 .1 802593281 clocks = 802 .5932805424 DIS

d : 0 .2 760798085 clocks : 760 . 7980848432 DIS

d = 0 .3 719002889 clocks = 719 .0028891440 ms

d = 0 .4 698105394 clocks = 698 .1053936944 ms

d = 0 .5 656310198 clocks = 656 .3101979952 ms

d = 0 .G 614515002 clocks = 614 .5150022960 ms

d : 0 .7 593617507 clocks : 593 .6175068464 ms

d = 0 .8 551822311 clocks = 551 .8223111472 ms

d = G .9 489129415 clocks = 489 .1294151984 ms

d : 1 .0 405538819 clocks : 405 .5388190000 ms

OK

ё)

N = 1 .024OOOO000OOOOE+0OO3

d = 0. 0 = 3325391011843 clocks = 3325391.0118430000 ms

d = 0. 1 = 6223750280 clocks = 6223 7502797104 ms

d = 0. 2 = 5891534969 clocks = 5891 . 5349689648 ms

d = 0. 3 = 5559319658 clocks = 5559. 3196582192 ms

d = 0. 4 = 5227104347 clocks = 5227. 1043474736 ms

d = 0. 5 = 4894889037 clocks = 4894. 8890367280 ms

d = 0. 6 = 4562673726 clocks = 4562. 6737259824 ms

d = 0. 7 = 4230458415 clocks = 4230. 4584152368 ms

d = 0. 8 = 3898243104 clocks = 3898 2431044912 ms

d = 0. 9 = 3566027794 clocks = 3566 0277937456 ms

d = 0K 1. 0 = 3233812483 clocks = 3233 8124830000 ms

ж)

N = i !.0Ч800000000000Е+0003

d : 0 0 : 184746709618 clocks : 184746.7096175920 l

d : 0 1 : 49662687533 clocks = 49662 6875331888 ms

d = 0 2 : 47013982021 clocks = 47013 9820209456 ms

d = 0 3 = 4Ч365276509 clocks = 44365 2765087024 ms

d = 0 ч = 41716570996 clocks = 41716 5709964592 ms

d = 0 5 = 39067865484 clocks = 39067 8654842160 ms

d = 0 6 = 36419159972 clocks = 36419 1599719728 ms

d = 0 7 = 3377ОЧ5ЧЧ60 clocks : 33770 4544597296 ms

d : 0 8 : 31121748947 clocks : 31121 7489474864 ms

d = 0 9 : 28473043435 clocks = 28473 0434352432 ms

d = 0K 1 0 : 25824337923 clocks = 25824 3379230000 ms

з)

№ 193927

• .V. . д

« а" а. ^уаайй! к а

а в & & & &

НА ПОЛЕЗНУЮ .МОДЕЛЬ

УТВЕРЖДАЮ «Инвитро вижн»

^Маслаков Ю.Н.

/фЩ &А, 2021 г.

АКТ

о внедрении результатов диссертационных исследований Гвоздевой Светланы Николаевны

Комиссия в составе: председателя

Маслаков Ю.Н. Яценко В.М.

и членов комиссии

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

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

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

Председатель комиссии: Члены комиссии:

В.М. Яценко

Ю.Н. Маслаков

УТВЕРЖДАЮ Зам. генерального директора ООО «Ред Софт Центр» ■-_ Д.Е. Андрианов