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

• Волобуев, Сергей Викторович
• кандидат технических наук
• 2010

Оглавление диссертации кандидат технических наук Волобуев, Сергей Викторович

ВВЕДЕНИЕ

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

1.1. Многопроцессорные системы на кристалле

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

1.3. Методы барьерной синхронизации

1.3.1 Программные методы барьерной синхронизации

1.3.2 Программно-аппаратные (гибридные) методы барьерной синхронизации

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

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

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

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

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

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

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

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

3.3. Функционирование барьерного синхронизатора согласно стандарту \ MPI

3.4. Оценка структурной сложности параллельно-конвейерного барьерного синхронизатора

3.4.1. Оценка аппаратной сложности

3.4.2. Оценка коммуникационной сложности 85 Выводы

4. ОЦЕНКА БЫСТРОДЕЙСТВИЯ ПАРАЛЛЕЛЬНО-КОНВЕЙЕРНОЙ

ПРОЦЕДУРЫ И УСТРОЙСТВА СИНХРОНИЗАЦИИ

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

4.2. Определение параметров параллельно-конвейерного барьерного синхронизатора с учетом заданных ограничений ОМК

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

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

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

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

Введение диссертации (часть автореферата) на тему «Параллельно-конвейерная процедура и устройство распределенной барьерной синхронизации матричных СБИС-мультикомпьютеров»

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

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

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

Кардинальное снижение времени барьерной синхронизации обеспечивается путем включения в мультикомпьютер соответствующих средств аппаратной поддержки, что уже нашло отражение в архитектуре многих коммерческих систем (СМ-5, Cray T3D, Cray ТЗЕ, SGI Origin 3000, IBM SP-2, IBM Blue Gene и др.). В настоящее время существует два подхода к организации аппаратной поддержки процедуры барьерной синхронизации. Первый из них (гибридный) базируется на стандартных коммуникационных протоколах мультикомпьютера и предусматривает незначительные схемные модификации на уровне узловых коммутационных устройств. Второй подход (аппаратный) предполагает использование специализированных барьерных процессоров и/или координирующих сред в дополнение к имеющейся коммуникационной сети. В рамках этих подходов разработаны различные процедуры барьерной синхронизации (гибридные и аппаратные), определяющие порядок взаимодействия синхронизируемых процессов, синтезированы схемы соответствующих коммуникационных устройств и сред (М.Х.Т. Delgado, H.D. Dietz, R. Hoare, T.A. Johnson, C.-T. King, S.T. Kofuji, P.K. McKinley, L.M. Ni, D.K. Panda, I.D. Scherson, H. Xu, J.-S. Yang и др.).

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

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

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

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

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

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

Работа выполнена в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» (мероприятие 1.1), государственный контракт №14.740.11.0090, при поддержке гранта Президента РФ МД-685.2009.8, а также в соответствии с планом НИР КурскГТУ по единому заказ-наряду Министерства образования и науки РФ в 2007-2010 годах.

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

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

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

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

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

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

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

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

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

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

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

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

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

Праюпическая ценность работы:

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

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

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

Результаты диссертационного исследования доведены до уровня функциональных схем, защищенных патентами РФ на изобретение (№№2336553, 2359320, 2360283), и пригодны для дальнейшей технологической проработки.

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертационной работы были заслушаны и получили одобрение на VII Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (г. Новочеркасск, 2007), IV Международной конференции «Параллельные вычисления и задачи управления» РАСО'08 (г. Москва, 2008), Всероссийской научно-технической конференции «Интеллектуальные и информационные системы» (г. Тула, 2009), X Международной научно-практической конференции «Методы и алгоритмы прикладной математики в технике, медицине и экономике» (г. Новочеркасск, 2010), IX Международной научно-технической конференции «Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации» (г. Курск, 2010), а также на научных семинарах кафедры вычислительной техники ЮЗГУ (ранее КурскГТУ) с 2006 по 2010 г.

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

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [4,13] выполнен сравнительный анализ методов барьерной синхронизации, в [11,12] разработана процедура параллельно-конвейерной барьерной синхронизации, в [10] проведен анализ результатов моделирования, в [8,9] предложена структурно-функциональная схема модуля барьерного синхронизатора, в [26] разработаны схемы блоков управления барьерной синхронизацией, в [27,28] предложены схемные решения блоков коммутационного модуля.

