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

• Аль-Хади Абдулрахман Мохаммед Али
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Аль-Хади Абдулрахман Мохаммед Али

ВВЕДЕНИЕ

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 раза.

Список литературы диссертационного исследования кандидат технических наук Аль-Хади Абдулрахман Мохаммед Али, 2011 год

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 Чернецкая И.Е.