close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
Мартынов Илья Александрович
МЕТОД, АППАРАТНО-ОРИЕНТИРОВАННЫЕ АЛГОРИТМЫ И
УСТРОЙСТВО КЛАССИФИКАЦИИ БИНАРНЫХ ОТНОШЕНИЙ ВЕРШИН
ГРАФ-СХЕМ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ
Специальность 05.13.05 – Элементы и устройства
вычислительной техники и систем управления
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Курск – 2016
Работа выполнена в Юго-Западном государственном университете на
кафедре вычислительная техника.
Научный руководитель:
Титов Виталий Семенович, доктор технических
наук, профессор, заслуженный деятель наук РФ
Официальные оппоненты:
Магергут
Валерий
Залманович,
доктор
технических наук, профессор, Белгородский
государственный технологический университет
им. В.Г.Шухова, профессор кафедры техническая
кибернетика
Института
информационных
технологий и управляющих систем
Жизняков
Аркадий
Львович,
доктор
технических наук, профессор, Муромский
институт
(филиал)
«Владимирский
государственный университет имени А.Г. и
Н.Г. Столетовых», заведующий кафедрой САПР
Ведущая организация:
федеральное
государственное
бюджетное
образовательное
учреждение
высшего
образования «Воронежский государственный
технический университет»
Защита состоится «1» апреля 2016 г. в 12 часов 00 минут на заседании
диссертационного совета Д 212.105.02 при ФГБОУ ВО «Юго-Западный
государственный университет» по адресу: 305040, г. Курск, ул. 50 лет
Октября, 94.
С диссертацией можно ознакомиться в библиотеке Юго-Западного
государственного университета и на сайте swsu.ru
Автореферат разослан «__»__________2016
Ученый секретарь
диссертационного совета
Титенко Евгений Анатольевич
2
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы исследования. Системы логического управления
(СЛУ) являются одним из распространенных классов цифровых управляющих
систем, проблемы анализа и синтеза которых на протяжении многих лет остаются
в центре внимания отечественных и зарубежных ученых (С.И. Баранов,
А.А. Баркалов, В.И. Варшавский, В.А. Горбатов, А.Д. Закревский, И.В. Зотов,
В.Г. Лазарев,
В.З. Магергут,
Е.И. Пийль,
Е.Н. Турута,
В.С. Харченко,
А.А. Шалыто, С.А. Юдицкий, T. Agerwala, S. Husson, R. Puri и др.). Современные
СЛУ, именуемые также логическими мультиконтроллерами (ЛМК), представляют
собой
параллельные
многомодульные
однородные
мультисистемы,
объединяющие тысячи параллельно работающих процессорных узлов
(контроллеров). Как правило, это многофункциональные системы, способные
оперативно перестраиваться на новый алгоритм управления путем его
декомпозиции на блоки ограниченной сложности. Подобные системы могут
выполнять комплексные управляющие алгоритмы теоретически неограниченной
сложности при условии их предварительного разбиения (декомпозиции) на блоки,
назначаемые на отдельные модули мультисистемы. При этом длительность
процессов начальной настройки, отладки или последующей перенастройки
системы, как правило, выполняемых автоматизировано, во многом определяется
временем поиска походящего разбиения, сокращение которого ведет к
повышению производительности труда и увеличению коэффициента готовности
СЛУ.
Нахождение оптимального решения задачи разбиения практически
недостижимо для алгоритмов управления реальной сложности (20 вершин и
более) ввиду необходимости перебора и сопоставления очень большого числа
различных разбиений. В связи с этим, на практике распространены эвристические
алгоритмы декомпозиции, обеспечивающие приближенное (субоптимальное)
решение задачи за полиномиальное время с использованием различных
структурных преобразований и эвристик (С.И. Баранов, А.А. Баркалов,
В.А. Горбатов, А.Д. Закревский, И.В. Зотов, В.С. Харченко, M. Dorigo, C. Gelatt,
D. Karaboga, S. Kirkpatrick, M. Vecchi и др.). В независимости от особенностей
применяемого алгоритма при построении разбиения необходим учет структурных
и технологических ограничений СЛУ, одним из которых является требование
отсутствия параллельных вершин в составе блоков разбиения. Его соблюдение, с
одной стороны, позволяет существенно упростить структуру контролера в составе
СЛУ, но, с другой стороны, приводит к необходимости классификации бинарных
отношений вершин заданного алгоритма управления перед построением
разбиения, что при программной реализации требует существенных затрат
времени и памяти ЭВМ.
Потребность в построении разбиений при ограниченных временных
затратах на их получение приводит к необходимости переноса вычислительно
сложных процедур, к которым относится классификация бинарных отношений, с
программного уровня на аппаратный путем разработки специализированных
устройств-акселераторов, жестко адаптированных к особенностям решаемой
3
задачи. Известные устройства (В.Л. Баранов, В.В. Васильев, Р. Выжиковски,
А.Г. Додонов, В.В. Епихин, В.М. Глушань, Н.И. Заболотная, В.А. Калашников,
В.В. Косьянчук, В.Г. Красиленко, А.А. Кричмара, С. Кун, В.М. Курейчик,
Н.А. Лиходед, С.В. Михляев, П.Г. Романовский, А.А. Сердцев, П.И. Соболевский,
П.Е. Твердохлеб, А.Н. Чаплиц, В.Н. Червяцов, Л.И. Щербаков, В.П. Якуш,
В.И. Ян, Q.E. Dolecek, Hsiang-Tsung Kung, K. Barman, P. Dighe, C.E. Leiserson,
R.M. Rao и др.) для умножения матриц и решения схожих задач на графах
характеризуются недостаточными функциональными возможностями или
избыточной вычислительной и аппаратной сложностью.
Таким образом, существует противоречие между необходимостью
повышения качества разбиений с целью улучшения функциональных
характеристик систем логического управления, с одной стороны, и снижения
вычислительных затрат на поиск субоптимальных разбиений, с другой. В связи с
этим актуальной научно-технической задачей является разработка метода,
алгоритмов и аппаратно-программных средств классификации бинарных
отношений вершин граф-схем параллельных алгоритмов, позволяющих
формировать разбиения при ограниченных затратах вычислительного времени на
их построение.
Работа выполнена в рамках выполнения государственного задания для
ЮЗГУ на 2014–2017 гг., номер НИР 2246 (тема 1.20.14ф), а также в рамках
научной школы НШ-2357.2014.8.
Объектом исследования являются многомодульные однородные системы
логического управления, ориентированные на реализацию комплексных
параллельных управляющих алгоритмов.
Предметом исследования являются алгоритмы и аппаратно-программные
средства классификации бинарных отношений вершин граф-схем параллельных
алгоритмов логического управления.
Целью работы является сокращение временных затрат на построение
разбиений граф-схем параллельных алгоритмов логического управления на
основе разработки метода, аппаратно-ориентированных алгоритмов и устройства
классификации бинарных отношений вершин граф-схем параллельных
алгоритмов.
Для достижения поставленной цели в работе решаются следующие
основные задачи:
1. Анализ существующих методов, алгоритмов, программных и аппаратных
реализаций классификации бинарных отношений вершин графов общего вида и
граф-схем параллельных алгоритмов.
2. Разработка
метода
и
аппаратно-ориентированных
алгоритмов
классификации бинарных отношений вершин граф-схем параллельных
алгоритмов, ориентированных на параллельную программно-аппаратную
реализацию и позволяющих перенести вычислительно сложные процедуры
классификации бинарных отношений с программного уровня на аппаратный.
4
3. Разработка структурно-функциональной организации устройстваакселератора для реализации наиболее трудоемких операций при классификации
бинарных отношений граф-схем параллельных алгоритмов.
4. Проведение вычислительных экспериментов, оценка аппаратной
сложности разработанного устройства и выигрыша во времени обработки при его
применении.
Новыми научными результатами и положениями, выносимыми на
защиту, являются:
1. Метод классификации бинарных отношений вершин граф-схем
параллельных алгоритмов, основанный на модели бинарных отношений
достижимости и контрдостижимости графов общего вида, позволяющий
обеспечить распараллеливание процесса классификации бинарных отношений
граф-схем параллельных алгоритмов.
2. Алгоритм транзитивного замыкания бинарного отношения следования
вершин граф-схем параллельных алгоритмов, основанный на алгоритме ФлойдаУоршалла
и
отличающийся
возможностью
досрочного
прерывания
вычислительного процесса нахождения скалярного произведения битовых
векторов.
3. Параллельный алгоритм классификации бинарных отношений вершин
граф-схем параллельных алгоритмов, основанный на последовательной
классификации бинарных отношений, позволяющий частичное совмещение во
времени этапов загрузки исходных данных, заполнения матриц бинарных
отношений битовыми значениями и выгрузки результата и снижение затрат
времени при его практической реализации.
4. Структурно-функциональная
организация
акселератора
для
классификации бинарных отношений вершин граф-схем параллельных
алгоритмов, позволяющая аппаратно-программную реализацию алгоритмов
транзитивного замыкания и классификации бинарных отношений, отличающаяся
использованием многопортового матричного запоминающего устройства с
двухкоординатной адресацией и операционной части с возможностью
эффективного досрочного прерывания вычислительного процесса нахождения
скалярного произведения битовых векторов.
Достоверность результатов, положений и выводов диссертации
обеспечивается корректным
и обоснованным
применением
методов
математической логики, теории множеств и графов, теории проектирования
конечных автоматов, дискретных систем и устройств ЭВМ, и подтверждается
экспертизой РосПатента, результатами практического использования, а также
вычислительным экспериментом с применением зарегистрированных в
установленном порядке программных средств.
Практическая ценность результатов работы заключается в снижении до
2 порядков затрат вычислительного времени при классификации бинарных
отношений вершин граф-схем параллельных алгоритмов за счет разработки
параллельных аппаратно-ориентированных алгоритмов и реализующего их
устройства, что, в свою очередь, снижает затраты времени на построение
5
разбиений граф-схем параллельных алгоритмов логического управления,
повышает производительность труда и коэффициент готовности СЛУ.
Реализация и внедрение. Результаты диссертационного исследования
используются в учебном процессе Юго-Западного государственного университета
в
рамках
дисциплин
«Программирование»,
«Схемотехника
ЭВМ»,
«Теоретические основы проектирования многопроцессорных комплексов и
систем» по направлению «Информатика и вычислительная техника», а также
внедрены в АО «МЦСТ» (г. Москва) и ООО «ГРИФОН СБ» (г. Москва), что
подтверждается соответствующими актами.
Апробация работы. Основные положения диссертационной работы
докладывались и получили положительную оценку на региональных, российских
и международных конференциях: Многоядерные процессоры, параллельное
программирование, ПЛИС, системы обработки сигналов (Барнаул, 18 февраля
2014); Перспективные информационные технологии (Самара, 30 июня – 4 июля
2014); Медико-экологические информационные технологии (Курск, 21–23 мая
2014); Eighth World Conference on Intelligent Systems for Industrial Automation
(Tashkent, 25–27 ноября 2014); Оптико-электронные приборы и устройства в
системах распознавания образов, обработки изображений и символьной
информации (Курск, 12–16 мая 2015); а также на научных семинарах кафедры
вычислительной техники ЮЗГУ с 2013 по 2015 гг.
Публикации. По результатам диссертации опубликовано 13 печатных
работ, среди которых 5 статей в журналах, входящих в перечень рецензируемых
научных изданий, 1 свидетельство о государственной регистрации программы для
ЭВМ (№ 2014619797) и 1 патент на полезную модель (№ 157948).
Личный вклад автора. Все выносимые на защиту научные результаты
получены соискателем лично. В работах по теме диссертации, опубликованных в
соавторстве, лично соискателем выполнено следующее: в [1, 3, 13] исследован
потенциал (достижимая реальная производительность) современного аппаратного
обеспечения с параллельной архитектурой при выполнении операции умножения
матриц; в [2, 6, 7, 15] исследованы возможности практического использования
итерационных эвристических методов в задачах дискретной комбинаторной
оптимизации, в том числе, в задаче поиска разбиений граф-схем параллельных
алгоритмов; в [8] предложена структурно-функциональная организация
запоминающего устройства с матричной структурой для хранения битовых
признаков бинарных отношений; в [9, 11, 12, 14] предложена структурнофункциональная организация операционной части аппаратно-ориентированного
акселератора классификации бинарных отношений вершин, даны оценки
аппаратной сложности и быстродействия; в [10] произведено измерение реальной
пропускной способности шины PCI Express при передаче блока данных из/в
оперативной памяти к/от периферийным устройствам.
Объем и структура работы. Диссертационная работа состоит из введения,
4 глав, заключения, списка литературы из 190 источников и 1 приложения. Работа
содержит 131 страницу основного текста, 24 рисунка и 28 таблиц.
6
Соответствие паспорту специальности. Содержание диссертации
соответствует п. 1 «Разработка научных основ создания и исследования общих
свойств и принципов функционирования элементов, схем и устройств
вычислительной техники и систем управления» в части разработки модели и
принципов функционирования устройства классификации бинарных отношений
вершин граф-схем параллельных алгоритмов и п. 2 «Теоретический анализ и
экспериментальное исследование функционирования элементов и устройств
вычислительной техники и систем управления в нормальных и специальных
условиях с целью улучшения технико-экономических и эксплуатационных
характеристик» паспорта специальности 05.13.05 – Элементы и устройства
вычислительной техники и систем управления в части разработки аппаратноориентированных алгоритмов и устройства классификации бинарных отношений
вершин граф-схем параллельных алгоритмов, обеспечивающих снижение затрат
вычислительного времени на построение их разбиений.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы диссертации, сформулированы
цель и задачи исследований, отмечены научная новизна, практическая ценность и
результаты реализации работы.
В первой главе отмечаются особенности задачи разбиения граф-схем
параллельных алгоритмов логического управления на последовательные блоки
ограниченной сложности, возникающие при проектировании однородных
многомодульных мультисистем в базисе логических мультиконтроллеров
[Ватутин Э.И., Зотов И.В., Титов В.С., 1999–2009], проводится анализ
существующих методов декомпозиции графов и управляющих алгоритмов,
подробно рассматриваются известные аппаратно-ориентированные методы
решения задач на графах.
Задача разбиения алгоритмов управления относится к классу NP-трудных,
что не позволяет находить ее оптимальное решение для управляющих алгоритмов
реальной сложности ( n  100  1000 вершин и более) за приемлемое время.
В связи с этим, на практике используются эвристические методы, требующие, в
ходе их выполнения, информации о бинарных отношениях вершин граф-схемы
параллельного алгоритма управления, для которых производится поиск
разбиения.
Так, по способу формирования решения, выделяются последовательные
методы разбиения (жадные методы, методы С.И. Баранова и А.Д. Закревского,
метод параллельно-последовательной декомпозиции), предусматривающие
формирование единственного решения с использованием ряда эвристик, и
итерационные (метод случайного и взвешенного случайного перебора,
генетические алгоритмы, методы ограниченного перебора, методы муравьиной и
пчелиной колонии, метод имитации отжига [В.М. Курейчик, M. Dorigo, C. Gelatt,
D. Karaboga, S. Kirkpatrick, M. Vecchi и др., 1993–2009 гг.] и их модификации),
подразумевающие перебор вариантов решения и выбор наилучшего. Ряд
известных методов ориентирован на разбиение только последовательных
7
алгоритмов управления, однако допускает простое расширение на класс
параллельных алгоритмов (метод С.И. Баранова), другие методы (метод
А.Д. Закревского,
метод
параллельно-последовательной
декомпозиции)
непосредственно ориентированы на поиск разбиений граф-схем параллельных
алгоритмов. Некоторые из них предполагают сведение задачи выбора разбиения к
другим задачам (метод А.Д. Закревского – к задаче поиска минимальной
раскраски специального графа). Большинство из рассмотренных методов требует
классификации бинарных отношений вершин граф-схемы, для которых
производится поиск разбиения.
Также в теории графов известны ряд задач, которые является в достаточной
степени схожими с задачей классификации бинарных отношений вершин графсхем параллельных алгоритмов. К ним относятся задачи проверки связности
графа и построения числа и состава компонент связности, проверка достижимости
и контрдостижимости вершин графа с использованием соответствующих матриц,
задачи разбиения при крупноблочном распараллеливании вычислений
[В.В. Воеводин, Вл.В. Воеводин, 2002] и проектировании сетецентрических
систем с балансировкой вычислительной нагрузки [И.А. Каляев, Э.В. Мельник,
2011].
Для решения вушеуказанных задач на практике применяются алгоритмы,
большинство из которых характеризуются асимптотической временной
сложностью порядка O n 2   O n5  . При их практической реализации
значительную часть (до 10–23%) вычислительного времени занимают матричные
операции, что делает актуальной попытку снижения указанных затрат
вычислительного времени путем распараллеливания соответствующих
программных реализаций или разработки специализированных аппаратноориентированных
устройств-акселераторов.
Несмотря
на
очевидные
преимущества параллельного выполнения вычислений существует целый ряд
задач, не получающих существенного выигрыша от подобного рода
распараллеливания. Основными недостатками, влияющими на эффективное
параллельное исполнение, являются последовательный характер решаемой
задачи, низкая степень параллелизма (ширина графа задачи), наличие большого
числа синхронизаций и/или обменов данными между узлами используемой
вычислительной системы или ее компонент, приводящих к простою
вычислителей, недостаточный темп поступления данных из памяти. Матричные
операции, возникающие при классификации бинарных отношений вершин, имеют
хороший потенциал для распараллеливания на современных поколениях
вычислителей, к наиболее доступным и распространенным из которых относятся
CPU и GPU.
В то же время известен ряд программно-аппаратных решений,
допускающих получение существенного ускорения путем переноса ряда
преобразований с программного уровня на аппаратный с использованием
специализированных вычислительных средств, жестко адаптированных к
структуре решаемой задачи. Подобные устройства-акселераторы, несмотря на их
относительно узкую сферу применения и, как следствие, высокую стоимость,
8
способны достигать наибольшего выигрыша в быстродействии по сравнению как
с последовательными, так и с параллельными программными реализациями
алгоритмов. Компромиссным решением по себестоимости разработки и
производства, с одной стороны, и реальной производительности, с другой,
является использование программируемых логических интегральных схем
(ПЛИС) в качестве аппаратного обеспечения для реализации схемотехнических
решений.
Во второй главе дается формализованное описание математической
модели системы бинарных отношений вершин граф-схем параллельных
алгоритмов и их свойств, на которых базируются метод, алгоритмы и
предложенная структурно-функциональная организация устройства-акселератора
для их быстрого нахождения.
Известно, что бинарные отношения характеризуются такими свойствами
как транзитивность, рефлексивность и симметричность, которые могут быть
выражены следующими определениями: рефлексивность ( x  S : xRx ),
транзитивность
( x, y, z  S :  xRy    yRz   xRz ),
симметричность
(
x, y  S : xRy  yRx ), где R – некоторое бинарное отношение, x, y, z – элементы
множества S , над которым определено отношение R.
Для рассматриваемого класса граф-схем параллельных алгоритмов
G  A, V , где A  a1 , a2 , ..., aN  – множество вершин, N  A – число вершин,
V  v1 , v2 , ..., vM   A A – множество дуг, M  V – число дуг, вводится
математическая модель системы бинарных отношений [Ватутин Э.И., Зотов И.В.,
Титов В.С., 1999–2009] со следующими свойствами:
- отношение следования  , обладающее свойствами антирефлексивности,
несимметричности и транзитивности;
- отношение связи   , обладающее свойствами рефлексивности,
симметричности и не обладающее свойством транзитивности;
- отношение параллельности  , обладающее свойствами рефлексивности,
симметричности и нетранзитивности;
обладающее
свойствами
- отношение
альтернативы
 ,
