Содержание к диссертации
Введение
1 Обзор задач, требующих классификации бинарных отношений, и подходов к их практическому решению 12
1.1 Формализованное описание граф-схем алгоритмов управления 12
1.2 Постановка задачи поиска разбиения и ограничения базиса логических мультиконтроллеров 15
1.3 Классификация методов построения разбиений 18
1.4 Обзор задач на графах, требующих классификации бинарных отношений 21
1.5 Обзор классов современного аппаратного обеспечения для программной и аппаратной реализации преобразований матриц отношений 23
1.6 Обзор программных и аппаратных подходов к реализации классификации бинарных отношений с использованием матричных преобразований 26
2 Математическая модель и свойства бинарных отношений вершин граф-схем параллельных алгоритмов 30
2.1 Свойства бинарных отношений 30
2.2 Понятие и свойства бинарных отношений вершин граф-схем параллельных алгоритмов 31
2.3 Понятие матрицы отношений и ее свойства 37
3 Алгоритмы классификации бинарных отношений, ориентированные на программную и аппаратную реализацию 43
3.1 Понятие транзитивного замыкание бинарного отношения и алгоритмы его построения 43
3.2 Анализ эффективности и оптимизация программной реализации алгоритма транзитивного замыкания отношения, основанного на умножении матриц 46
3.3 Аппаратно-ориентированный алгоритм умножения битовых векторов 67
3.4 Стратегия аппаратно-программной классификации бинарных отношений. Аппаратно-ориентированный алгоритм построения матрицы отношений 70
4 Аппратно-программная реализация классификации бинарных отношений вершин 74
4.1 Структурно-функциональная организация устройства-акселератора для аппаратно-ориентированной классификации бинарных отношений 74
4.2 Матричное запоминающее устройство для хранения битовых признаков отношения следования 75
4.3 Схема загрузки данных в запоминающее устройство 78
4.4 Схема булева умножения битовых векторов 78
4.5 Схемотехническая реализация операции транзитивного замыкания отношения следования 82
4.6 Ячейка однородной среды для хранения битовых признаков отношения связи 85
4.7 Ячейки однородной среды для хранения битовых признаков отношений параллельности и альтернативы 87
4.8 Оценка выигрыша во времени при аппаратно-ориентированной классификации бинарных отношений 4.8.1 Оценка времени выполнения преобразований при программной реализации 92
4.8.2 Оценка быстродействия матричного запоминающего устройства для хранения отношения следования 93
4.8.3 Оценка быстродействия схемы умножения битовых векторов 93
4.8.4 Оценка быстродействия схемы транзитивного замыкания отношения следования 94
4.9. Оценка аппаратной сложности акселератора 97
4.9.1. Оценка аппаратной сложности ячейки и запоминающего устройства для хранения битовых признаков 97
4.9.2. Оценка аппаратной сложности операционной части устройства 99
4.10. Сравнительная оценка аппаратной сложности и быстродействия систолических матричных устройств для умножения матриц 102
Заключение 106
Список использованных источников 108
- Обзор классов современного аппаратного обеспечения для программной и аппаратной реализации преобразований матриц отношений
- Понятие и свойства бинарных отношений вершин граф-схем параллельных алгоритмов
- Стратегия аппаратно-программной классификации бинарных отношений. Аппаратно-ориентированный алгоритм построения матрицы отношений
- Схемотехническая реализация операции транзитивного замыкания отношения следования
Введение к работе
Актуальность темы исследования. Системы логического управления (СЛУ) являются одним из распространенных классов цифровых управляющих систем, проблемы анализа и синтеза которых на протяжении многих лет остаются в центре внимания отечественных и зарубежных ученых (С.И. Баранов, А.А. Баркалов, В.И. Варшавский, В.А. Горбатов, А.Д. Закревский, И.В. Зотов, В.Г. Лазарев, В.З. Магергут, Е.И. Пийль, Е.Н. Турута, В.С. Харченко, А.А. Шалыто, С.А. Юдицкий, T. Agerwala, S. Husson, R. Puri и др.). Современные СЛУ, именуемые также логическими мультиконтроллерами (ЛМК), представляют собой параллельные многомодульные однородные мультисистемы, объединяющие тысячи параллельно работающих процессорных узлов (контроллеров). Как правило, это многофункциональные системы, способные оперативно перестраиваться на новый алгоритм управления путем его декомпозиции на блоки ограниченной сложности. Подобные системы могут выполнять комплексные управляющие алгоритмы теоретически неограниченной сложности при условии их предварительного разбиения (декомпозиции) на блоки, назначаемые на отдельные модули мультисистемы. При этом длительность процессов начальной настройки, отладки или последующей перенастройки системы, как правило, выполняемых автоматизировано, во многом определяется временем поиска походящего разбиения, сокращение которого ведет к повышению производительности труда и увеличению коэффициента готовности СЛУ.
Нахождение оптимального решения задачи разбиения практически недостижимо для алгоритмов управления реальной сложности (20 вершин и более) ввиду необходимости перебора и сопоставления очень большого числа различных разбиений. В связи с этим, на практике распространены эвристические алгоритмы декомпозиции, обеспечивающие приближенное (субоптимальное) решение задачи за полиномиальное время с использованием различных структурных преобразований и эвристик (С.И. Баранов, А.А. Баркалов, В.А. Горбатов, А.Д. Закревский, И.В. Зотов, В.С. Харченко, M. Dorigo, C. Gelatt, D. Karaboga, S. Kirkpatrick, M. Vecchi и др.). В независимости от особенностей применяемого алгоритма при построении разбиения необходим учет структурных и технологических ограничений СЛУ, одним из которых является требование отсутствия параллельных вершин в составе блоков разбиения. Его соблюдение, с одной стороны, позволяет существенно упростить структуру контролера в составе СЛУ, но, с другой стороны, приводит к необходимости классификации бинарных отношений вершин заданного алгоритма управления перед построением разбиения, что при программной реализации требует существенных затрат времени и памяти ЭВМ.
Потребность в построении разбиений при ограниченных временных затратах на их получение приводит к необходимости переноса вычислительно сложных процедур, к которым относится классификация бинарных отношений, с программного уровня на аппаратный путем разработки специализированных устройств-акселераторов, жестко адаптированных к особенностям решаемой
задачи. Известные устройства (В.Л. Баранов, В.В. Васильев, Р. Выжиковски, А.Г. Додонов, В.В. Епихин, В.М. Глушань, Н.И. Заболотная, В.А. Калашников, В.В. Косьянчук, В.Г. Красиленко, А.А. Кричмара, С. Кун, В.М. Курейчик, Н.А. Лиходед, С.В. Михляев, П.Г. Романовский, А.А. Сердцев, П.И. Соболевский, П.Е. Твердохлеб, А.Н. Чаплиц, В.Н. Червяцов, Л.И. Щербаков, В.П. Якуш, В.И. Ян, 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.
Объектом исследования являются многомодульные однородные системы логического управления, ориентированные на реализацию комплексных параллельных управляющих алгоритмов.
Предметом исследования являются алгоритмы и аппаратно-программные средства классификации бинарных отношений вершин граф-схем параллельных алгоритмов логического управления.
Целью работы является сокращение временных затрат на построение разбиений граф-схем параллельных алгоритмов логического управления на основе разработки метода, аппаратно-ориентированных алгоритмов и устройства классификации бинарных отношений вершин граф-схем параллельных алгоритмов.
Для достижения поставленной цели в работе решаются следующие основные задачи:
-
Анализ существующих методов, алгоритмов, программных и аппаратных реализаций классификации бинарных отношений вершин графов общего вида и граф-схем параллельных алгоритмов.
-
Разработка метода и аппаратно-ориентированных алгоритмов классификации бинарных отношений вершин граф-схем параллельных алгоритмов, ориентированных на параллельную программно-аппаратную реализацию и позволяющих перенести вычислительно сложные процедуры классификации бинарных отношений с программного уровня на аппаратный.
-
Разработка структурно-функциональной организации устройства-акселератора для реализации наиболее трудоемких операций при классификации бинарных отношений граф-схем параллельных алгоритмов.
-
Проведение вычислительных экспериментов, оценка аппаратной сложности разработанного устройства и выигрыша во времени обработки при его применении.
Новыми научными результатами и положениями, выносимыми на защиту, являются:
-
Метод классификации бинарных отношений вершин граф-схем параллельных алгоритмов, основанный на модели бинарных отношений достижимости и контрдостижимости графов общего вида, позволяющий обеспечить распараллеливание процесса классификации бинарных отношений граф-схем параллельных алгоритмов.
-
Алгоритм транзитивного замыкания бинарного отношения следования вершин граф-схем параллельных алгоритмов, основанный на алгоритме Флойда-Уоршалла и отличающийся возможностью досрочного прерывания вычислительного процесса нахождения скалярного произведения битовых векторов.
-
Параллельный алгоритм классификации бинарных отношений вершин граф-схем параллельных алгоритмов, основанный на последовательной классификации бинарных отношений, позволяющий частичное совмещение во времени этапов загрузки исходных данных, заполнения матриц бинарных отношений битовыми значениями и выгрузки результата и снижение затрат времени при его практической реализации.
-
Структурно-функциональная организация акселератора для классификации бинарных отношений вершин граф-схем параллельных алгоритмов, позволяющая аппаратно-программную реализацию алгоритмов транзитивного замыкания и классификации бинарных отношений, отличающаяся использованием многопортового матричного запоминающего устройства с двухкоординатной адресацией и операционной части с возможностью эффективного досрочного прерывания вычислительного процесса нахождения скалярного произведения битовых векторов.
Достоверность результатов, положений и выводов диссертации обеспечивается корректным и обоснованным применением методов математической логики, теории множеств и графов, теории проектирования конечных автоматов, дискретных систем и устройств ЭВМ, и подтверждается экспертизой РосПатента, результатами практического использования, а также вычислительным экспериментом с применением зарегистрированных в установленном порядке программных средств.
Практическая ценность результатов работы заключается в снижении до 2 порядков затрат вычислительного времени при классификации бинарных отношений вершин граф-схем параллельных алгоритмов за счет разработки параллельных аппаратно-ориентированных алгоритмов и реализующего их устройства, что, в свою очередь, снижает затраты времени на построение
разбиений граф-схем параллельных алгоритмов логического управления, повышает производительность труда и коэффициент готовности СЛУ.
Реализация и внедрение. Результаты диссертационного исследования используются в учебном процессе Юго-Западного государственного университета в рамках дисциплин «Программирование», «Схемотехника ЭВМ», «Теоретические основы проектирования многопроцессорных комплексов и систем» по направлению «Информатика и вычислительная техника», а также внедрены в АО «МЦСТ» (г. Москва) и ООО «ГРИФОН СБ» (г. Москва), что подтверждается соответствующими актами.
Апробация работы. Основные положения диссертационной работы докладывались и получили положительную оценку на региональных, российских и международных конференциях: Многоядерные процессоры, параллельное программирование, ПЛИС, системы обработки сигналов (Барнаул, 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 таблиц.
Соответствие паспорту специальности. Содержание диссертации соответствует п. 1 «Разработка научных основ создания и исследования общих свойств и принципов функционирования элементов, схем и устройств вычислительной техники и систем управления» в части разработки модели и принципов функционирования устройства классификации бинарных отношений вершин граф-схем параллельных алгоритмов и п. 2 «Теоретический анализ и экспериментальное исследование функционирования элементов и устройств вычислительной техники и систем управления в нормальных и специальных условиях с целью улучшения технико-экономических и эксплуатационных характеристик» паспорта специальности 05.13.05 - Элементы и устройства вычислительной техники и систем управления в части разработки аппаратно-ориентированных алгоритмов и устройства классификации бинарных отношений вершин граф-схем параллельных алгоритмов, обеспечивающих снижение затрат вычислительного времени на построение их разбиений.
Обзор классов современного аппаратного обеспечения для программной и аппаратной реализации преобразований матриц отношений
Число возможных разбиений для заданной граф-схемы алгоритма логического управления, включающей в своем составе N вершин, ограничено сверху числом Белла [19], что делает невозможным построение оптимальных разбиений [30] для граф-схем с 7V 10 15, а соответствующая задача поиска подобного разбиения попадает в класс труднорешаемых (TVP-трудных). Ввиду необходимости ее решения на практике прибегают к использованию эвристических методов, которые обеспечивают получение субоптимальных решений за приемлемое время с различным отклонением качества оптимизации частных показателей (1.2) от оптимума.
Существующие методы и алгоритмы поиска суб- и квазиоптимальных разбиений, следуя классификации [1-4], могут быть разделены на два класса: последовательные и итерационные. Методы первого из названных классов предполагают синтез единственного решения, не подразумевая какого-либо перебора вариантов решения. При этом разбиение алгоритма управления на блоки получается путем последовательного перебора вершин, не включенных в ранее образованные блоки, и выбора из них наилучшего кандидата на включение в формируемый блок. Выбор вершин-кандидатов осуществляется на основе множества частных критериев (эвристик), определенным образом увязанных с общим показателем оптимальности разбиения. Процесс выбора вершин продолжается до тех пор, пока имеются вершины, не включенные ни в один из блоков разбиения. К числу подобных методов можно отнести, например, метод С.И. Баранова [20, 21] и его модификации [22, 23], являющиеся по сути классическими жадными методами, а также метод параллельно-последовательной декомпозиции [24–29].
Локально-оптимальный безвозвратный характер последовательных методов и отсутствие средств глубокого анализа результатов выбора вершин-кандидатов на включение в блок на несколько шагов вперед как правило обусловливают невысокое качество получаемых решений [31–45]. Указанный недостаток может быть частично устранен, например, при введении специальных процедур, позволяющих оценить результаты выбора того или иного локального варианта с возможностью реализации комбинаторного возврата [46] в случае попадания в тупиковую ветвь дерева комбинаторного перебора или следуя стратегии ветвей и границ, однако при этом возможно существенное увеличение асимптотической временной сложности алгоритма в целом (вплоть до факториальной или экспоненциальной, что неприемлемо).
Итерационные алгоритмы, в отличие от последовательных, предполагают выбор оптимального разбиения из некоторой совокупности решений и реализуют перебор различных вариантов разбиения по ряду правил, специфичных для выбранного метода и как правило также имеющих эвристический характер. В некоторых случаях для их работы требуется предварительный выбор начального решения. Это решение может быть определено либо случайным образом, либо в результате выполнения последовательного алгоритма. В качестве условия окончания работы итерационных алгоритмов обычно используется заданное количество рассмотренных решений либо ограничение на время вычислительного эксперимента. Примером подобных алгоритмов могут служить алгоритмы полного и случайного перебора [30, 42, 47–49]. Также к этому классу можно отнести и ряд других алгоритмов [50–55], включающих генетические, эволюционные и/или биоинспирируемые методы, метод имитации отжига, вариации случайного перебора и другие.
Алгоритмам данного класса присуще существенно различное качество получаемых разбиений в различных задачах, а их асимптотическая временная (емкостная) сложность достигает на несколько порядков больших величин, что приводит к существенно большим необходимым затратам вычислительного времени и, по-видимому, является причиной слабой проработанности данных методов на практике в указанном классе задач. Вместе с тем итерационные алгоритмы находят широкое применение при решении схожих треднорешаемых задач, к примеру, при компоновке элементов на этапе коммутационно-монтажного проектирования радиоэлектронной аппаратуры [57], а также при решении задачи размещения алгоритмов в распределенных и параллельных структурах [58–60], в задачах теории графов [63–66] и пр.
Существуют также и другие классификации методов поиска разбиений, основанные на универсальности или учете специфики решаемой задачи (так, например, метод С.И. Баранова с незначительными модификациями может строить разбиения как последовательных, так и параллельных граф-схем алгоритмов, хотя разрабатывался для класса последовательных граф-схем, а метод параллельно-последовательной декомпозиции специально ориентирован на класс параллельных граф-схем) или на сведении указанной задачи к известной (например, к раскраске графа специального вида, как это было предложено в работах А.Д. Закревского [61, 62]). Некоторым из них свойственен ряд дополнительных недостатков, таких как невозможность оптимизировать разбиения по некоторым частным показателям качества или отсутствие соблюсти все ограничения (например, раскраска графа не подразумевает наличие каких-либо дополнительных ограничений кроме отсутствия смежных вершин одного цвета, что с успехом реализуется на графе бинарного отношения параллельности вершин, в то время как поддержка технологических ограничений отсутствует, а ее введение чревато существенной переделкой известных алгоритмов и их программных реализаций в совокупности с потерей универсальности).
Понятие и свойства бинарных отношений вершин граф-схем параллельных алгоритмов
Если же осуществлять хранение, например, только верхней треугольной подматрицы в формате для этого потребуется m — l) + (w — 2) + ... + 1 = ячеек памяти, т.е. имеет место почти двукратная экономия, что составляет немалую величину, учитывая квадратичную зависимость затрат памяти для хранения матрицы отношений от размерности решаемой задачи. При аппаратной реализации использование свойства симметричности бинарных отношений способствует снижению аппаратной сложности запоминающего устройства и части логических схем.
При хранении всех элементов матрицы обращение к элементу m фактически приводит к обращению по адресу addr/w = addrM + \ii — X)n + j — \)s, (2.6) где addrMfl - адрес в памяти первого элемента матрицы отношений, а s -размер одного элемента матрицы отношений (в байтах или битах). Исключение из рассмотрения диагональных элементов несколько усложняет формулу: addrM + ((/ -1)(п -1) + j - \)s, і j, addr/wy , / = j, (2.V) addrM + ((/ -1)(n -1) + j - 2)s, і j, где прочерк соответствует отсутствующим в матрице диагональным элементам. Если же производится хранение, например, только верхней треугольной подматрицы, то адрес искомого элемента mij вычисляется как i(2n — i — \) addrM + + j - /, / j, addrw. = —, i = j, (2-8) j(2n-j-\) addrM + L + i-j, / y. Синтезированная и хранящаяся одним из описанных выше способов матрица отношений позволяет выяснить состав множества отношений между интересующей парой вершин за время, не зависящее от размерности задачи п. При больших п объем матрицы отношений может превышать объем кэш-памяти CPU или разделяемой памяти GPU, поэтому с целью повышения эффективности обработки могут применяться специальные алгоритмические приемы, рассмотренные в разделе 3. При аппаратно-ориентированной реализации хранения матрицы битовых признаков [166] удобно использовать двухкоординатное запоминающее устройство, что избавляет от необходимости расчета адресов.
Следуя работам [153, 165], выяснение значений компонентов матрицы отношений будем производить в ходе следующих преобразований. 1. Получение ациклической граф-схемы G+ алгоритма путем идентификации и разрыва циклов в исходной граф-схеме G . 2. Объединение линейных участков граф-схемы G+ (при необходимости) с целью уменьшения размерности задачи [167]. 3. Заполнение начальных значений отношения следования матрицы MVR отталкиваясь от вершин граф-схемы G+, непосредственно соединенных дугой. 4. Транзитивное замыкание отношения следования с целью получения окончательно сформированной матрицы отношения следования MVR. 5. Заполнение значений отношения связи матрицы MR отталкиваясь от сформированных ранее значений матрицы MVR. 6. Анализ альтернативных ветвлений, построение альтернативных путей, заполнение значений отношения альтернативы матрицы MR . 7. Заполнение значений матрицы отношения параллельности M отталкиваясь от сформированных ранее значений матриц М% и Мд .
Как уже было отмечено выше, для граф-схем алгоритмов с циклами множество свойств (2.1-2.5) в общем случае несправедливо, поэтому циклы должны быть ликвидированы в первую очередь. Данное преобразование может изменить часть отношений, однако оно не затрагивает распределение отношения параллельности, что является важным с позиции соблюдения структурных ограничений (1.1) при синтезе корректного разбиения. Объединение линейных участков выполняется с целью получение из последовательностей вершин, выполняемых подряд друг за другом, обобщенных вершин, что впоследствии снижает размерность решаемой задачи и позитивно влияет как на сокращение времени выполняемых преобразований, так и на затраты памяти при программной реализации и аппаратную сложность запоминающего устройства. Порядок выяснения отношений определяется зависимостями по данным, которые, в свою очередь, следуют из свойств системы бинарных отношений (2.1-2.5). Выяснение конкретных значений элементов матриц для каждого из отношений базируется на их свойствах и более подробно рассмотрено ниже.
Выяснение отношения следования основано на его транзитивности: если ava и avak, то atvak. После задания начальных значений матрицы между парами вершин а. и а., непосредственно соединенными дугой (а,а.у: тг :={ } в матрице MVR осуществляется поиск элементов mi , т.к и mik, таких что (у Є тЛ/\(у Є тА/\(у тА, (2.9) и включение отношения v в множество отношений элемента mik. Процесс поиска и включения продолжается до тех пор, пока возможно нахождение элементов, соответствующих условию (2.9). Указанное преобразование фактически приводит к транзитивному замыканию [168] отношения следования, отталкиваясь от матрицы смежности граф-схемы О . Как уже было отмечено выше, вершины ai и а находятся в отношении связи, если atva или a vaj (2.2). Выяснение отношения сводится к однократному просмотру элементов матрицы отношений с целью выделения таких элементов т , что v є т , и включению отношения ф в состав элементов т и т : ті. := mv U {ф} т}і:=т}і\]Щ.
Выяснение выделению альтернативных ветвей ветвлений L є Ф и заданию отношения альтернативы для вершин, входящих в состав различных ветвей в рамках одного ветвления: если а, є L , а, є L , причем L є Фф и Z є Фф, то о, чіхх : mkk :={і)}. Для однозначного определения окончания альтернативных ветвлений в алгоритме должны быть вершины объединения альтернативных дуг. При выяснении отношения альтернативы следует иметь в виду, что возможны произвольные комбинации вложения альтернативных ветвлений различных типов друг в друга в виде дочерних фрагментов.отношения альтернативы сводится к поиску альтернативных фрагментов Ф ,
Стратегия аппаратно-программной классификации бинарных отношений. Аппаратно-ориентированный алгоритм построения матрицы отношений
В результате применения данного алгоритма для всех /, j = 1, TV получается модифицированная матрица MR, представляющая собой искомое транзитивное замыкание отношения следования.
Существенной особенностью данного алгоритма является сокращение числа итераций внутреннего цикла (по переменной к). При умножении матриц с большим число единиц число выполняемых итераций по к будет малым, что существенно уменьшает как число выполняемых операций, так и число обращений к памяти. Однако при программной реализации с использованием универсальных конвейерных суперскалярных вычислителей у данного способа экономии числа выполняемых операций есть группа недостатков, которые существенно снижают выигрыш от его использования. Прежде всего, при программной реализации в коде появляются условные переходы, паттерн срабатывания которых является нерегулярным. При их спекулятивном исполнении наблюдаются частые сбросы вычислительного конвейера CPU ввиду неправильного предсказания направления перехода, что приводит к сбросу конвейера. Как известно [170, 171], данная ситуация является негативной и снижает эффективность работы процессора в несколько десятков раз. Т.е. ценой экономии выполняемого числа операций является проигрыш в реальной производительности за счет сбросов конвейера, отнимающий практически все преимущества рассмотренного алгоритма.
При реализации указанного алгоритма на GPU, вычислители которой также имеют спекулятивную конвейерную архитектуру, имеет место тот же недостаток. Однако к нему добавляются еще два. Первый из них связан с планированием запуска потоков путем из объединения в WARP ы [102]. При наличии в составе WARP а хотя бы одного условия, сработавшего в сторону различных альтернатив, WARP запускается дважды, снижая тем самым реальную производительность в два раза. При наличии в коде нерегулярно срабатывающих условий данная ситуация существенно усугубляется и потоки в составе WARP ов исполняются неэффективно, что образует первый недостаток. Второй недостаток связан с тем, что благодаря наличию условий различные потоки обращаются к различным элементам матрицы, нарушая требование на формирование coalesced-запросов. Нарушение данного требования практически на порядок снижает эффективную пропускную способность глобальной памяти GPU, что является критическим фактором в рассматриваемой задаче.
Таким образом, в совокупности указанные негативные факторы существенно снижают эффективность программных реализаций при выполнении умножения неплотных битовых матриц, выполняемым в ходе реализации транзитивного замыкания, что не позволяет разработку эффективной программной реализации, ориентированной на современные универсальные классы аппаратного обеспечения с параллельно-конвейерной архитектурой, и вынуждает осуществлять разработку специализированной аппаратно-ориентированной реализации, способной нивелировать влияние условий и получить выигрыш от сокращения числа итераций при выполнении умножения битовых векторов.
С учетом рассмотренных в главе 2 особенностей системы бинарных отношений вершин граф-схем параллельных алгоритмов заполнение матрицы отношений можно производить, совмещая во времени классификацию некоторых отношений. При этом на аппаратный уровень целесообразно перенести наиболее трудоемкие этапы, при параллельной реализации которых возможно получение максимального выигрыша во времени обработки, к которым относится выяснение отношений следования, связи и параллельности. Выяснение отношения альтернативы достаточно эффективно реализуется на программном уровне с использованием алгоритма, описанного в [153], его перенос с программного уровня на аппаратный представляется в настоящее время нецелесообразным. Общая схема обмена данными между программным и аппаратным уровнем приведена на рисунке 3.4. RAM обменов данными, возникающих при аппаратно-ориентированном построении матрицы отношений MR (каждый из квадратов представляет собой область памяти RAM либо специализированное запоминающее устройство для хранения одного из бинарных отношений)
Исходные и результирующие матрицы бинарных отношений хранятся в оперативной памяти (RAM). На начальном этапе производится формирование начальных значений для отношений следования и альтернативы, после чего производится их передача в специализированные матричные запоминающие устройства акселератора. Затем производится выполнение транзитивного замыкания отношения следования, следом за ним – выяснение отношения связи, а затем – параллельности. После выполнения указанных действий матрицы отношений следования, связи и параллельности передаются обратно в оперативную память. Обмен данными между оперативной памятью и матричной памятью устройства может быть реализован с использованием DMA, что позволяет разгрузить центральный процессор, занятый в это время выполнением другими задач. Соответствующий описанному параллельный аппаратно-ориентированный алгоритм классификации бинарных отношений вершин граф-схем параллельных алгоритмов может быть представлен в следующем виде (рисунок 3.5).
Схемотехническая реализация операции транзитивного замыкания отношения следования
Прежде всего, сопоставление времени обработки с временем передачи исходных данных (в данном случае, матрицы, содержащей исходные значения для определения значения следования) показывает, что время передачи занимает менее 1% от общего времени обработки и может не учитываться при расчете выигрыша. При обработке матриц, для которых не происходит раннего прерывания работы схемы СБУ, использование предложенного устройства нецелесообразно, т.к. по сравнению с программной реализацией оно обеспечивает проигрыш во времени обработки до 6 раз при 7V = 8196. Транзитивное замыкание отношения следования для подобных матриц целесообразно находить с использованием классического умножения матриц с использованием SIMD-ориентированной [111, 112], CUDA-ориентированной [ПО] программной или специализированной аппаратной реализации [122-146, 178], ориентированной на использование матричных и/или систолических вычислительных структур. При обработке матриц отношения следования для реальных граф-схем параллельных алгоритмов наблюдается частая возможность досрочного прерывания работы схемы СБУ (—0,1 0,01], что позволяет эффективное использование предложенного устройства и обеспечивает выигрыш во времени обработки от нескольких десятков раз (7V = 2564-8196 при к = 0,017V, TV = 128 при к = 0,17V) до сотен раз (7V = 128 при к= 0,017V), подтверждая целесообразность его разработки. Следует также отметить, что приведенные выше оценки получены для значения времени задержки распространения сигнала вентиля t0=\ нс, по порядку величины совпадающего с ПЛИС-реализацией. При реализации устройства в заказном исполнении указанное время задержки может быть снижено приблизительно на порядок, что приблизительно на порядок увеличивает потенциальный теоретический выигрыш.
Оценку аппаратной сложности [189] будем производить в эквивалентных вентилях (ЭВ) с целью абстрагироваться от деталей заказной или ПЛИС-реализации устройства, понимая под эквивалентным вентилем одно- или двухвходовой логический элемент, выполняющий элементарную логическую операцию (И, ИЛИ, НЕ и т.д.). В таком случае TV-входовой логический элемент имеет аппаратную сложность 7V —1 ЭВ, 73-триггер - 4 ЭВ, элемент задержки - 2 ЭВ, TV-разрядный регистр - 47V.
Аппаратная сложность устройства складывается из сложности ЗУ и сложности обрабатывающей логики в его составе.
Ячейка ЗУ (ЯЗУ), используемая для хранения битовых признаков бинарных отношений, в общем случае включает в себя следующие элементы (таблица 4.8). Таблица 4.8 - Элементы ячеек ЗУ и их аппаратная сложность
Элемент Аппаратная сложность, ЭВ И 1 2 ТТ 2 4 И 3i 2 ИЛИ 4i 1 Совокупная аппаратная сложность ячейки ЗУ может быть определена как (4.15) R 2a + 4 +K 2a+ 3 + 4, ЯЗУ 2 + 1 И ЛИ И1 TT2 ЯЗ,- ЯЖ 4, где a є {0,1} - битовый признак необходимости записи с использованием двухкоординатной адресации, К - число портов чтения. Отталкиваясь от формулы (4.15), характеризующей сложность ячейки ЗУ в общем виде, можно определить сложность ячеек ЗУ, хранящих значения бинарных отношений, в соответствии со спецификой (см. таблицу 4.1) выполняемых преобразований (таблица 4.9). Аппаратная сложность, ЭВ 7 6 Таблица 4.9 - Оценка аппаратной сложности ячеек ЗУ, хранящих битовые признаки бинарных отношений Отношение a К Следования 1 3 Связи 0 і Параллельности 0 і Альтернативы 1 0 С учетом приведенных в таблице 4.9 сложностей ячеек можно оценить сложность ЗУ в целом. В его состав (рисунок 4.3) входит N ячеек и группа из К N-входовых элементов ИЛИ, используемых при чтении данных с использованием портов чтения. Соответственно сложность ЗУ в общем случае определяется как RЗУ = NRЯЗУ-\-K\N — V). (4-16) ИЛИ При хранении бинарных отношений, обладающих свойством симметричности (связь, параллельность и альтернатива), можно ограничиться хранением только верхней треугольной подматрицы, а соответствующая аппаратная сложность может быть определена как
С использованием данных таблицы 4.9 и формул (4.16) и (4.17) можно оценить сложности запоминающих устройств для хранения битовых признаков бинарных отношений (таблица 4.10).
Операционная часть устройства (рисунок 4.1) представлена схемами умножения битовых векторов, транзитивного замыкания отношения (умножения битовых матриц) и матрицами элементов ИЛИ и И. Ее аппаратная сложность может быть определена как
В состав схемы умножения битовых векторов (рис. 4.5) входят следующие элементы (таблица 4.12), не считая матричного ЗУ, сложность которого вычислена выше, и устройства управления. Таблица 4.12 - Оценка аппаратной сложности схемы умножения битовых векторов