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

На правах рукописи

АЛЬ-ХАДИ АБДУЛРАХМАН МОХАММЕД АЛИ

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

СИГНАЛОВ

05.13.05 - Элементы и устройства вычислительной техники и систем управления

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 6 июн 2011

КУРСК-2011

4850149

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

Научный руководитель:

доктор технических наук, профессор

Зотов Игорь Валерьевич

Официальные оппоненты:

доктор технических наук, профессор Атакищев Олег Игоревич

кандидат технических наук Сусин Павел Викторович

Ведущая организация: Тульский государственный университет

Защита состоится 27 июня 2011 г. В 12 часов на заседании совета по защите докторских и кандидатских диссертаций Д 212.105.02 при Юго-Западном государственном университете по адресу: 305040, Курск, ул. 50 лет Октября, 94 (конференц-зал).

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

Автореферат разослан 26 мая 2011 г.

Ученый секретарь совета по защите докторский и кандидатских диссертаций Д 212.105.02

Е.А. Титенко

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Современная микроэлектронная технология обеспечивает возможность производства СБИС общей емкостью порядка 2 млрд. транзисторов, что позволяет реализовать на одной микросхеме мультикомпьюте-ры, содержащие до 100 полнофункциональных процессорных элементов. Многие ведущие производители (Intel, IntellaSys, Reytheon, Tilera) уже предлагают или планируют в ближайшем будущем выпуск подобных однокристальных мульти-компьютеров (ОМК). Учитывая технологические ограничения СБИС, в качестве топологической структуры ОМК, как правило, используется двумерная матрица. Типичным представителем подобных однокристальных систем являются матричные мультикомпьютеры фирмы Tilera (TILEPro36, TILE64, TILEPro64, TILE-Gx), объединяющие от 32 до 100 процессорных элементов, соединенных коммуникационной средой в двухмерную матричную структуру.

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