антирефлексивности, симметричности и нетранзитивности.
Для произвольного графа возможно введение бинарных отношений
достижимости (связности) и контрдостижимости, являющихся аналогами
отношений следования и связи, определенными для граф-схем параллельных
алгоритмов. Указанные бинарные отношения могут быть представлены в виде
матрицы отношений M R  mij , i, j  1, N , N – число вершин в составе графсхемы алгоритма, которая, в свою очередь, представлена в виде четырех
подматриц M R , M R , M R и M R , соответствующих бинарным отношениям.
Пример граф-схемы и соответствующая ей система бинарных отношений
приведены на рисунке 1 и в таблице 1.
9
a0
a1
a10
a4
a2
a5
a3
a6
a7
a12
a11
a8
a13
a9
Рисунок 1 - Пример граф-схемы алгоритма управления
Таблица 1 - Матрица отношений M R , соответствующая граф-схеме алгоритма
a0
a1
a2
a3
a4
a5
a6
a7
a8
a0








–
, 







a1
–
, 
, 
a2






–
, 
, 
a3






–
, 
, 
a4





–

, 
, 
, 

a5



–

, 
, 
, 
a6




–

, 
, 
a7



–



, 
, 
, 
, 
, 
, 
a8


–
, 
, 
, 
, 
, 
, 
, 
, 
, 
a9
a9









