Введение к работе
Актуальность работы. Современная микроэлектронная технология обеспечивает возможность производства СБИС общей емкостью порядка 2 млрд. транзисторов, что позволяет реализовать на одной микросхеме мультикомпьютеры, содержащие до 100 полнофункциональных процессорных элементов. Многие ведущие производители (Intel, IntellaSys, Reytheon, Tilera) уже предлагают или планируют в ближайшем будущем выпуск подобных однокристальных мультикомпьютеров (ОМК). Учитывая технологические ограничения СБИС, в качестве топологической структуры ОМК, как правило, используется двумерная матрица. Типичным представителем подобных однокристальных систем являются матричные мультикомпьютеры фирмы Tilera (TILEPro36, TILE64, TILEPro64, TILE-Gx), объединяющие от 32 до 100 процессорных элементов, соединенных коммуникационной средой в двухмерную матричную структуру.
Функционирование ОМК сопряжено с выполнением ряда коммуникационных операций, к которым относятся обращения к внешней памяти, межпроцессорный обмен данными и координационные управляющие взаимодействия. Эти операции вносят существенный вклад в общее время выполнения параллельных программ, ограничивая потенциально достижимую производительность мультикомпьютера. Одной из них является барьерная синхронизация. Она заключается в согласовании моментов завершения и запуска параллельных участков программы (ветвей, процессов) в определенной ее точке (называемой барьером) и предполагает приостановку выполнения некоторых процессов до наступления условия синхронизации, при котором все требуемые процессы достигли барьера. Весьма часто барьерная синхронизация применяется при реализации итеративных вычислений для обеспечения скоординированного перехода множества процессов к следующей итерации цикла.
Реализация барьерной синхронизации на программном уровне связана с необходимостью передачи большого числа служебных сообщений между взаимодействующими процессами (особенно при большой мощности барьерной группы), что вносит значительные задержки в общее время выполнения программы. Несмотря на то, что путем определенных преобразований параллельной программы можно достичь сокращения числа барьеров, полностью исключить их из большинства программ принципиально невозможно. Вследствие этого снижение времени барьерной синхронизации в ОМК обеспечивается путем аппаратной поддержки данной процедуры. Такой подход уже нашел воплощение во многих коммерческих системах (CM-5, Cray T3D, Cray T3E, SGI Origin 3000, IBM Blue Gene и др.) и широко представлен в литературе в виде различных аппаратно-ориентированных процедур синхронизации (J.-S. Yang, M.X.T. Delgado, H.D. Dietz, R. Hoare, T.A. Johnson, S.T. Kofuji, P.K. McKinley, C.-T. King, D.K. Panda и др.). При этом получили распространение два уровня аппаратной реализации. Первый из них (гибридный) предполагает аппаратную поддержку синхронизации путем схемной модификации стандартных узловых коммуникационных устройств. Второй уровень (аппаратный) предусматривает использование отдельных барьерных процессоров или координирующих сред в дополнение к стандартной коммуникационной среде ОМК.
Большинство известных процедур барьерной синхронизации (независимо от уровня реализации) не учитывают особенности итеративных параллельных вычислений, выполняя координационную операцию в конце каждой итерации цикла как независимую операцию, что сопряжено с многократной инициализацией / финализацией барьерной группы. В свою очередь, процедуры, поддерживающие циклически выполняемые барьеры, характеризуются рядом недостатков, затрудняющих их эффективное применение в ОМК. Так, для гибридных процедур характерен значительный поток служебных сообщений, который может достигать нескольких тысяч сообщений на один барьер и серьезно ограничивать пропускную способность коммуникационной сети. Большинство аппаратных процедур синхронизации устанавливают жесткие ограничения на размещение синхронизируемых процессов на множестве модулей ОМК, что не позволяет эффективно использовать ограниченные процессорные ресурсы системы и вступает в противоречие со стандартами параллельного программирования. Известные распределенные аппаратные процедуры синхронизации, которым не свойственно указанное ограничение, характеризуются недостаточным быстродействием, поскольку предполагают распространение координирующих сигналов по всей матрице процессоров без учета фактического размещения синхронизируемых процессов.
Исходя из сказанного выше, существует объективная необходимость разработки процедур и аппаратных средств барьерной синхронизации для матричных ОМК, обеспечивающих уменьшение времени синхронизации за счет ограничения области распространения координирующих сигналов, исключения многократной инициализации/финализации барьерных групп при выполнении циклических программ и ослабляющих ограничения на размещение синхронизируемых процессов на множестве процессоров.
Научно-технической задачей диссертации является разработка процедуры и устройства распределенной барьерной синхронизации для матричных ОМК, обеспечивающих уменьшение времени синхронизации при итеративных параллельных вычислениях и снижающих ограничения на размещение синхронизируемых процессов в процессорных модулях (ПМ).
Объект исследования: аппаратные средства барьерной синхронизации в составе однокристальных матричных мультикомпьютеров (матричных ОМК).
Предмет исследования: методы, алгоритмы и схемы устройств барьерной синхронизации параллельных процессов в матричных ОМК.
Работа выполнена при поддержке грантов Президента РФ МД-685.2009.8 и МД-2218.2011.8, а также в соответствии с планом НИР ЮЗГУ в 2008-2011 гг.
Целью диссертационной работы является уменьшение среднего времени барьерной синхронизации при итеративных параллельных вычислениях в матричных однокристальных мультикомпьютерах путем разработки процедуры и устройства распределенной барьерной синхронизации с динамическим ограничением области распространения координирующих сигналов.
Для достижения поставленной цели необходимо решение следующих частных задач:
-
Провести сравнительный анализ существующих процедур и устройств барьерной синхронизации.
-
Разработать процедуру распределенной барьерной синхронизации, позволяющую снизить время барьерной синхронизации при выполнении итеративных параллельных программ в матричных ОМК.
-
Построить математическую модель процедуры распределенной барьерной синхронизации с целью обоснования ее корректности.
-
Разработать структурно-функциональную организацию отдельного устройства барьерной синхронизации в составе координирующей среды матричного ОМК. Оценить аппаратную сложность и временные характеристики предложенного решения.
-
Провести экспериментальные исследования функционирования разработанного устройства в составе координирующей среды матричного мультикомпьютера с целью оценки среднего времени синхронизации.
Научная новизна результатов исследований:
-
Создана процедура распределенной барьерной синхронизации для матричных ОМК, отличающаяся динамическим ограничением области распространения координирующих сигналов и исключением повторной инициализации/финализации барьерных групп, позволяющая снизить время передачи координирующих сигналов и тем самым уменьшить среднее время барьерной синхронизации в условиях наличия циклически выполняемых барьеров.
-
Синтезирована дискретная математическая модель процесса распределенной барьерной синхронизации на основе аппарата сетей Петри, позволившая путем анализа достижимых маркировок доказать отсутствие тупиковых ситуаций в процессе синхронизации с использованием разработанной процедуры в матричных ОМК с произвольным числом ПМ.
-
Разработана структурно-функциональная организация устройства распределенной барьерной синхронизации, включаемого в состав координирующей среды ОМК совместно с другими аналогичными устройствами, новизна которой заключается в наличии блоков для динамического формирования области распространения координирующих сигналов (ограничивающей области) и блоков генерации, приема и передачи сигналов опроса и запуска процессорных модулей внутри сформированной области, за счет чего обеспечивается сокращение длины цепей распространения координирующих сигналов и уменьшение времени синхронизации для циклически выполняемых барьеров.
-
Разработана имитационная модель разработанного устройства в терминах расширенного языка Q-схем, отличающаяся наличием новых моделирующих агрегатов – массовых контроллеров, инкапсулирующих правила распространения управляющих и координирующих сигналов при формировании ограничивающей области и в ходе барьерной синхронизации, позволяющая реализовать статистическое моделирование работы координирующей среды матричного ОМК и исследовать зависимости среднего времени синхронизации от размера ограничивающей области.
Достоверность результатов диссертации обеспечивается корректным и обоснованным применением положений и методов математической логики, теорий: множеств и графов, вероятностей и математической статистики, систем и сетей массового обслуживания, проектирования устройств ЭВМ и систем, аппарата сетей Петри, а также подтверждается совпадением теоретических выводов с результатами имитационного моделирования.
Практическая значимость работы:
-
Использование разработанного устройства в качестве модуля координирующей среды матричного ОМК обеспечивает снижение времени синхронизации за счет исключения повторной инициализации / финализации барьерных групп в условиях итеративных вычислений, при этом максимальное время синхронизации на одной итерации цикла для матричных ОМК с числом процессоров до 1000 не превышает 1.4 мкс (при задержке вентиля равной порядка 3 нс).
-
Разработанная структурно-функциональная организация устройства барьерной синхронизации позволяет динамически выделять множество участвующих в синхронизации процессов, обеспечивая уменьшение области распространения координирующих сигналов и обусловленное этим сокращение среднего времени синхронизации. Аппаратная сложность предложенного устройства не превышает 25 тыс. эквивалентных вентилей (ЭВ) на модуль для всех практически значимых случаев, что в совокупности позволяет сохранить приемлемую сложность СБИС ОМК.
На защиту выносятся следующие научные результаты:
-
Аппаратно-ориентированная процедура распределенной барьерной синхронизации для матричных ОМК, отличающаяся динамическим ограничением области распространения координирующих сигналов, позволяющая исключить опрос части не участвующих в синхронизации модулей, устранить необходимость повторной инициализации/финализации барьерных групп и тем самым снизить среднее время синхронизации при итеративных вычислениях.
-
Математическая модель процесса распределенной барьерной синхронизации на основе аппарата сетей Петри, описывающая распространение двоичных сигналов в координирующей среде ОМК на каждом этапе синхронизации, позволяющая на основе исследования множества достижимых маркировок моделирующей сети Петри доказать корректность разработанной процедуры синхронизации, а также ее инвариантность к размещению синхронизируемых процессов внутри ограничивающей области при условии, что ее длина составляет ПМ.
-
Структурно-функциональная организация устройства распределенной барьерной синхронизации, входящего в состав координирующей среды ОМК, отличающаяся наличием блоков для динамического формирования области распространения координирующих сигналов, а также блоков генерации, приема и передачи сигналов опроса и запуска процессорных модулей внутри сформированной области.
-
Результаты аналитической оценки аппаратной сложности и максимальной задержки распространения координирующих сигналов, экспериментальной оценки среднего времени синхронизации для предложенного устройства в зависимости от размера ограничивающей области, подтверждающие снижение среднего времени синхронизации циклически выполняемых барьеров и целесообразность реализации средств барьерной синхронизации ОМК на базе коллектива разработанных устройств.
Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы внедрены в ООО «Визор» (г. Курск), а также используются в учебном процессе на кафедре вычислительной техники ЮЗГУ в рамках дисциплин «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров», «Отказоустойчивые многопроцессорные платформы», в курсовом и дипломном проектировании.
Апробация работы. Основные положения и результаты диссертационной работы были заслушаны и получили одобрение на Юбилейной Международной научно-технической конференции «Медико-экологические информационные технологии» (г. Курск, 2007), Всероссийской научно-технической конференции «Интеллектуальные и информационные системы» (г. Тула, 2009), IX Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2010), XVII Российской научно-технической конференции «Материалы и упрочняющие технологии - 2010» (г. Курск, 2010), Международной конференции «Information and Telecommunication Technologies in Intelligent Systems» (Lugano, Schweiz, 2010), а также на научных семинарах кафедры вычислительной техники ЮЗГУ (ранее КурскГТУ) с 2008 по 2011 г.
Публикации по теме диссертации. Результаты диссертационной работы отражены в 9 публикациях, в числе которых 3 статьи, опубликованные в научных изданиях из Перечня ВАК, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.
Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах личный вклад соискателя сводится к следующему: в [1] выполнен сравнительный анализ методов распределенной барьерной синхронизации в матричных системах, в [2] разработана процедура барьерной синхронизации с динамическим ограничением области распространения координирующих сигналов, в [3,4,8] сформулированы принципы обмена координирующими сигналами при реализации барьерной синхронизации, в [5] получена зависимость аппаратной сложности устройства синхронизации от параметров координирующей среды ОМК, в [6,7] предложен подход к снижению времени барьерной синхронизации при итеративных вычислениях за счет исключения не участвующих в синхронизации процессоров, в [9] разработаны наиболее важные сущности иерархии моделирующих агрегатов.
Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 134 страницы текста (с учетом приложений) и поясняется 26 рисунками и 5 таблицами; список литературы включает 94 наименования.
Области возможного использования. Результаты диссертационной работы могут найти применение при разработке коммуникационных устройств матричных мультикомпьютеров различной размерности, а также в матричных локальных сетях и ccNUMA-мультипроцессорах.