Реализация барьерной синхронизации на программном уровне связана с необходимостью передачи большого числа служебных сообщений между взаимодействующими процессами (особенно при большой мощности барьерной группы), что вносит значительные задержки в общее время выполнения программы. Несмотря на то, что путем определенных преобразований параллельной программы можно достичь сокращения числа барьеров, полностью исключить их из большинства программ принципиально невозможно. Вследствие этого снижение времени барьерной синхронизации в ОМК обеспечивается путем аппаратной поддержки данной процедуры. Такой подход уже нашел воплощение во многих коммерческих системах (СМ-5, Cray T3D, Cray ТЗЕ, SGI Origin 3000, IBM Blue Gene и др.) и широко представлен в литературе в виде различных аппаратно-ориентированных процедур синхронизации (J.-S. Yang, М.Х.Т. 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 гг.

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

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

1. Провести сравнительный анализ существующих процедур и устройств барьерной синхронизации.

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

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

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

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

Научная новизна результатов исследований:

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

2. Синтезирована дискретная математическая модель процесса распределенной барьерной синхронизации на основе аппарата сетей Петри, позволившая путем анализа достижимых маркировок доказать отсутствие тупиковых ситуаций в процессе синхронизации с использованием разработанной процедуры в матричных ОМК с произвольным числом ПМ.

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

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

Достоверность результатов диссертации обеспечивается корректным и обоснованным применением положений и методов математической логики, теорий: множеств и графов, вероятностей и математической статистики, систем и сетей массового обслуживания, проектирования устройств ЭВМ и систем, аппарата

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

Практическая значимость работы:

1. Использование разработанного устройства в качестве модуля координирующей среды матричного ОМК обеспечивает снижение времени синхронизации за счет исключения повторной инициализации / финализации барьерных групп в условиях итеративных вычислений, при этом максимальное время синхронизации на одной итерации цикла для матричных ОМК с числом процессоров до 1000 не превышает 1.4 мкс (при задержке вентиля равной порядка 3 не).

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

На защиту выносятся следующие научные результаты:

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

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

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

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

Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы внедрены в ООО «Визор»

(г. Курск), а также используются в учебном процессе на кафедре вычислительной техники ЮЗГУ в рамках дисциплин «Теоретинеские основы проектирования отказоустойчивых мультимикропроцессоров», «Отказоустойчивые многопроцессорные платформы», в курсовом и дипломном проектировании.

Апробация работы. Основные положения и результаты диссертационной работы были заслушаны и получили одобрение на Юбилейной Международной научно-технической конференции «Медико-экологические информационные технологии» (г. Курск, 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-мультипроцессорах.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

TBS -> min; CBS -> max; EBS < EBS, где TBS - среднее время синхронизации; CBS - комбинаторная гибкость средств синхронизации; EBS - структурная сложность средств синхронизации (EBS -предельно допустимое значение).

Приоритетной количественной характеристикой средств синхронизации является время OßS, которое определяется как средний интервал между достижением барьера последним синхронизируемым процессом и моментом запуска последнего процесса из барьерной группы. Комбинаторная гибкость CBS представляет собой отношение числа допустимых вариантов размещения синхронизируемых процессов среди модулей ОМК к общему числу таких вариантов и в пределе равна единице. Структурная сложность EBS определяет сложность реализации средств синхронизации и может включать объем программного кода, аппаратную сложность и т.п.

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

сообщений. При таком подходе в большинстве случаев синхронизация осуществляется путем настройки коммуникационной'среды на соединение синхронизируемых процессов с целью снижения времени передачи сообщений (обеспечивается поддержка циклически выполняемых барьеров). Этот подход обеспечивает высокую комбинаторную гибкость CBS —> 1 и приемлемую структурную сложность EBS < EBS, но характеризуется большим потоком служебных сообщений (до нескольких тысяч на один барьер), что снижает общую пропускную способность коммуникационной сети и ведет к возрастанию времени TBS.

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

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

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

Представим структуру матричного ОМК в виде графа Я =<M,U >, где M -множество вершин, соответствующее множеству однотипных ПМ, a U — множество дуг, отражающее связи мювду ПМ. Для каждого ПМ зададим составной порядковый номер (i,j), ; =1,ЛГ], j = \,N2, где Nl - число строк в процессорной матрице, а Лг2 - число столбцов, Nl> 1, N2> 1, и в общем случае Л;, ^Лг2. Вершины графа Я сопоставим множеству ПМ так, что

[{mij'm(M)j)& и>' = U^i-DJ=

■ w/.0+D ) e u' J = '' - !)> ' = N\-где m,j - ПМ с порядковым номером (i, j). Мультикомпьютер, представленный описанным способом, обозначим как jyrW.

Основу разработанной процедуры составляет следующий принцип. Синхронизация параллельно выполняющихся процессов (ветвей) программы и запуск ожидающих ПМ базируются на формировании и циклическом распространении координирующих сигналов, являющихся значениями двоичных индикаторных функций 2Д/)е{0,1}, в множестве одноразрядных слоев синхронизации Ки = {К^Кг,..,Кп}, где п - максимально возможное количество параллельных барьеров. Каждый слой синхронизации К^, I = 1,п, соответствует определенному барьеру и представляет собой совокупность ячеек координирующей среды, распределенных между ПМ и соединенных согласно матричной топологической структуре.

Каждому процессорному модулю поставим в соответствие вектор (и) = (у[^(и),у'^(и),..,у'^(и)), устанавливающий зависимость между ПМ и барьерами и-й программы. Значение у'^(и) = 0, если ПМ т^ выполняет ветвь программы и, завершающуюся барьером V,, в противном случае у'/-1 (м) = 1. Также введем признак завершения ветви программы с?е(<). Если сЦ(() = 0, то ПМ т1^ еще не выполнил е-ю ветвь программы, завершающуюся барьером \>5, если же

<5е(*) = 1, то ветвь программы завершена.

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

Для описания процесса формирования ограничивающего прямоугольника на первом этапе синхронизации введем ряд признаков. Каждому ПМ поставим в соответствие признак его включения в ограничивающую область Если

к'/(0 = 1, то ПМ находится в границах области, в противном случае ПМ находится вне области и не принимает участия в синхронизации. Значение признака ^"Ч0 формируется на основании значений признаков наличия соседних ПМ, обозначающихся в дальнейшем как М^Ц) - для соседа сверху, - для сосе-

да снизу, Ьг'^Ц) - для соседа справа, Ы'^Ц) - для соседа слева. Эти признаки определяют тот факт, что хотя бы один из ПМ, находящихся в г-й строке или в у'-м столбце с соответствующей, стороны от ПМ т1), находится внутри ограничивающей области, и устанавливаются согласно условиям:

=о V #и+1)(0; =А/^ЧО у к^о)-

Значение признака () формируется следующим образом:

приу^(и) = 0; (КЧО л ЩЧО) V (К'(0 л 0) V

V А «Л0) V А V

V л /7/^(0) V («ЛО л Аг;->(0), «рм УЛ") = 1. Другими словами, признак к1/^) принимает значение 1, если ПМ выполняет ветвь программы и, завершающуюся барьером либо ПМ получил любые два признака наличия соседних ПМ. То есть процесс формирования ограничивающей области и установка признаков к'/(1) происходит поэтапно, начиная с ПМ, входящих в барьерную группу, а затем посредством распространения признаков наличия соседних ПМ ИЬ'/Ц), Г). чт0 позволяет, не обладая данными о размещении синхронизируемых ветвей, исключить не участвующие в синхронизации ПМ.

На втором этапе синхронизации происходит циклический опрос и запуск ПМ, входящих в барьерную группу. Этап начинается тогда, когда определяются значения для всех ПМ, входящих в ОМК. Опрос и запуск ПМ организуются в виде последовательности циклов распространения координирующих сигналов в слое Ки. Каждый цикл включает две фазы: 1) опрос ПМ о завершении ими ветвей программы и формирование признака синхронизации = 1; 2) запуск ПМ по достижении барьера и восстановление исходного значения = 0. Распространение признака синхронизации происходит от ПМ, находящегося в верхнем левом углу ограничивающей области, и до ПМ, расположенного в ее нижнем правом углу. Обозначим эти ПМ как т.. . и т.. .. соответственно.

Выделим из множества М подмножество вершин т/ ■ еМ*, удовлетворяющее условию (V/,7 еМ* :(г >/*)д(7 >_/*)л(; <г")л(_/<_/'")). Данное

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

Текущее состояние ПМ определим двоичным признаком состояния

251 (0 = У*3(*)у(0• Тогда для индикаторной функции 2^(1) 5-го барьера можно записать ZJ (/) = л г'^ (г).

Для определения значения индикаторной функции Zs(¿) на выходе каждого ПМ введем понятия большего и меньшего порядкового номера ПМ. Будем считать, что ПМ Л имеет меньший порядковый номер, чем ПМ т^ Л, т{, Л < т^,

если (/, </2)л (у, < у2)л((/1 * У2))- Аналогично будем считать, что ПМ

имеет больший порядковый номер, чем ПМ Щх > ^, если

(/', > /2) л Ц > у2) а ((/, * /2) V (у, * у2)).

Тогда значение функции Zs(t) на выходе (/, у) -й ячейки слоя К5 для ПМ ] будет равно 1, если ПМ завершил свою ветвь программы (или не участвует в

5-м барьере) и все ПМ с меньшими порядковыми номерами к этому моменту также завершили ветви программы, относящиеся к 5-му барьеру (или не участвуют в нем). Соответственно, момент времени I' завершения всех ветвей барьера V, задается условием (У) = (/') = 0 -»1.

Значение функции на выходе (/,у)-й ячейки слоя К5 для ПМ не зависит от текущего состояния ПМ и равно 1, только если на выходах ПМ с большими порядковыми номерами уже установлено единичное значение. Условие

окончания второй фазы синхронизации: (¿") = 1 ->0. Фазы повторя-

ются циклически.

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

Иг'^Ц), происходит удаление ограничивающей области. Сброс

признаков наличия соседних ПМ происходит согласно условиям:

= А £5(Ы)"' (0; = О Л

К'(0=Ч'о+1)(0 л А/"«) = Ы'/^Ц) л 0.

Признаки обнуляются согласно следующему выражению:

[О, при у'/(и) = 0-,

[(й^С) А л Нг"(0 Л Ы'/(1)1 при у';\и) = 1.

Таким образом, признак вхождения ПМ сбрасывается, если ПМ т{ ]

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

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

Подсети Петри Л^у, И = {1,Ь,г,1}, моделируют получение и распространение признаков наличия соседних ПМ 0. Подсеть Петри А* • отображает формирование признака вхождения ПМ в ограничивающую область . Соединенные между собой согласно двумерной матричной топологии сети Петри образуют объединенную сеть 0, моделирующую

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

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

Переход я. отображает завершение выполнения ветви программы модулем mLJ, 7t*j - запуск ПМ по завершении барьера, ïïj j и л)- прохождение сигнала синхронизации через ячейку координирующей среды. Соединение подсетей A'j j и A"j согласно двумерной матричной топологии приводит к получению двух

подсетей: Л' и Л". Подсеть Л' отражает динамику формирования признака синхронизации внутри ограничивающей области, а подсеть Л" - передачу данного признака и запуск ПМ. Соединенные между собой подсети Л' и Л* образуют сеть Л, моделирующую поведение отдельного слоя координирующей среды на втором этапе синхронизации.

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

Рис. 1. Сеть Петри 0, ;

а)

б)

Рис. 2. а) подсеть Л] j ; б) подсеть Л("

Анализ достижимых маркировок сетей Петри ©, Л, Н показал, что они являются живыми, а максимальная емкость позиций равна соответственно 3, 1 и 8. Это доказывает отсутствие тупиковых ситуаций как при построении/удалении области распространения координирующих сигналов, так и при опросе и запуске ПМ.

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

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

Назначение основных элементов и блоков устройства следующее.

Регистр 1 служит для хранения значения вектора соответствия Ъ1^ (и) данного ПМ. Дешифратор 2 предназначен для приема от ПМ номера барьера, которым завершается выполняемая им ветвь программы. Дешифратор 3 служит для приема номера барьера, по достижении которого необходимо произвести запуск ПМ. Дешифратор 4 и группа элементов 5.1-5.и предназначены для выделения слоя координирующей среды. Элементы 6-13 служат для генерации глобальных тактирующих сигналов, с помощью которых определяется момент завершения первого этапа синхронизации. Элемент ИЛИ 14 и одновибратор 15 предназначены для генерации сигнала запуска ПМ при выполнении барьера. Блок формирования прямоугольника 16-5, детализированный на рисунке 5, служит для генерации и приема сигналов построения ограничивающей области. Блок формирования сигналов завершения этапов 17.« предназначен для определения момента начала второго этапа синхронизации. Блок опроса и запуска 18.б служит для формирования признака синхронизации и генерации сигнала запуска для текущего ПМ.

Рис. 3. Сеть Петри .

Представленное устройство позволяет динамически выделять и освобождать отдельные слои синхронизации в процессе выполнения мультикомпьютером параллельной программы (с поддержкой функций стандарта параллельного программирования MPI). При выделении слоя происходит ограничение области распространения сигналов с учетом текущего расположения входящих в барьерную группу ПМ, после чего внутри нее осуществляется циклический опрос и запуск данных ПМ; за счет этого обеспечивается снижение времени синхронизации циклически повторяющихся барьеров. Синхронизируемые процессы могут произвольно размещаться среди модулей ограничивающей области, при этом длина ее сторон не должна быть меньше 2 ПМ.

4

log2n

5.1

п 1

с

5.п

logj« 78 -у** 79

Iog2n 80

81

D DC

— г

Ln

D DC

En 3

82

83.

84.

85. 86878889-

' ,А

90

и

91_, xf 6

93 9495 96-

^ С

кг

R TT

S 10

&h2

16.5

17.5

-АЛ-

_97 -98

"п-99

100

13

Î}

18.5

101

102

-тЦ—103

15

404

-105

Рис. 4. Функциональная схема разработанного устройства распределенной барьерной синхронизации

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

^ = [1оё2 л](3/7 + 6)+ 173« + 38 ЭВ,

где п- число слоев в координирующей среде ОМК, ] - округление до большего целого. Согласно данному выражению при п <128 аппаратная сложность

WBS <25тыс. ЭВ на один модуль. Минимальная аппаратная сложность (и = 1) составляет 211 ЭВ на модуль.

Рис. 5. Блок формирования прямоугольника 16.5

В четвертом разделе проводится аналитическая оценка максимального времени синхронизации, получаемого при использовании разработанного устройства. С помощью вычислительного эксперимента исследуется зависимость среднего времени синхронизации от числа ПМ ОМК и размера ограничивающей области.

Максимальное время синхронизации на одной итерации цикла 7},шах равно

Т,Г =(7(ЛГ/ + ЛГ2') + 2/0&и-з)гэя,

где , М'2 — длины сторон ограничивающей области , п - число слоев синхронизации, 1ЭВ - задержка ЭВ. Согласно этому выражению величина Г„тах в явном виде не зависит от размеров матрицы ОМК, что позволяет снизить время синхронизации в условиях параллельных итеративных вычислений.

Максимальное время переключения слоя между барьерами Г51шах равно Та™ = (14шах(ЗД) + 6(ЛГ, + Щ) +19)^.

Среднее время синхронизации на одну итерацию цикла TBsmi" составляет

гп max __ т шах , тг> max / j 1BS ~1Il ' 1 '

где I- число итераций цикла.

Для сравнения приведем значения времени синхронизации аналогичных устройств для ОМК размера NixNz=32x32 при числе участвующих в синхронизации процессоров 256 и t3B = 3не: прототип [параллельно-последовательный барьерный синхронизатор (ППБС)] - ~ 1,9 мке, [М.Х.Т. Delgado, S.T. Kofují] -«\,6мкс, [S. Moh, С. Yu, В. Lee и др.] --Ъмкс, [J.-S. Yang, С.-Т. King] - »5.икс. Время синхронизации для разработанного устройства при 1 = 1 не превышает «3,1 мке, что соизмеримо с аналогами. При 1 = 3 оно составляет »1,5 мке, а при / = 16» 0,8 мке, т.е. в два раза ниже, чем у аналогичных устройств.

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

Рис. 6. Q-схема ¡-го модуля имитационной модели

Состав схемы и назначение элементов следующее.

Генераторы служат для выдачи заявок, имитирующих подачу

сигналов синхронизации модулям, расположенным на границах ограничивающей области (генерация заявок происходит на каждой итерации); очереди предназначены для хранения пришедших с соответствующего направления заявок; клапаны К11,КЬ1,К11 ,Кг1 и К, 3, Кь 3, Кь 3, Кг 3 разрешают передачу заявок между соответствующими генератором и очередью, либо удаляют заявки из системы; клапаны К,2,КЬ2,К12,КГ2 предназначены для разрешения передачи заявок соседним модулям; клапаны К,4,Кь4,К, 4, Кг4 служат для удаления заявок из

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

Моделирование проводилось для ОМК размером NlxN2 =15x15. При этом расположение ограничивающей области и ветвей программы внутри него задавалось случайно. Время выполнения ветвей программы устанавливалось согласно нормальному закону распределения с параметрами fi = SN, а = 3.27V. Результаты

моделирования показаны с учетом t3B = 3не.

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

Т,п 500 400 300 200 100 0

10 20 30 40 50 60 70 80 90 % Рис. 7. Зависимость времени T¡, от соотношения размеров ограничивающей области и матрицы ОМК (%)

На рисунке 8 изображены графики зависимости среднего времени синхронизации TBS от количества итераций цикла I. При площади ограничивающего прямоугольника равной 25%, 50% и 75% от площади матрицы ОМК.

TBS, не 1300 1100 900 700 500 300 100

Рис. 8. Зависимость времени TBS от числа итераций цикла I

Согласно полученным зависимостям с увеличением количества итераций цикла значительно снижается среднее время синхронизации, что объясняется меньшим влиянием на него задержки инициализации/финализации ограничивающей области. Сравнение разработанного устройства с прототипом при данных значениях параметров ОМК показывает, что выигрыш в среднем времени синхронизации при типовых значениях числа итераций цикла (10-100) достигает 2-3 раз.

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

не

В приложениях приводятся тексты проектов имитационного моделирования, данные, полученные в ходе вычислительного эксперимента, акты внедрения.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

В ходе решения этой задачи получены следующие основные результаты:

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

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

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

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

Список публикаций по теме диссертации

Статьи в научных изданиях по перечню ВАК Минобрнауки РФ

1. Аль-Хади, A.M. Методы распределенной барьерной синхронизации параллельных процессов в матричных СБИС-системах [Текст] / И.В. Зотов, C.B. Во-лобуев, A.M. Аль-Хади // Нейрокомпьютеры: разработка, применение. 2009. №12. С. 46-52.

2. Аль-Хади, A.M. Распределенная процедура барьерной синхронизации с динамическим ограничением области распространения координирующих сигна-

лов [Текст] / А.М. Аль-Хади, С.А. Муратов, И.В. Зотов // Телекоммуникации. 2011. №5. С. 2-7.

3. Аль-Хади, А. Организация отказоустойчивого межпроцессорного взаимодействия в матричных мультикомпьтотерах [Текст] / А.Аль-Хади, И.В .Зотов [и др.] // Известия ТулГУ. Бизнес-процессы и бизнес-системы. Тула: ТулГУ, 2006. Вып.4. С.

4. Аль-Хади, A.M. Универсальная коммуникационная процедура для параллельных вычислительных систем [Текст] / A.M. Аль-Хади, И.В. Зотов [и др.] // Медико-экологические информационные технологии материалы докладов Юбилейной Международной научно-технической конференции, Курск, 24-25 апреля 2007 г -Курск КурскГТУ, 2007 - С 163-167.

5. Аль-Хади, A.M. Оценка аппаратной сложности распределенного барьерного синхронизатора n-мерной матричной многопроцессорной системы [Текст] / A.M. Аль-Хади, С.В. Волобуев, И.В. Зотов // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы IX международной конференции, Курск, 2010 г. Курск: КурскГТУ, 2010. С. 161-162.

6. Аль-Хади, A.M. Об ограничении области распространения координирующих сигналов при реализации барьерной синхронизации в матричных системах [Текст] / A.M. Аль-Хади, И.В. Зотов [и др.] // Всероссийская научно-техническая конференция «Интеллектуальные и информационные системы»: Тульский государственный университет, Тула, 2009. С. 80-82.

7. Аль-Хади, A.M. Распределенная аппаратная процедура барьерной синхронизации с частичным исключением не участвующих процессоров [Текст] / А.М. Аль-Хади, И.В. Зотов, С.В. Волобуев // XVII Российская научно-техническая конференция «Материалы и упрочняющие технологии - 2010 ». С. 201-205.

8. Al-Hadi, A.M. A distributed parallel pipelined barrier synchronizer for N-dimensional mesh-connected multiprocessor systems [Текст] / A.M. Al-Hadi, S.V. Volobuev, I.V. Zotov // Proceedings of Seventh International Conference «Information and Telecommunication Technologies in Intelligent Systems». 2010. P. 89-94.

Свидетельство о государственной регистрации программы для ЭВМ

9. Аль-Хади, A.M. Программа имитационного моделирования матричных коммутаторов с отказоустойчивой маршрутизацией пакетов / A.M. Аль-Хади и др. // Свидетельство об официальной регистрации программы для ЭВМ №2009612576; заявл. 23.03.2009; per. 21.05.2009.

3-9.

Материалы конференций и тезисы докладов

Соискатель

А.М. Аль-Хади

Подписано в печать 15.05.2011 г. Формат 60x84 1/16 . Печатных листов 1. Тираж 120 экз. Заказ 5? Юго-Западный государственный университет, 305040, Курск, ул. 50 лет Октября, 94.

ВВЕДЕНИЕ

1. МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ НА КРИСТАЛЛЕ. ПОНЯТИЕ БАРЬЕРНОЙ СИНХРОНИЗАЦИИ И МЕТОДЫ ЕЕ РЕАЛИЗАЦИИ

1.1. Однокристальные мультикомпьютеры

1.2. Координационные процессы. Процедура барьерной синхронизации. Особенности синхронизации итеративных вычислений

1.3. Методы барьерной синхронизации 17 1.3.1. Программные методы- барьерной синхронизации *

1.3.2 Гибридные методы барьерной синхронизации

1.3.3 Аппаратные методы барьерной синхронизации 25 Выводы

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

2.1. Концептуальный базис процесса синхронизации

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

2.3. Математическая модель координирующей среды 47 Выводы

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

3.1. Структурно-функциональная организация модуля распределенного барьерного синхронизатора

3.2. Процесс функционирования распределенного барьерного синхронизатора

3.3. Оценка аппаратной сложности распределенного барьерного синхронизатора

Выводы 81 4. ОЦЕНКА БЫСТРОДЕЙСТВИЯ РАСПРЕДЕЛЕННОЙ ПРОЦЕДУРЫ И УСТРОЙСТВА БАРЬЕРНОЙ СИНХРОНИЗАЦИИ С ДИНАМИЧЕСКИМ

ОГРАНИЧЕНИЕМ ОБЛАСТИ РАСПРОСТРАНЕНИЯ СИГНАЛОВ

4.1. Максимального времени синхронизации

4.3. Постановка и результаты вычислительного эксперимента

4.3.1. Постановка эксперимента

4.3.2. <3-схема моделируемой системы

4.3.3. Результаты вычислительного эксперимента 93 Выводы

Актуальность работы. Современная микроэлектронная технология обеспечивает возможность производства СБИС общей емкостью порядка- 2' млрд. транзисторов, что позволяет реализовать на одной микросхеме мультикомпьютеры, содержащие до 100 полнофункциональных процессорных элементов. Многие ведущие производители (Intel, IntellaSys, Reytheon, Tilera) уже предлагают или планируют в ближайшем будущем выпуск подобных однокристальных мультикомпьютеров (ОМК). Учитывая* технологические ограничения СБИС, в качестве топологической структуры ОМК, как правило, используется двумерная матрица. Типичным представителем подобных однокристальных систем являются матричные мультикомпьютеры фирмы Tilera (TILEPro36, TILE64, TILEPro64, TILE-Gx), объединяющие от 32 до 100 процессорных элементов, соединенных коммуникационной средой в двухмерную матричную структуру.

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

Реализация барьерной синхронизации на программном уровне связана с необходимостью передачи большого числа служебных сообщений между взаимодействующими процессами (особенно при большой- мощности барьерной группы); что вносит значительные задержки в общее время выполнения программы. Несмотря на то,, что путем определенных преобразований параллельной, программы можно достичь сокращения, числа барьеров, полностью исключить их из большинства программ принципиально невозможно. Вследствие этого снижение времени барьерной синхронизации в ОМК обеспечивается путем аппаратной поддержки данной процедуры. Такой подход уже нашел воплощение во многих коммерческих системах (СМ-5, Cray T3D, Cray ТЗЕ, SGI Origin 3000, IBM Blue Gene и др.) и широко представлен в литературе в виде различных аппаратно-ориентированных процедур синхронизации (J.-S. Yang, М.Х.Т. Delgado, H.D. Dietz, R. Hoare, T.A. Johnson, i

S.T. Kofuji, P.K. McKinley, C.-T. King, D.K. Panda и др.). При этом получили-распространение два уровня аппаратной реализации. Первый из них (гибридный) предполагает аппаратную поддержку синхронизации путем-схемной модификации стандартных узловых коммуникационных устройств. Второй уровень (аппаратный) предусматривает использование отдельных барьерных процессоров или координирующих сред в дополнение к стандартной коммуникационной среде ОМК.

Большинство известных процедур барьерной синхронизации, (независимо от уровня реализации) не учитывают особенности итеративных параллельных вычислений, выполняя координационную операцию в конце каждой итерации цикла как независимую операцию, что сопряжено с многократной инициализацией / финализацией барьерной группы. В свою очередь, процедуры, поддерживающие циклически выполняемые барьеры, характеризуются рядом недостатков, затрудняющих их эффективное применение в ОМК. Так, для гибридных процедур характерен значительный поток служебных сообщений, который может достигать нескольких тысяч сообщений на один барьер и серьезно ограничивать пропускную способность коммуникационной сети. Большинство аппаратных процедур синхронизации устанавливают жесткие ограничения на размещение синхронизируемых процессов на множестве модулей ОМК, что не позволяет эффективно использовать ограниченные процессорные ресурсы системы и вступает в противоречие со- стандартами параллельного программирования. Известные распределенные аппаратные процедуры* синхронизации, которым не свойственно указанное ограничение, характеризуются недостаточным быстродействием, поскольку предполагают распространение координирующих сигналов по всей матрице процессоров без учета фактического размещения синхронизируемых процессов.

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

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

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

Предмет исследования: методы, алгоритмы и схемы устройств барьерной синхронизации параллельных процессов в матричных ОМК.

Работа выполнена при поддержке грантов Президента РФ МД-685.2009.8 и МД-2218.2011.8, а также в соответствии с планом НИР ЮЗГУ в 2008-2011 гг.

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

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

1. Провести сравнительный анализ- существующих процедур и устройств барьерной синхронизации.

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

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

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

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

Научная новизна результатов исследований:

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

2. Синтезирована дискретная математическая модель процесса распределенной барьерной синхронизации на основе аппарата сетей Петри, позволившая путем анализа достижимых маркировок доказать отсутствие тупиковых ситуаций в процессе синхронизации с использованием разработанной процедуры в матричных ОМК с произвольным/числом ПМ.

3: Разработана структурно-функциональная организация устройства распределенной барьерной синхронизации, включаемого в состав координирующей среды ОМК совместно с другими аналогичными устройствами, новизна которой заключается в наличии блоков» для динамического формирования области распространения координирующих сигналов (ограничивающей области) и блоков генерации, приема и передачи сигналов опроса и запуска процессорных модулей внутри сформированной области, за счет чего обеспечивается сокращение длины цепей распространения координирующих сигналов и уменьшение времени синхронизации для-циклически выполняемых барьеров.

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

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

Практическая значимость работы:

1. Использование разработанного устройства в качестве модуля координирующей; среды матричного ОМК обеспечивает снижение времени синхронизации за счет исключенияповторной инициализации / финализации барьерных: групп в условиях итеративных вычислений, при этом максимальное время!синхронизации;на одной итерации- цикла для?матричных ОМК с числом процессоров до 1000' не превышает 1.4 мкс (при: задержке вентиля« равной порядка 3; не):

2. Разработанная структурно-функциональная;! организация устройства барьерной синхронизации позволяет динамически выделятьI множество; участвующих в синхронизации процессов; обеспечивая уменьшение области распространения координирующих сигналов и обусловленное этим сокращение среднего времени синхронизации. Аппаратная сложность, предложенного устройства; не превышает 25 тыс. эквивалентных вентилей'(ЭВ) на модуль для всех практически значимых случаев, что в совокупности позволяете сохранить, приемлемую сложность СБИС ОМК.

На защиту выносятся следующие научные результаты:

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

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

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

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

Практическое использование результатов работы. Основные научные результаты и выводы диссертационной работы внедрены в ООО «Визор» (г. Курск), а также используются в учебном процессе на кафедре вычислительной техники ЮЗГУ в рамках дисциплин «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров»,

Отказоустойчивые многопроцессорные платформы», в курсовом и дипломном проектировании.

Апробация работы. Основные положения и результаты диссертационной-работы были заслушаны и получили одобрение на Юбилейной Международной научно-технической конференции «Медико-экологические информационные технологии» (г. Курск, 2007), Всероссийской научно-технической конференции «Интеллектуальные и информационные системы» (г. Тула, 2009), IX Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания- образов, обработки изображений и символьной информации» (г. Курск, 2010), XVII Российской научно-технической конференции «Материалы и упрочняющие технологии -2010» (г. Курск, 2010), Международной конференции «Information and Telecommunication Technologies in Intelligent Systems» (Lugano, Schweiz, 2010), а также на научных семинарах кафедры вычислительной техники ЮЗГУ (ранее КурскГТУ) с 2008 по 2011 г.

Публикации по теме диссертации. Результаты диссертационной работы отражены в 9 публикациях, в числе которых 3 статьи, опубликованные в научных изданиях из Перечня ВАК, а также 1 свидетельство о Государственной регистрации программы для ЭВМ.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах личный вклад соискателя сводится к следующему: в [1] выполнен сравнительный анализ методов распределенной барьерной синхронизации в матричных системах, в [7] разработана процедура барьерной синхронизации с динамическим ограничением области распространения координирующих сигналов, в [3,8,47] сформулированы принципы обмена координирующими сигналами при реализации барьерной синхронизации, в [4] получена зависимость аппаратной сложности устройства синхронизации от параметров координирующей среды ОМК, в [2,6] предложен подход к снижению времени барьерной синхронизации при итеративных вычислениях за счет исключения не участвующих в синхронизации процессоров, в [5] разработаны наиболее важные сущности иерархии моделирующих агрегатов.

Объем и структура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 134 страницы текста (с учетом приложений) и поясняется 26 рисунками и 5 таблицами; список литературы включает 94 наименования.

Выводы

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

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

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

ЗАКЛЮЧЕНИЕ

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

В ходе решения этой задачи получены следующие основные результаты:

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

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

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

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

1. Аль-Хади, A.M. Методы распределенной барьерной синхронизации-параллельных процессов в матричных СБИС-системах Текст. / И.В: Зотов; C.B. Волобуев, А.М: Аль-Хади // Нейрокомпьютеры: разработка,.применение. 2009: №12.„С.„46-52.

2. Аль-Хади, A.M. Организация отказоустойчивого межпроцессорного* взаимодействия, в матричных мультикомпьютерах Текст. / А.Аль-Хади, И.В.Зотов [и др.] // Известия ТулГУ. Бизнес-процессы и бизнес-системы. Тула: ТулГУ, 2006. Вып.4. С. 3-9.

3. Аль-Хади, A.M. Программа имитационного моделирования матричных коммутаторов с отказоустойчивой маршрутизацией пакетов / A.M. Аль-Хади и др. // Свидетельство об официальной регистрации программы для ЭВМ№2009612576; заявл. 23.03.2009; per. 21.05.2009.

4. Аль-Хади, А.М. Распределенная процедура барьерной синхронизации; с динамическим ограничением? области- распространения; координирующих сигналов* Текст.! / А.М; Аль-Хади; С.'Ау Муратову ШВ\ Зотова // Телекоммуникации. 2011. №5. G. 2-7.

5. Антонов, A.C. Параллельное программирование: с использованием технологии ОрепМР Текст.: Учебное пособие. — М.: Изд-во МГУ, 2009. 77 с.

6. Волобуев, С.В. Распределенный; механизм барьерной; синхронизации, на основе параллельно-конвейерной координирующей среды Текст. / С.В: Волобуев, И.В. Зотов // Информационно-измерительные и управляющие системы. 2010. №7. С. 35-39.

7. Котов, В.Е. Сети Петри Текст. М.: Наука, Гл. ред. физ.-мат. л-ры, 1984.-160 с.

8. Кремер, Н.Ш: Теория вероятности и математическая статистика Текст.: Учеб. для вузов 3-е изд. перераб. и доп.* - М'.: «ЮНИТИДАНА», 2004. -573 с.

9. Мелехин, В'.Ф. Вычислительные машины, системы и сети Текст.: учебник для студ. высш: уч. заведений / В.Ф. Мелехин, Е.Г. Павловский. — 2-е изд. М.: «Академия», 2007. — 560 с.

10. Обзор продукции. Процессор Intel Хеоп серии 7500 Электронный ресурс. // Корпорация Intel, 2010. URL: http://cache-www.intel.com/cd/00/00/45/27/452706452706.pdf (дата обращения: 15.09.2010).

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

12. Патент №2005/0050374 А1 США, МКИ 8 G06F 12/00. Method for synchronizing processors in a multiprocessors system / T. Nakamura, N. Sukegawa (Япония). -№10/894064; заявлено 20.07.2004; опубл. 03.03.2005. 14 с.

13. Патент №2116665 РФ, МКИ 6 G06F9/22. Модуль мультимикропрограммной системы / И.В.Зотов, В.А.Колосков, В.С.Титов (РФ). -№97102631/09; заявлено 18.02.97; опубл. 27.07.98, Бюл. №21.-21 с.

14. Патент №2145434 РФ, МКИ 7 G05B19/18, G06F9/22. Модуль системы программного управления / И.В.Зотов (РФ). №98119803/09; заявлено 2.11.98; опубл. 10.02.2000, Бюл. №4. - 23 с.

15. Патент №2146064 РФ, МКИ 7 G05B19/18, G06F9/22. Устройство программного, управления / И.В:Зотов (РФ). — №99101272/09; заявлено 19.01.99; опубл. 27.02.2000, Бюл. №6. 18 с.

16. Патент №2152071 РФ, МКИ-7 G06F9/22; 9/28. Модуль системы, микропрограммного управления / И.В.Зотов (РФ). №99109080/09; заявлено 5.05.99; опубл. 27.06.2000; Бюл. №18. - 20 с.

17. Патент №2168198 РФ, МКИ 7 G05B19/05, G06F9/28. Микроконтроллерная сеть / И.В.Зотов (РФ). №99119676/09; заявлено 13.09.99; опубл. 27.05.2001, Бюл. №15. - 21 с.

18. Патент №2280887 РФ, МКИ 8 G05B19/18, G06F9/28. Микроконтроллерная сеть / А.А.Иванов, Дж.Н.Абдель-Джалил, И.В'.Зотов, С.В.Виноградов (РФ). №2005104065/09; заявлено 15.02.2005; опубл. 27.07.2006, Бюл. №21. - 26 с.

19. Патент №6085303 США, МКИ 7 G06F15/16. Serialized race-free virtual barrier network / G.Thorson, R.S.Passint, S.L.Scott (США). №972010; заявлено 17.11.97; опубл. 04.07.2000.-22 с.

20. Патент №6216174 В1 США, МКИ 7 G06F15/80. System and method for fast barrier synchronization / S.L. Scott, R.E. Kessler (США). №09/162673; заявлено 29.09.98; опубл. 10.04.2001. - 10 с.

21. Патент №6996812 В2 США, МКИ 8 G06F9/45. Software implementation of synchronous memory barrier / P.E. McKenney (США). — №09/884597; заявлено 18.06.2001; опубл. 7.02.2006. 11 с.

22. Патент №7444385 США, МКИ 9 G06F15/16. Global interrupt and.burner network / M.A. Blumrich; D. Chen; P.W. Coteus и др. (США). №10/468997; заявлено'25.02.02; опубл. 28.10:08. - 10 с.

23. Патент №7487501 В2 США, МКИ 9 G06F 9/46, 1/00: Distributed counter and centralized sensor- in barrier wait synchronization / R.E. Silvera, K.A. Stoodley, G. Zhang (США). №10/929165; заявлено 30.08.2004; опубл. 03.02.2009. - 7 с.

24. Патент №751295 IB 1 США, МКИ 9 G06F9/46. Barrier synchronization object for multi-threaded application / R. Marejca (США). — №10/641172; заявлено 14.08.03; опубл. 31.03.09. 13 с.

25. Патент №7770170 В2 США, МКИ 10 G06F 9/45, 9/46, 17/30, 13/00. Blocking local sense synchronization barrier / J. Rector, J.D. Morrison; N.M: Clift и др. (США). -№11/180338; заявлено 12.07.2005; опубл. 03.08.2010. 16 с.

26. Питерсон, Дж. Теория сетей Петри и моделирование систем Текст.: Пер. с англ. -М.: Мир, 1984. -264 с.

27. Процессоры AMD Электронный ресурс. // Advanced Micro Devices, Inc. URL: http://www.amd.com/ru/products/Pages/processors.aspx (дата обращения» : 15.09.2010).

28. Свидетельство о регистрации программы для ЭВМ №2006610308. Библиотека классов для имитационного моделирования коммуникационных сетей / Э.И.Ватутин, И.В.Зотов (РФ). М.: РосПатент; заявлено 22.10.2005; дата регистрации 16.01.2006.

29. Советов, Б.Я. Моделирование систем Текст.: учеб. пособие / БЛ.Советов, С.А.Яковлев. М.: Высшая школа, 2005. - 343 с.

30. Таненбаум Э. Современные операционные системы Текст. 2-е изд. - СПб.: Питер, 2002.- 1040 е.: ил.

31. Угрюмов, Е.П. Цифровая схемотехника Текст.: учеб. пособие / Е.П.Угрюмов. СПб.: БХВ-Петербург, 2004. - 800 с.

32. Эндрюс, Г.Р. Основы многопоточного; параллельного и распределенного программирования Текст.: Пер. с англ. — М.: Издательский дом «Вильяме», 2003: 512 с.

33. Якобовский, М'.В! Распределенные системы и сети Текст.: Учебное пособие. -М.: МГТУ "Станкин", 2000. 118 с.

34. An 8-core, 64-thread; 64-bit, power efficient SPARC SoC Электронный ресурс. // Sun Microsystems Inc., Niagara 2, ISSCC 2007 URL: http: //www.opensparc.net/pubs/preszo/07/n2isscc.pdf. (дата обращения: 15.09.2010).

35. Abellan, J.L. Efficient and» scalable barrier synchronization for many-core CMPs Текст. / J.L. Abellan, J. Fernandez, M.E. Acacio // Proceedings of the 7th ACM international conference on Computing frontiers, Bertinoro, Italy, 2010. P. 73-74.

36. Anderson, J. R. Simulation and Analysis of Barrier Synchronization Methods Текст. / J. R. Anderson // Technical Report No: HPPC-95-04, University of Minnesota, 1995. 42 p.

37. Brooks, E.D. The Butterfly Barrier Текст. / E.D. Brooks // International Journal of Parallel Programming. -1986.-Vol. 15, №4. P. 295-307.

38. Buntinas, D. Optimizing Synchronization Operations for Remote Memory Communication Systems Текст. / D. Buntinas, A. Saify, D.K. Panda и др. // International Parallel and Distributed Processing Symposium (IPDPS'03), 2003.

39. Cole, B. NEWS: 40-core processor with Forth-based IDE tools unveiled Электронный ресурс. // URL: http://www.eetimes.com/electronics-products/processors/4107362/NEWS-40-core-processor-with-Forth-based-IDE-tools-unveiled (дата обращения: 15.09.2010).

40. Delgado, M., A distributed barrier synchronization solution in hardware for 2D-mesh multicomputers Текст. / M. Delgado, S. Kofuji // Proc. 3rd Intl Conf. High Performance Computing, Dec. 19-22 1996. IEEE: 1996. -P: 368-373.

41. Dietz, H.G. A fine-grain parallel architecture based on barrier synchronization Текст. / H. G. Dietz, R. Hoare, T. Mattox // Intl. Conf. Parallel Processing, 1996. Vol. 1. - P.* 247-250.

42. Feldmann, A. Subset barrier synchronization on a-private-memory parallel system* Текст. / A. Feldmann, T. Gross, D. O'Hallaron и др. // Proc. ACM Symp. Parallel Algor. Architect. (SPAA92), San Diego, 29 June 1 July 1992. - ACM, 1992.-P. 209-218.

43. Goodman, J.R. Efficient Synchronization Primitives for Large-Scale Cache-Coherent Multiprocessors Текст. / J.R. Goodman, M.K. Vernon, P.J. Woest // ACM SIGARCH Computer Architecture News. 1989. - Vohl7, №2. - P. 64-75.

44. Gupta, R. High speed synchronization of processors using fuzzy barriers Текст. / R. Gupta, M. Epstein // International Journal of Parallel Programming. -1990.-Vol. 19, №1.

45. Hengsen, D. Two Algorithms for Barrier Synchronization Текст. / D. Hengsen, R. Finkel, U. Manber // International Journal of Parallel Programming. -1988. — Vol. 17, №1. P. 1-17.

46. Ноаге, R.R. ClusterNet: An Object-Oriented Cluster Network Текст. / R.R. Hoare // Proceedings of the 15 IPDPS 2000 Workshops on Parallel and Distributed Processing, May 01 05,2000. - P. 28-38.

47. Hoefler, T. A Survey of Barrier Algorithms for Coarse Grained Supercomputers Текст. / Т. Hoefler, Т. Mehlan, F. Mietke и др. // Chemnitzer Informatik Berichte. 2004. - Vol 04, №03.

48. Johnson, D. Low-cost, high-performance barrier synchronization, on networks of workstation Текст. / D. Johnson, D. Lilja, J. Reidl и др. // Journal of Parallel and Distributed Computing. 1997. - Vol. 40. - РГ131-137.

49. Johnson, T.A. Cyclical cascade chains: a dynamic barrier synchronization mechanism for multiprocessor systems Текст. / T.A.Johnson, R.R.Hoare // Proc.

50. EE Workshop Mass. Paral. Processing, Intl Paral. Distrib. Processing Symp. (IPDPS-01), San Francisco, 23-27 April 2001. Los Alamitos: IEEE Computer Society, 2001. - P. 2061-2068.

51. Jordan, H.F. A special purpose architecture for. finite element analysis Текст. / H.F. Jordan // International Conference on Parallel Processing, 1978. — P. 263-266.

52. Jung, II Two-phase barrier: a synchronization' primitive for improving the processor utilization Текст. / I. Jung, J. Hyun, J. Ma // International Journal of Parallel Programming. 2001. - Vol. 29, №6. - P. 607-627.

53. Kessler, R.E. Cray T3D: A new dimension for Cray Research Текст. / R. E. Kessler, J. L. Schwarzmeier // Proc. 38th IEEE Int. Computer Conf., 1993. P. 176-182.

54. Lin, X. Deadlock-Free Multicast Wormhole Routing in 2D Mesh Multicomputers Текст. / X. Lin, P.K. McKinley, L.M. Ni // IEEE Transactions on Parallel and Distributed Systems. 1994. - Vol. 5, № 8. - P. 793-804.

55. Mee, W.J. Synchronization techniques for distributed systems: an overview / W.J. Mee, G.S. Hura // Microelectron. Reliab. 1992. - Vol.32, №1/2. - P. 175197.

56. Mellor-Crummey, J.M. Algorithm for Scalable Synchronization on Shared-Memory Multiprocessors Текст . / J.M. Mellor-Crummey, M.L. Scott // ACM Trans. Computer Systems. 1991. - Vol. 9. - P. 21-65.

57. Moh, S. Four-ary tree-based barrier synchronization for 2d meshes without nonmember involvement Текст . / S.Moh, C.Yu, B.Lee и др. // IEEE Trans. Comput. 2001. - Vol.50, №8.- P. 811-823.

58. Monchiero, M. Efficient synchronization for embedded on-chip multiprocessors / M. Monchiero, G. Palermo, C. Silvano, O. Villa // IEEE

59. Transactions on very large scale integration (VLSI) systems — October 2006 — Vol. 14, №10.-P. 1049-1062.

60. MPI: The Complete Reference Электронный ресурс. // URL: http://rsusul .md.runnet.ru/ncube/mpi/mpibool'c/mpi-book.html (дата обращения 16.08.2009).

61. MPI: The Message Passing Interface Электронный* ресурс. // URL: http://parallel.ru/tech/techdev/mpi.html (дата обращения16.08.2009).

62. Panda, D.K. Fast Barrier Synchronization in Wormhole k-ary n-cube Networks Текст. / D.K. Panda // First IEEE Symposium on High Performance Computer Architecture, 1995.-P. 200-209.

63. Sampson, J. Fast synchronization for chip multiprocessors Текст. / J.Sampson, R.Gonzalez, J.-F.Collard и др. // SIGARCH Computer Architecture News.- 2005.- Vol.33, №4.- P. 64-69.

64. Sartori, J. Low-overhead, high-speed multi-core barrier synchronization Текст. / J. Sartori, R. Kumar // High Performance Embedded Architectures and Compilers, Lecture Notes in Computer Science, 2010. Vol. №5952. - P. 18-34.

65. Scott, S.L. Synchronization and Communication in the T3E Multiprocessor Текст . / S.L. Scott // Proc. of the 7th ASPLOS, 1996.

66. Sivaram, R. A reliable hardware barrier synchronization4 scheme Текст. / R.Sivaram, C.B.Stunkel, D.K.Panda // Proc. 11 Intl Parallel Processing Symp. (IPPS-97), Geneva, 1-5 April 1997. Los Alamitos: IEEE Computer Society, 1997. -P. 274-280:

67. TILE64™ Overview Электронный ресурс. // Tilera Corporation, 2010: URL: http://www.tilera.com/sites/default/files/productbriefs/PBO 10 TILE64ProcessorAv4.pdf (дата обращения: 15.09:2010).

68. TILE-Gx™ Overview Электронный ресурс. // Tilera Corporation; 2010. URL: htip://www.tilera.com/sites/default/files/productbriefs/PB025TILE-GxProcessorAv3.pdf (дата обращения: 15.09.2010).

69. TILEPro36™ Overview Электронный ресурс. // Tilera Corporation, 2010. URL: http://www.tilera.com/sites/default/files/productbriefs /PB020TILEPro36processorAv2.pdf (дата обращения: 15.09.2010).

70. TILEPro64™ Overview Электронный ресурс. //Tilera Corporation, 2010. URL: http://www.tilera.com/sites/default/files/productbriefs /PB019TILEPro64ProcessorAv3.pdf (дата обращения: 15.09.2010).

71. Tzeng, N.-F. Distributed1 Shared Memory Systems with Improved Barrier Synchronization and Data Transfer Текст. / N.-F. Tzeng, A. Kongrmmvattana // Proceedings of the 11th international conference on Supercomputing, Vienna, Austria, 1997.-P. 148-155.

72. Vega 3 Processors Электронный ресурс. // Azul Systems, 2010. URL: http://www.azulsystems.com/technology/vega (дата обращения: 15.09.2010).

73. Yang, J. S. Designing tree-based barrier synchronization on 2D mesh networks Текст. / J.S.Yang, C.T.King // IEEE Trans. Parallel Distrib. Systems. -1998. Vol.9, №6. - P. 526-533.

74. Yew, P.C. Distributing Hot Spot Addressingin Large Scale Multiprocessors Текст. / P.C. Yew, N.F. Tzeng, D.H. Lawrie // IEEE Transactions on Computers, 1987.-Vol.36, №4. P. 388-395.

75. Zhang, L. Highly Efficient Synchronization Based on Active Memory Operations Текст. / L. Zhang, Z. Fang, J. B. Carter // 18th International Parallel and Distributed Processing Symposium, 2004. — P. 58-68.

76. Исх.34/11 от « 8 » апреля 2011г.1. УТВЕРЖДАЮ

77. Данный акт не является основанием для финансовых расчетов.л*" ¿>с: л '

78. Технический директор ООО «Визор», * о ««■*' \ л "В

79. Коммерческий директор ООО «Визор» * /, Сараев А.Н.« —~— .—»--мов Н.Н.1. УТВЕРЖДАЮ1. АКТоб использовании результатов диссертационной работы Аль-Хади Абдулрахмана Мохаммеда Али

80. Начальник учебно-методического упра""о,тт*"к.т.н., доцент1. Романченко A.C.

81. Декан факультета ИВТ д.т.н., профессор1. Дегтярев C.B.1. Зам. зав. каф. ВТпо учебно-воспитательной работе к.т.п., доцент4 Чернецкая И.Е.