–
Применительно к подклассу ациклических граф-схем параллельных
алгоритмов математическая модель системы бинарных отношений обладает
рядом свойств:
,
(1)
ai a j  ai  a j   ai a j   a j ai  ,
      A A ,
    ,     ,      ,
ai 1a j  ai 2 a j   ai 3a j ,
1 , 2 , 3  , , , 1   2 , 1  3 ,  2  3 .
10
(2)
(3)
(4)
(5)
Указанные свойства математической модели системы бинарных отношений
используются при построении матрицы отношений. В общем случае для графсхем алгоритмов, содержащих циклы, указанная система свойств нарушается,
однако при построении разбиений перед выяснением бинарных отношений
производится специальное преобразование, именуемое разрывом циклов, которое
приводит исходную граф-схему алгоритма к ациклическому виду.
В третьей главе приводится описание метода и алгоритмов классификации
бинарных отношений, ориентированных на программную и аппаратную
реализацию.
Метод классификации бинарных отношений основан на свойствах
математической модели системы бинарных отношений и заключается в
определении значений элементов матрицы смежности:
- определение начальных значений отношения следования по заданной
граф-схеме алгоритма;
- транзитивное замыкание отношения следования;
- определение значений, соответствующих элементам отношения связи, по
результатам транзитивного замыкания отношения следования;
- определение значений отношения альтернативы в ходе анализа ветвей
альтернативных ветвлений в составе заданной граф-схемы алгоритма;
- определение значений отношения параллельности по значениям
отношений связи и альтернативы.
Для определения отношения следования производится его транзитивное
замыкание отталкиваясь от начальных значений, получаемых исходя из
рассмотрения всех дуг передачи управления в составе граф-схемы:
(6)
aia j   a j ak   aiak  .
Для этого в исходной матрице M R необходимо найти такие i, j и k, что
aia j   a j ak    aiak 
(7)
и положить mik : mik   , повторяя указанное действие до тех пор, пока
возможно нахождение элементов, удовлетворяющих (7). При практической
реализации указанного действия существует два подхода. Первый из них основан
на том, что искомое транзитивное замыкание отношения возможно путем
умножения исходной матрицы бинарного отношения самой на себя:
(8)
M R   M R  M R ... M R .
Асимптотическая временная сложность указанного преобразования
составляет O  N 4  , а число умножений матриц составляет в худшем случае N. Ее
можно снизить до O  N 3 log N  путем итерационного возведения исходной
матрицы в квадрат до тех пор,
что в худшем случае требуется
пока ее содержимое не перестанет изменяться, на
 log 2 N  шагов.