Объем и струшпура работы. Диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений. Работа содержит 151 страницу текста (с учетом приложений) и поясняется 31 рисунком и 9 таблицами; список литературы включает 114 наименований.

Заключение диссертации по теме «Элементы и устройства вычислительной техники и систем управления», Волобуев, Сергей Викторович

Выводы

1. Сравнительный анализ быстродействия разработанного устройства с существующими аппаратными решениями позволил установить, что время синхронизации предложенного устройства соизмеримо с аналогичными решениями и составляет порядка нескольких микросекунд («4.7мкс при Ы2 = 32, р = 4, =3нс).

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Волобуев, Сергей Викторович, 2010 год

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

2. Букатов, A.A., Программирование многопроцессорных вычислительных систем Текст. / A.A. Букатов, В.Н. Дацюк, А.И. Жегуло. -Ростов-на-Дону: Изд-во ОО «ЦВВР», 2003. 208 с.

3. Воеводин, В.В. Параллельные вычисления Текст. / В.В. Воеводин, Вл.В. Воеводин. СПБ.: БХВ-Петербург, 2002. - 608 е.: ил.

4. Волобуев, C.B. Анализ средств барьерной синхронизации / C.B. Волобуев, В.Н. Николаев // Молодой ученый. 2010. №11. С. 50-52.

5. Волобуев, C.B. Организация параллельно-конвейерной барьерной синхронизации в матричных многопроцессорных системах на основе распределенной координирующей среды Текст. / C.B. Волобуев, И.В. Зотов //