11
Преимуществом алгоритма нахождения транзитивного замыкания,
базирующегося на умножении матриц, является превосходный потенциал для
распараллеливания, т.к. как отдельные произведения матриц, так и вычисление
отдельных элементов матрицы и выполнение части действий при вычислении
каждого из них могут быть реализованы параллельно, что позволяет использовать
для его практической реализации широкий спектр известных программных и
аппаратных решений, ориентированных на параллельную форму организации
вычислительного процесса.
Алгоритм умножения бинарных матриц заключается в следующем виде.
1. i : 1 .
2. j : 1 .
3. k : 1.
4. mij : mij  mik mkj .
5. k : k  1 . Если k  N , перейти к п. 4.
6. j : j  1 . Если j  N , перейти к п. 3.
7. i : i  1 . Если i  N , перейти к п. 2.
8. Конец алгоритма.
Искомое транзитивное замыкание может быть гарантировано найдено за
один проход и время O  N 3  с использованием известного алгоритма
Флойда-Уоршалла. Алгоритм транзитивного замыкания бинарного отношения,
основанный на алгоритме Флойда-Уоршалла, отличается от приведенного выше
алгоритма порядком вложения циклов i, j , k   k , i, j  . Однако при этом
существенно снижается потенциал для его распараллеливания, т.к. элементы
результирующей матрицы бинарного отношения связаны зависимостями по
данным.
При использовании современных универсальных вычислительных структур
с параллельной организацией вычислений выяснение транзитивного замыкания с
использованием умножения матриц является предпочтительным. Указанное
действие может быть выполнено на процессорах и видеокартах с поддержкой
технологии GPGPU [1, 3, 11]. При этом время выполнения умножения матриц
лимитируется не вычислительной частью, а темпом поступления исходных
данных из памяти, в связи с чем могут быть применены специальные
алгоритмические оптимизации, учитывающие особенности функционирования
кэш-памяти процессора или глобальной и разделяемой памяти видеокарты.
При выполнении операции умножения на CPU обращение к элементам j-го
столбца матрицы производятся не последовательно с шагом, равным размеру
строки матрицы в памяти, что снижает эффективную емкость кэш-памяти и ее
реальную пропускную способность. Указанного негативного эффекта можно
избежать путем организации предварительной буферизации указанного
j-го столбца, а данный способ получил название буферизованного умножения.
12
При умножении больших матриц, размер которых превышает размер кэш-памяти
CPU, применяется т.н. блочное умножение, при котором результирующая
матрица получается поблочно:
N
S
2S
3S
N
cij   aik bkj   aik bkj   aik bkj   aik bkj  ...   aik bkj 
k 1
k 1
k  S 1
k  SB1
k  N S 1

z
N
S

N
сумм
S
(9)
zS

z 0 k  z1S 1
aik bkj .
Размер порции обрабатываемых данных на каждом шаге не превосходит
размера кэш-памяти CPU. В совокупности с раскруткой внутреннего цикла
указанные алгоритмические оптимизации приводят к снижению времени
выполнения умножения матриц до 40 раз.
Существенно большим потенциалом для распараллеливания указанной
операции умножения матриц обладают современные видеокарты с поддержкой
концепции GPGPU. Для их эффективного использования в указанной задаче
необходима реализация алгоритма блочного умножения по формуле (9) с
раскруткой внутреннего цикла, что позволяет сократить время выполнения
умножения до 2000 раз.
Разработанные программные реализации операции умножения могут быть
эффективно использованы при умножении матриц вещественных чисел, однако
при умножении булевых матриц время выполнения умножения может быть
дополнительно сокращено за счет использовании известного тождества алгебры
логики: x  1  1 . Другими словами, вычисление cij -го элемента матрицы может
быть досрочно прекращено при достижении единичного значения на одном из
промежуточных шагов алгоритма умножения i-й строки и j-го столбца матриц,
который представлен ниже.
13
T : aij .
1. Если T  1 , перейти к п. 8.
2. k : 1.
3. T : T  aik akj .
4. Если T  1 , перейти к п. 8.
5. k : k  1 .
6. Если k  n , перейти к п. 4.
7. aij : T .
8. Конец алгоритма.
При реализации данного алгоритма на универсальных вычислительных
архитектурах
наблюдается
существенное
снижение
реальной
производительности, сводящее на нет преимущество в виде снижения числа
итераций вложенного цикла, причиной чему являются сбросы конвейера CPU при
попытке предсказания направления ветвления, и неэффективное исполнение
WARP'ов из потоков на GPU. Для его эффективного использования необходима
разработка специализированной аппаратной реализации указанных действий с
возможностью досрочного прерывания вложенного цикла.
Выяснение значений матрицы M R возможно непосредственно после
реализации операции транзитивного замыкания отношения следования, причем,
ввиду отсутствия каких-либо зависимостей по данным между результирующими
элементами, оно может быть реализовано за один такт с использованием
специализированной параллельной матричной вычислительной структуры по
формуле:
(10)
ai a j  ai a j   a j ai  .
Выяснение отношения альтернативы, требующее информации о граф-схеме
параллельного алгоритма, рационально осуществлять на программном уровне с
последующей передачей полученной матрицы на аппаратный уровень.
Завершающим этапом классификации отношений является выяснение значений
матрицы M R отталкиваясь от значений матриц M R и M R :
ai a j  ai a j   ai a j  .
(11)
С учетом указанных особенностей аппаратно-ориентированный алгоритм
классификации бинарных отношений вершин граф-схем параллельных
алгоритмов представлен на рисунке 2.
14
ν↓
ν'
ψ↓
φ
ν' ↑
ω
φ↑
ω↑
Рисунок 2 - Параллельный алгоритм аппаратно-ориентированного построения
матрицы отношений (стрелками вниз обозначена передача данных с
программного уровня на аппаратный, вверх – в обратном направлении)
Время выполнения классификации бинарных отношений при его
программной реализации ограничивается временем выполнения процедуры
транзитивного замыкания отношения следования.
В четвертой главе рассмотрены особенности структурно-функциональной
организации аппаратно-программного комплекса классификации бинарных
отношений вершин граф-схем параллельных алгоритмов. Структурнофункциональная организация устройства-акселератора приведена на рисунке 3.
15
5
1
Патент № 157948
СУБМ СБУ
ЗУ ν
PCI Express
6
7
ЗУ φ
М ИЛИ
2
8
4
3
МИ
ЗУ ψ
ЗУ ω
Рисунок 3 - Структурно-функциональная организация устройства-акселератора
классификации бинарных отношений
Она включает в своем составе матричные запоминающие устройства (ЗУ)
1–4 для хранения бинарных отношений следования, связи, параллельности и
альтернативы соответственно, схему умножения бинарных матриц (СУБМ) 5,
схему битового умножения векторов (СБУ) 6, а также матрицы логических
элементов ИЛИ 7 и И 8 [6, 7, 12].
Запоминающие устройства подключены к шине PCI Express с целью
загрузки исходных данных для построения матрицы отношений и выгрузки
результата [8]. В соответствии с рассмотренным выше алгоритмом на первом
шаге работы устройства производится загрузка начальных значений для
определения отношения следования. Вслед за этим в работу вступает схема
умножения битовых матриц, которая с использованием схемы умножения
битовых векторов в соответствии с рассмотренным выше алгоритмом,
базирующемся на алгоритме Флойда-Уоршалла, производит нахождение
транзитивного замыкания отношения следования, после чего обновленная
матрица отношения следования может быть выгружена в оперативную память.
Затем с использованием матрицы элементов ИЛИ 7 возможно определение
значений отношения связи, которое формируется в ЗУ 2, после чего может быть
выгружено в оперативную память. Параллельно с определением значений
следования и связи возможна загрузка отношения альтернативы, определяемого
на программном уровне, в ЗУ 3. После определения матриц отношений связи и
альтернативы с использованием матрицы элементов И возможно определение
отношения параллельности, записываемого в ЗУ 4 и затем выгружаемого в
оперативную память.
Матричное ЗУ имеет структуру ячейки, представленную на рисунке 4.
16
way[j]
ra1y[j]
ra2y[j]
raKy[j]
ra1x[i]
ra2x[i]
raKx[i]
D TT
[i,j]
C
wd[j]
&
Cw
d
2
31
1
wax[i]
41
32
3K
&
&
&
1
1
1
42
rd1
4K
rd2
rdK
Рисунок 4 - Схема ячейки ЗУ для хранения битовых признаков бинарного
отношения
Оно характеризуется возможностью двухкоординатной адресации и
параллельного многопортового чтения данных из ячеек.
Схемотехническая реализация операции булева умножения i-й строки на j-й
столбец матрицы M R приведена на рисунке 5 [9, 10].
C1
ρ
n
n
n
n
n
n
i
j
1
n+1
1
0
C2
0 RG
1
.
.
.
n
DSL
DSR
C
L
0
1
.
.
.
n
n+1
k
2
&
1
n
n
n
4
ra1x
ra1y
ra2x
ra2y
ra3x
ra3y
wax
way
wd
Cw
rd1
rd2
rd3
5
& 1
D TT
&
10
1
Θ
C
ЗУ
ν
n×n×1
&
3
6
1
7
8
9
Рисунок 5 - Схема булева умножения (СБУ) строки и столбца бинарной матрицы
отношения следования
С использованием элемента ИЛИ 10 данная схема реализует возможность
досрочного формирования единичного значения признака готовности  . С ее
использованием представляется возможным реализовать схему умножения
матрицы самой на себя с целью транзитивного замыкания бинарного отношения
(рисунок 6).
17
C1
1
6
n+1
1
0
&
C2
0 RG
1
i
.
.
.
n
DSL
DSR
C
L
0
1
.
.
.
n
0 RG
1
j
.
.
.
n
DSL
DSR
C
L
0
1
.
.
.
n
n+1
5
i
j
МУУ
ρ
C1
C2
СБУ ΘСБУ
2
4
n+1
L
7
&
8
1
0
n+1
Θ
3
Рисунок 6 - Схемотехническая реализация операции умножения битовой матрицы
самой на себя (схема транзитивного замыкания, СТЗ)
Оценка времени работы схемы транзитивного замыкания, лимитирующего
время построения матрицы отношений в целом, определяется как
tСТЗ  tСТЗ 0  ntСТЗ 2  3t0  N n 7  13k  2 log 2 N  k t0  4t0  
(12)
2
2
2


 13 N k  2 N k log 2 N   7 N  4 N t0 .