6. Параллельные вычисления и задачи управления (РАСО'08): труды IV международной конференции, Москва, 2008 г. Москва: Институт проблем управления им. В.А. Трапезникова РАН, 2008. С. 616-642.

7. Волобуев, C.B. Параллельно-конвейерный барьерный синхронизатор, совместимый со стандартом программирования MPI Текст. / C.B. Волобуев,

8. B.Н. Николаев // Научно-технический сборник. Изд-во «Курский НИИ» МО РФ, 2010. №75(3). С. 18-24.

9. Волобуев, C.B. Процедура распределенной параллельно-конвейерной барьерной синхронизации, инвариантная к способу размещения синхронизируемых процессов Текст. / C.B. Волобуев, И.В. Зотов // Известия ВУЗов: Приборостроение. 2010. №10. С. 29-34.

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

11. Зотов, И.В. Методы распределенной барьерной синхронизации параллельных процессов в матричных СБИС-системах Текст. / И.В. Зотов,

12. C.B. Волобуев, A.M. Аль-Хади // Нейрокомпьютеры: разработка, применение. 2009. №12. С. 46-52.

13. Зотов, И.В. Модель синхронизации параллельных управляющих процессов в микроконтроллерных сетях с матричной организацией Текст. / И.В.Зотов // Автоматика и вычислительная техника. 2001. №3. С. 44-55.

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

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

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

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

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

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

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

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

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

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

24. Патент №2280887 РФ, МКИ 8 G05B19/18, G06F9/28. Микроконтроллерная сеть / А.А.Иванов, Дж.Н.Абдель-Джалил, И.В.Зотов,

25. С.В.Виноградов (РФ). №2005104065/09; заявлено 15.02.2005; опубл. 27.07.2006, Бюл. №21. - 26 с.

26. Патент №2336553 РФ, МКИ 9 G06F9/28, G06F15/173, G06F1/10. Микроконтроллерная сеть / С.В.Волобуев и др. (РФ). №2007114559; заявлено 17.04.2007; опубл. 20.10.2008, Бюл. №29. - 15 с.

27. Патент №2359320 РФ, МКИ 9 G06F15/163. Модуль для организации обмена сообщениями / И.В.Зотов, Д.Н. Абдель-Джалиль, С.В.Волобуев и др. (РФ). №2007123995/09; заявлено 27.06.2007; опубл. 20.06.2009, Бюл. №17.

28. Патент №2360283 РФ, МКИ 9 G06F15/163, Н03К17/00. Коммутационный модуль с параллельно-конвейерной обработкой и вещанием сообщений / О.В.Крикунов, М.Х.Наджаджра, С.В.Волобуев и др. (РФ). -№2007130934/09; заявлено 13.08.2007; опубл. 27.06.2009, Бюл. №18.

29. Патент №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 с.

30. Патент №2010/0095090 А1 США, МКИ 10 G06F 15/76, 9/02, 12/08. Barrier synchronization method, device and multi-core processor. / H. UNNO, M. Ukai, M. Depetro (США). -№12/638746; заявлено 15.12.2009; опубл. 15.04.2010. -18 c.

31. Патент №2010/0124241 A1 США, МКИ 10 H04G 3/06. Barrier synchronization apparatus, barrier synchronization system and barrier synchronization method / S. Hiramoto, Y. Ajima, T. Inoue (Япония). №12/582119; заявлено 20.10.2009; опубл. 20.05.2010. - 39 с.

32. Патент №5434995 США, МКИ 6 G06F15/16, 15/80. Barrier synchronization for distributed memory massively parallel processing systems / S.M.Oberlin, E.C.Fromm (США). №165265; заявлено 10.12.93; опубл. 18.07.95. -25 с.

33. Патент №5721921 США, МКИ 6 G06F13/38, 15/16. Barrier and eureka synchronization architecture for multiprocessors / R.E. Kessler, S.M. Oberlin, G.M. Thorson (США). -№450251; заявлено 25.05.95; опубл. 24.02.98. 37 с.

34. Патент №5765009 США, МКИ6 G06F15/16. Barrier synchronization system in parallel data processing / K. Ishizaka (США). №779493; заявлено 08.01.97; опубл. 09.06.98. - 43 с.

35. Патент №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 с.

36. Патент №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 с.

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

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

39. Патент №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 с.

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

41. Патент №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 с.

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

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

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

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

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

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

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

49. 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.

50. 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. (дата обращения: 13.06.2010)

51. 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.

52. Bai, S. Barrier Synchronization for CELL Multi-Processor Architecture Текст. / S. Bai, Q. Zhou, R. Zhou и др. // Ubi-Media Computing, Lanzhou, 31 July 2008-1 Aug. 2008.-P. 155-158.

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

54. 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.

55. Chen, X. Supporting Efficient Synchronization in Multi-core NoCs Using Dynamic Buffer Allocation Technique Текст. / X. Chen, Z. Li, A. Jantsch и др. // Proceedings of the 2010 IEEE Annual Symposium on VLSI. 2010. - P. 462-463.

56. Cohen, W.E. An optical bus-based distributed dynamic barrier mechanism Текст. / W.E.Cohen, D.W.Hyde, R.K.Gaede // IEEE Trans. Comput. 2000. -Vol.49, №12. P. 1354-1365.

57. 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.06.2010).

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

59. 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.

60. Duarte, M.E.M. Networks on Chip (NOC): Design Challenges Текст. / M.E.M. Duarte // 4th Internal Conference on Computer Architecture (ICCA'03), 2003.-P. 121-128.

61. 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.

62. Ghose, К. Efficient synchronization schemas for large-scale shared-memory multiprocessors Текст. / К. Ghose, D.-C. Cheng // International Conference on Parallel Processing, 1991.-P. 153-158.

63. 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. - Vol.17, №2. - P. 64-75.

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

65. Hoare, 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.

66. 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.

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

68. 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. - P. 131-137.

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

70. Jung, I. 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.

71. Karlin, A.R. Empirical studies of competitive spinning for a shared-memory multiprocessor Текст. / A.R. Karlin, K. Li, M.S. Manasse и др. // In Proceedings of the 13th ACM Symposium on Operating Systems Principles, 1991. P. 41-55.

72. 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.

73. Kontothanassis, L. Using Scheduler Information to Achieve Optimal Barrier Synchronization Performance Текст. / L. Kontothanassis, R.W. Wisniewski // ACM SIGPLAN Notices. 1993. - Vol.28, №7. - P. 64-72.

74. LaMarca, A.A Performance Evaluation of Lock-Free Synchronization Protocols Текст. / A. LaMarca // Proceedings of the 13 annual ACM symposium on Principles of distributed computing, Los Angeles, California, United States, 1994. -P. 130-140.

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

76. Loh, G. 3D Stacked Microprocessor: Are We There Yet? Текст. / G. Loh, Y. Xie // IEEE Micro. May-June 2010. - Vol.30, № 3. p.60-64.

77. Lundsorm, S.F. A controllable mimd architecture Текст. / S.F. Lundsorm, G.H. Barnes // International Conference on Parallel Processing, 1980. P. 19-27.

78. 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.

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

80. Monchiero, M. Efficient synchronization for embedded on-chip multiprocessors / M. Monchiero, G. Palermo, C. Silvano, O. Villa // IEEE Transactions on very large scale integration (VLSI) systems.- October 2006 — Vol. 14, №10.-P. 1049-1062.

81. MPI: The Complete Reference Электронный ресурс. // URL: http://rsusul .rnd.runnet.ru/ncube/mpi/mpibook/mpi-book.html (дата обращения 12.02.2009).

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

83. O'Boyle, M. Compile time barrier synchronization minimization Текст. / M.O'Boyle, E.Stohr // IEEE Trans. Parallel Distrib. Systems. 2002. - Vol.13, №6. -P. 529-543.

84. O'Keefe, M. Hardware barrier synchronization: Dynamic barrier MIMD (DBM) Текст. / M. O'Keefe, H. Dietz // ICPP Proceedings, 1990. -Vol. 1.- P. 43-46.

85. O'Keefe, M. Hardware barrier synchronization: Static barrier MIMD (SBM) Текст. / M. O'Keefe, H. Dietz // ICPP Proceedings, I990.-Vol. 1.- P. 35-42.

86. Olnowich, H.T. ALLNODE Barrier Synchronization Network Текст. / H.T. Olnowich // Proceedings of the 9th International Symposium on Parallel Processing, 25-28 April 1995. -P.265-269.

87. 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.

88. Propeller General Information Электронный ресурс. // URL: http://www.parallax.com/propeller/Index.html (дата обращения 12.09.2010).

89. 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.

90. 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.

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

92. Sivaram, R. A reliable hardware barrier synchronization 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.

93. Sun, C. Three-dimensional multiprocessor system-on-chip thermal optimization Текст. / С. Sun, L. Chang, R.P. Dick // 5th IEEE/ACM international conference on hardware/software codesign and system synthesis. 30 September -3 October, 2007. P. 117-122.

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

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

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

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

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

99. Tzeng, N.-F. Efficient Barrier Synchronization on Wireless Computing Systems Текст. / N.-F. Tzeng, B. Kasula, H. Wu // 11th International Conference on Parallel and Distributed Systems (ICPADS*05), 20-22 July 2005. Vol. 1. - P. 782788.

100. Vangal, S. An 80-tile 1.28TFLOPS network-on-chip in 65nm CMOS Текст. / S. Vangal, J. Howard, G. Ruhl и др. // In Procs. of 2007 Intl. Solid-State Circuit Conf., 2007. P. 98-589.

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

102. XLR700 Processor Электронный ресурс. // URL: http://www.netlogicmicro.com/Products/ProductBriefs/MultiCore/XLR700.htm (дата обращения: 10.04.2010).

103. 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.

104. 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.

105. 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.

106. Zhao, J. Cost-Aware Three-Dimensional (3D) Many-Core Multiprocessor Design Текст. / J. Zhao, X. Dong, Y. Xie // Proceedings of Design Automation Conference (DAC). 2010. P. 126-131.

107. Zotov, I.V. Distributed Virtual Bit-Slice Synchronizer: A Scalable Hardware Barrier Mechanism for n-Dimensional Meshes Текст. / I.V. Zotov // IEEE Trans. Comput. 2010. - Vol.59, №9. - P. 1187-1199.