где k – среднее число итераций работы схемы умножения битовых
векторов (определяется исходными данными, влияющими на плотность матриц),
t0 – время задержки распространения сигнала для эквивалентного вентиля (ЭВ).
При k  0,01N и t0  1 нс с использованием предложенного устройства
достигается выигрыш в скорости обработки от 16 до 139 раз по сравнению с
высоко оптимизированной параллельной программной реализацией в
зависимости от размерности задачи. Например, при N  8192 время программной
классификации отношений составляет 3457 с, использование предложенного
устройства позволяет снизить его до 214,9 с.
Аппаратная сложность предложенного устройства [5] складывается из
сложности запоминающих устройств и операционной части и определяется как
(13)
R  26 N 2  6 N  24 ЭВ.
Например, при реализации аппаратно-программной классификации
бинарных отношений для граф-схем с 8192 вершинами сложность устройства
составляет 1,8 109 ЭВ, что является приемлемым для современного уровня
развития схемотехники и существенно (более чем в 300 раз) ниже аппаратной
сложности известных устройств на базе систолических матричных структур
[А.с. СССР № 1534471].
18
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В диссертационной работе решена научно-техническая задача разработки
метода, алгоритмов и аппаратно-программных средств классификации бинарных
отношений вершин граф-схем параллельных алгоритмов, позволяющих
формировать разбиения при ограниченных затратах времени на их построение.
При этом получены следующие результаты:
1. Проведен анализ существующих методов, алгоритмов, программных и
аппаратных реализаций построения разбиений граф-схем параллельных
алгоритмов логического управления и необходимой при этом классификации
бинарных отношений вершин графов общего вида и граф-схем параллельных
алгоритмов в контексте их ориентации на современные вычислительные
структуры с параллельной организацией процесса обработки информации.
2. Разработан
метод
и
аппаратно-ориентированные
алгоритмы
транзитивного замыкания отношения следования и классификации бинарных
отношений вершин граф-схем параллельных алгоритмов, позволяющие перенести
вычислительно сложные процедуры классификации отношений с программного
уровня на аппаратный. Произведена оценка асимптотических временных
сложностей предложенных алгоритмов. Показано, что модификация алгоритма
Флойда-Уоршалла, используемого для определения отношения следования, не
приводит к изменению его асимптотической временной сложности. Определение
значений отношений связи и параллельности с использованием предложенной
структурно-функциональной организации устройства-акселератора возможно за
время, не зависящее от размерности обрабатываемых данных.
3. Разработана структурно-функциональная организация устройстваакселератора
для
аппаратно-ориентированной
реализации
процедур
транзитивного замыкания отношения следования и выяснения отношений связи и
параллельности, основанная на использовании запоминающего устройства с
матричной организацией, двухкоординатной адресацией и возможностью
параллельного во времени многопортового чтения.
4. Проведена оценка аппаратной сложности предложенного устройства,
позволяющая сделать вывод о снижении аппаратной сложности предложенного
устройства по сравнению с устройствами на базе систолических матричных
структур до 300 раз. В ходе вычислительных экспериментов произведена оценка
выигрыша во времени при аппаратно-ориентированной классификации бинарных
отношений вершин граф-схем параллельных алгоритмов. Показано, что
использование предложенного устройства-акселератора при обработке матриц
бинарных отношений с низкой плотностью позволяет сократить время обработки
до 139 раз по сравнению с высокооптимизированными программными
реализациями.
19
СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ
Статьи в ведущих рецензируемых научных журналах и изданиях
1. Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной
производительности современных процессоров в задаче умножения матриц для
однопоточной
программной
реализации
//
Известия
Юго-Западного
государственного университета. Серия: Управление, вычислительная техника,
информатика. Медицинское приборостроение. – 2013. – № 4. – С. 11–20.
2. Ватутин Э.И., Дремов Е.Н., Мартынов И.А., Титов В.С. Метод
взвешенного случайного перебора для решения задач дискретной комбинаторной
оптимизации // Известия Волгоградского государственного технического
университета. Серия: Электроника, измерительная техника, радиотехника и связь.
– 2014. – № 10 (137). Вып. 9. – C. 59–64.
3. Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной
производительности современных видеокарт с поддержкой технологии CUDA в
задаче умножения матриц // Известия Юго-Западного государственного
университета. Серия: Управление, вычислительная техника, информатика.
Медицинское приборостроение. – 2014. – № 2. – С. 8–17.
4. Мартынов И.А. Оценка аппаратной сложности устройства для быстрой
аппаратно-ориентированной классификации бинарных отношений вершин графсхем параллельных алгоритмов // Известия Юго-Западного государственного
университета. Серия: Управление, вычислительная техника, информатика.
Медицинское приборостроение. – 2015. – № 3 (16). – С. 67–76.
5. Мартынов И.А. Оценка выигрыша во времени обработки при аппаратноориентированной классификации бинарных отношений вершин граф-схем
параллельных алгоритмов // Вестник Череповецкого государственного
университета. – 2015. – № 7 (68). – С. 23–29.
Тезисы докладов и материалы конференций
6. Ватутин Э.И., Колясников Д.В., Мартынов И.А., Титов В.С. Метод
случайного перебора в задаче построения разбиений граф-схем параллельных
алгоритмов // Многоядерные процессоры, параллельное программирование,
ПЛИС, системы обработки сигналов. Барнаул. – 2014. – С. 115–125.
7. Ватутин Э.И., Мартынов И.А., Титов В.С. Способ обхода тупиков при
решении задач дискретной оптимизации с ограничениями // Перспективные
информационные технологии (ПИТ-2014). Самара: изд-во Самарского научного
центра РАН. – С. 313–317.
8. Ватутин Э.И., Мартынов И.А., Титов В.С. Многопортовое матричное
запоминающее устройство для хранения битовых признаков // Медикоэкологические информационные технологии – 2014. Курск: изд-во ЮЗГУ. –
2014. – С. 141–145.
9. 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
20
Intelligent Systems for Industrial Automation (WCIS – 2014). Tashkent. – 2014. –
P. 70–73.
10. Ватутин Э.И., Мартынов И.А. Измерение реальной пропускной
способности шины PCI Express с использованием видеокарт с поддержкой
технологии CUDA в качестве периферийных устройств // Оптико-электронные
приборы и устройства в системах распознавания образов, обработки изображений
и символьной информации (Распознавание – 2015). Курск. – 2015. – С. 242–244.
11. Ватутин Э.И., Мартынов И.А., Наджаджра М.Х. Схемотехническая
реализация операции умножения битовых векторов при классификации бинарных
отношений граф-схем параллельных алгоритмов // Оптико-электронные приборы
и устройства в системах распознавания образов, обработки изображений и
символьной информации (Распознавание – 2015). Курск. – 2015. – С. 275–277.
12. Ватутин Э.И., Мартынов И.А., Титов В.С. Аппаратно-ориентированная
реализация операции транзитивного замыкания бинарных отношений // Оптикоэлектронные приборы и устройства в системах распознавания образов, обработки
изображений и символьной информации (Распознавание – 2015). Курск. – 2015. –
С. 244–247.
Статьи
13. Ватутин Э.И., Мартынов И.А., Титов В.С. Оценка реальной
производительности современных процессоров и видеокарт с поддержкой
технологии CUDA в задаче умножения матриц // CUDA альманах (май 2015). –
2015. – С. 9–10.
Патент
14. Патент 157948 Российская Федерация, МПК G06F 17/16 (2006.01).
Устройство для умножения матриц / Э.И. Ватутин, И.А. Мартынов, В.С. Титов;
патентообладатель Курск. ЮЗГУ. - № 2015127533/08; заявл. 08.07.2015; опубл.
20.12.2015, Бюл. № 35. – 3 с.:ил.
Свидетельства об официальной регистрации программ для ЭВМ
15. Расчетный модуль для тестирования комбинаторных оптимизационных
алгоритмов в задаче поиска кратчайшего пути в графе с использованием
добровольных распределенных вычислений / Э.И. Ватутин, С.Ю. Валяев, Е.Н.
Дремов, И.А. Мартынов, В.С. Титов // Свидетельство о государственной
регистрации программы для ЭВМ № 2014619797; заявл. 28.07.2015;
опубл. 22.09.14.
Подписано в печать ______________. Формат 60×84 1/16 .
Печатных листов 1,0. Тираж 100 экз. Заказ ______.
Юго-Западный государственный университет.
305040, г. Курск, ул. 50 лет Октября, 94.
21
1/--страниц
Пожаловаться на содержимое документа