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

004613779

ВОЛОБУЕВ СЕРГЕЙ ВИКТОРОВИЧ

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

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

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

2 3 псН 2010

КУРСК - 2010

004618779

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

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

доктор технических наук, старший научный сотрудник. Николаев Виктор Николаевич

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

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

Атакищев Олег Игоревич

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

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

технологический университет им. В.Г.Шухова

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

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

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

Ученый секретарь совета по защите докторский и кандидатских диссертаций Д 212.105.02 / X Е.А.Титенко

у

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

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

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

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

Кардинальное снижение времени барьерной синхронизации обеспечивается путем включения в мультикомпьютер соответствующих средств аппаратной поддержки, что уже нашло отражение в архитектуре многих коммерческих систем (СМ-5, Cray T3D, Cray ТЗЕ, SGr 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 патента РФ на изобретение.

Личный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В опубликованных в соавторстве работах по теме диссертации личный вклад соискателя сводится к следующему: в [1,5] выполнен сравнительный анализ методов барьерной синхронизации, в [2,6] разработана процедура параллельно-конвейерной барьерной синхронизации, в [3] проведен анализ результатов моделирования, в [4,7] предложена структурно-функциональная схема модуля барьерного синхронизатора, в [11] разработаны схемы блоков управления барьерной синхронизацией, в [12ДЗ] предложены схемные решения блоков коммутационного модуля.

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

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

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

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

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

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

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

TBS -> min; CBS -> max; EBS < EBS, где TBS - среднее время синхронизации; Css - комбинаторная гибкость средств синхронизации; EBS - структурная сложность средств синхронизации (EBS - ее предельно допустимое значение). Время TBS определяется как средний интервал между моментом достижения барьера всеми процессами барьерной группы до момента активизации последнего из них. Величину CBS можно формально представить как отношение числа допустимых вариантов размещения синхронизируемых процессов в ОМК к общему числу таких вариантов (в пределе CBS =1). Величина EBS характеризует основные аспекты сложности средств синхронизации (аппаратная сложность WBS, коммуникационная сложность QBS, суммарное число операторов в составе системных утилит и т.п.).

Существенное снижение времени TBS возможно при реализации процедуры барьерной синхронизации на аппаратном уровне. Чаще всего аппаратная реализация сводится к аппаратной поддержке процедуры на уровне узловых коммутационных устройств (в них вводятся дополнительные барьерные регистры, ассоциативная память, и т.д.), при этом архитектура и протоколы коммуникационной среды не изменяются (гибридный подход). Такой подход обеспечивает высокую комбинаторную гибкость и приемлемую структурную сложность средств синхронизации (СBS ->1, EBS < Ешоднако порождает интенсивный поток служебных сообщений, который доходит до нескольких тысяч сообщений на один барьер для

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

Другой подход (аппаратный) предполагает реализацию процедуры синхронизации на основе специализированных барьерных процессоров и/или координирующих сред с особыми протоколами взаимодействия (при этом имеющаяся стандартная коммуникационная среда используется только для обмена данными). Для лучших на настоящий момент аппаратных решений TBS не превышает нескольких микросекунд. В то же время им свойственны жесткие ограничения на размещение синхронизируемых процессов (CBS <1), что затрудняет их применение в ОМК в соответствии со стандартом MPI. Кроме того, аппаратные процедуры синхронизации требуют введения большого числа дополнительных физических линий связи между процессорами ОМК в нарушение ограничения EBS < EBS.

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

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

Для описания процедуры синхронизации представим матричный ОМК в виде графа H =<М, U >, где M - множество вершин, соответствующее множеству однотипных процессорных элементов (ПЭ) - модулей, a U е M х M - множество дуг, отражающее связи между ПЭ. Для каждого ПЭ зададим составной порядковый номер вида (x1,x2,-,xd), х=1 ,Nt, i = l,d, где d - мерность мультикомпьютера (для топологии кольца d = 1, для двумерной матричной топологии d = 2 и т.д.), М, — число ПЭ в / -й мерности. Вершины графа H сопоставим множеству ПЭ так, что (т^х^х^т^+Ъх^х^еУ^Ъф^-^х, =l,Nni =1,с/; (m(x1,x2,..,xij),m(xvx2+l,..,xj))eu,x2 =l,(N2-l),xl =1,ЛГГ,/ = (1,3,..,^);

(т (л,, х,,.., х<1), т (х,, х2,.., хЛ +1)) е V, = 1, (ЛГ, -1), х, = 1, Ы,, / = 1, (с? -1), где т(х1,х2,..,ха) - ПЭ с порядковым номером •■,*</).

Разработанная процедура предполагает, что синхронизация параллельно выполняющихся участков (ветвей) программы и запуск ожидающих ПЭ базируется на формировании и циклическом распространении значений индикаторных функций (!) е {0,1} в множестве одноразрядных слоев синхронизации

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

(V*:, е к;,кг е к:'1 (,, до=1)&е? хп=1)) & а(ук, е к;; и к;;+1 ■. /?К0=о).

Другими словами в один момент времени активны только слои, входящие в две соседние группы, остальные находятся в режиме ожидания.

Каждому процессорному элементу сопоставим вектор соответствия

Ехох2.~,*</ = ^у*1,*2,■■,*</ (и),..,у*>->х* („)), устанавливающий зави-

симость между ПЭ и барьерами. Значение у*1'*1'"'*'1 (и} = 0, если ПЭ выполняет участок программы и, завершающийся в ;-м барьере, в противном случае уХ[,хг<- 'х* (и) = 1. Кроме этого для ПЭ введем признак завершения им участка программы с,5е (/). Если (/) = 0, то ПЭ еще не выполнил е-й участок программы, завершающийся Уу-м барьером, если же (/) = 1, то участок программы завершен.

На основании введенных признаков можно определить текущее состояние ПЭ как (г) = (,) у Значение индикаторной функции

для ^ -го барьера зависит от признаков состояний ПЭ (*) и равно

гМ)= & г?*-* (Л.

Для определения значения индикаторной функции Zs(t) на выходе каждого ПЭ введем обозначения большего и меньшего порядкового номера ПЭ. Будем считать, что один ПЭ имеет меньший порядковый номер, чем другой ПЭ, т'(х1,х'2,..,х(/) < т"(х'{,х2,..,х"а), если и только если

Аналогично будем считать, что один ПЭ имеет больший порядковый номер, чем другой ПЭ, т'(х'1,х'2,..,х'а) > т"(х^,х'2,..,х^), если и только если

(Ух'пх';,1 = \^:х]> х") & (Зх],х", ¡ =

Согласно разработанной процедуре процессы синхронизации и активизации для участков программы, относящихся к барьеру организуются в виде последовательности циклов распространения двоичных признаков в слое К5 е Кь. Каждый цикл включает два этапа: 1) опрос состояния 11Э, реализующих участки программы, завершающиеся в л-м барьере (множество ./(ул.)), и формирование

и

признака 2) активизация ПЭ, ожидающих завершения ¿'-го барьера (мно-

жество ¡•'(ул.)), и восстановление исходного значения У.х = 0.

Для первого этапа цикла распространения значение функции Zs{t) на выходе (х1,х2,..,хц)-го ПЭ определяется следующим образом:

\т(х1,хг,.,х'11)<т(х1,х1,..,х11)

Момент времени завершения всех участков барьера у5 задается условием

г,(1')=2*м*(г')=о-> 1.

Для второго этапа цикла распространения значение функции 2^(1) на выходе (х1,х2,..,х11)-го ПЭ определяется по следующей формуле:

(

7Х1Л

& '¿Х!"Х2'-Х" (!)

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

Формирование значения функции 2производится только при ?/5(/) = 1.

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

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

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

я-* моделирует выполнение процессором соответствующего участка программы, я1**^ ^ - запуск процессора по завершении барьера, л7^ ^ ^ и я^ ^ ^

- прохождение сигнала синхронизации через ячейку координирующей среды.

Соединив согласно топологии матричного ОМК подсети л (Кг) и

Л; Х2 _Л(КГ) получим соответственно две сети Петри: А'(КГ) и А"(КГ). При этом сеть А'(КГ) моделирует формирование признака завершения, а сеть А"(КГ) - передачу данного признака завершения и запуск ПЭ.

Рис. 1. а) подсеть Л'^.^ (Кг); б) подсеть Л^ ^ л (Кг) Соединенные между собой сети Л\КГ) и А"(КГ) формируют сеть А(КГ), моделирующую поведение отдельного слоя координирующей среды. Анализ достижимых маркировок сети А(КГ) показывает, что она является живой и безопасной. Условие срабатывания переходов было следующее: если ПЭ не выполняет ветвей из множества J(vr), то переход срабатывает сразу по изменению начальной маркировки сети, в противном случае - в момент завершения соответствующей ветви. Поскольку сформулированное условие не накладывает каких-либо ограничений на размещение ветвей множества J(vr) среди ПЭ, а живость и безопасность сети А(КГ) доказывает отсутствие тупиков во время синхронизации внутри одного слоя, то можно утверждать, что разработанная процедура инвариантна к способу расположения синхронизируемых процессов среди модулей ОМК.

Сеть Петри Л моделирует процесс скоординированного переключения групп слоев (рисунок 2).

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

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

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

Функциональная схема разработанного устройства представлена на рисунке 3. Она включает регистр 1 вектора соответствия, дешифраторы 2 и 3 номера барьера, группы элементов И 4.1-4.т и 5.1-5.т, триггер 6 конфигурации, элемент И 7, элементы ИЛИ 8, 15, 21, триггер 9, элементы задержки 10, 16, счетчики 11,12 и дешифраторы 13, 14 номера активной группы, группы 17.1 -17.р барьерных модулей, группы элементов ИЛИ 19.l-19.rn, 20.l-20.rn, одновибратор 22, дешифратор 51, группа 52.1-52.П элементов исключающего ИЛИ.

Функциональная схема группы барьерных модулей 17л представлена на рисунке 4 и содержит барьерные модули 18.l-18.rn. Барьерный модуль 18л включает элемент ИЛИ 23, элементы И 23,24,27,28, триггер 25, элемент И-НЕ 26.

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

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

Регистр 1 вектора соответствия служит для хранения текущего значения вектора соответствия ПЭ. Дешифраторы 2, 3 номера вершины синхронизации предназначены для приема от ПЭ номера барьера выполненного участка программы и номера барьера, по завершении которого произойдет запуск ПЭ, и активизации соответствующих барьерных модулей 17л. Группы элементов И 4.1-4.т, 5.1-5.Ш служат для организации распространения сигналов опроса состояния групп параллельных участков и сигналов запуска от соседних модулей. Регистр 6

конфигурации служит для хранения флагов ПЭ с номерами (1,1,..,1) и (Л^Л^,..,^). Элемент И 7, элементы ИЛИ 8, 15, триггер 9, элементы задержки 10 и 16 предназначены для выработки сигнала управления переключением групп барьерных модулей. Счетчики 11, 12 и дешифраторы 13, 14 номера активной группы служат для перебора номеров и активизации групп барьерных модулей. Группа барьерных модулей 17л служит для группировки однотипных барьерных модулей 180- Дешифратор 51 и группа элементов 52.1-52.П предназначены для динамической установки и сброса соответствующего бита в регистре 1.

Рис. 4. Группа барьерных модулей 17.i

Барьерный модуль 18.i предназначен для управления прохождением сигналов завершения групп параллельных участков и активизации ПЭ для одной из вершин синхронизации. Группы элементов ИЛИ 19.1 -19.т, 20.l-20.rn служат для формирования и выдачи сигналов опроса модулей и завершения барьера соответственно.

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

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

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

Г* = + + 20" + 2<d -2)'+

+24 р + 3(f log2p] + Г log2d1) + 21 ЭВ,

где [ ] - операция округления до целого в сторону увеличения, ¡V^o) ~ сложность дешифратора в зависимости от разрядности i его входа, d - мерность ОМК, п -число слоев синхронизации, р - число барьерных групп, т - число слоев в одной группе. Так, аппаратная сложность устройства при п < 128 составляет порядка 0.1 -5 тыс. ЭВ, а для п <256 не превышает 10 тыс., что соизмеримо со сложностью прототипа [A.A. Иванов, параллельно-последовательный барьерный синхронизатор (ГТПБС)].

Рис. 5. Схема соединения модулей барьерной синхронизации на примере матричного ОМК в конфигурации 4x4 ПЭ Разрядность каналов связи модуля барьерного синхронизатора, использующихся для соединения с соседними, равно QBS = m(2d + 2) + 4. Таким образом, в отличие от аналогичных аппаратных решений (для ППБС QBS = 1п, для [М.Х.Т. Delgado, H.D. Dietz] QBS =4ti), отсутствует прямая зависимость числа линий связи от количества слоев синхронизации (параллельных барьеров), что уменьшает требования к площади кристалла и числу выводов СБИС. Естественное увеличение количества связей внутри модуля распределенного синхронизатора не оказывает большого влияния, поскольку длина межмодульных линий связи значительно превышает длину внутримодульных связей.

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

Максимальное время синхронизации 7^,ах равно

'BS

(d

{2 + \log2p-}) £(AW) + 1 v/=l

+ 8

(p+2) + \log2n~} + H

l3B '

где ¡зв - задержка ЭВ.

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

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

Для упрощения имитационной модели мощность множеств ./(vj и F(vs)

устанавливалась одинаковой, т.е. |>/(vJ)| = |ir(v!)j=&(vJ), где Sz(vs) - размер барьера. В зависимости от задачи моделирования и числа процессоров ОМК размер барьера Ss(v,) варьировался в диапазоне от 5 до NxN. Количество одновременно синхронизируемых (параллельных) барьеров устанавливалось максимально возможным и равнялось числу барьерных слоев п. Время выполнения участков программы задавалось случайно в диапазоне от до 87}™?х. Среднее время синхронизации TBS определялось как выборочное среднее при доверительной вероятности 0.95 и ошибкой малой выборки не более 0.2 от выборочного среднего.

На рисунке 6 представлены результаты моделирования зависимости времени Тт от количества параллельных барьеров п. Моделирование проводилось при р = 2 и |У(у,)| = |F(v5)| = 5. Согласно графику время TBS не зависит от п.

^BS'he

400 320 240 160 80 0

0 10 20 30 40 50 60 70 80 п Рис. 6. Зависимость времени TBS от количества параллельных барьеров п

На рисунке 7 показан график зависимости времени TBS от размера барьера Sz(vs) при п = р- 2. Разница между минимальным и максимальным значениями для N = 16 составляет =17%, а для N = 24 - =10%. Данные значения обусловлены расположением участвующих в синхронизации процессов среди ПЭ ОМК. Максимальная задержка достигается при Sz(vs) = N2.

ТBs'hs 480

400

320

240

160

80

0

0 50 100 150 200 250 300 350 400 450 500 550 600 Рис. 7. Зависимость времени TBS от размера барьера &(vs)

.......... S—

—♦—N=16 1-—•—N=24 |-

На рисунке 8 представлены результаты моделирования среднего времени TBS от числа процессоров N2 ОМК. При этом р = 4, п = 8, для исключения влияния размера барьера на результаты Sz(vs) = 0.9N2 /п. Согласно полученным данным зависимость времени TBS в асимптотике равна О (Л'). Так при jV =14 Tns ~ 1Д7 мкс, а при N = 28 TBS я 2,4 мкс (l3ß ~ 3 не). Для сравнения на рисунке 8 показана зависимость времени TBS аналогичных распределенных устройств барьерной синхронизации [М.Х.Т. Delgado, S.T. Kofuji], ППБС. Значения времени TBS известных процедур синхронизации следующее: [S. Moh, С. Yu, В. Lee и др.] - для системы 32х 32 TBS я 3 мкс, [J.-S. Yang, С.-Т. King] - для системы 32 х 32 TBS я 5 мкс.

2500 2000 1500 1000 500 О

О 100 200 300 400 500 600 700 800 900 Л'2 Рис. 8. Зависимость времени Тв5 от числа процессоров Л'2 ОМК

Таким образом, полученные значения времени синхронизации Тв$ для разработанного устройства соизмеримы с известными аппаратными решениями.

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

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

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

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

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

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

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

М.Х.Т. Delgado, S.T. Kofuji -х-ППБС

Разработанное устройство

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

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

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

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

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

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

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

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

Статьи

4. Волобуев, C.B. Параллельно-конвейерный барьерный синхронизатор, совместимый со стандартом программирования MPI [Текст] / C.B. Волобуев, В.Н. Николаев // Научно-технический сборник. Изд-во «Курский НИИ» МО РФ, 2010. №75(3). С. 18-24.

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

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

6. Волобуев, C.B. Распределенная коммуникационная среда барьерной синхронизации [Текст] / C.B. Волобуев, И.В. Зотов // Методы и алгоритмы прикладной математики в технике, медицине и экономике: материалы VII Международной научно-практической конференции, Новочеркасск, 2007 г.: В 2 ч. Новочеркасск: ЮРГТУ, 2007. Ч. I. С. 69-70.

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

8. Волобуев, C.B. Имитационное моделирование процедуры параллельно-конвейерной барьерной синхронизации [Текст] / C.B. Волобуев // Интеллектуальные и информационные системы: материалы Всероссийской научно-технической конференции, Тула, 2009г. Тула: Тульский государственный университет, 2009. С. 40-41.

9. Волобуев, C.B. Математическая модель параллельно-конвейерной барьерной синхронизации на основе аппарата сетей Петри [Текст] / C.B. Волобуев // Методы и алгоритмы прикладной математики в технике, медицине и экономике: материалы X Международной научно-практической конференции, Новочеркасск, 2010 г. Новочеркасск: ЮРГТУ, 2010. С. 105-107.

10. Волобуев, C.B. Выбор параметров параллельно-конвейерного барьерного синхронизатора с учетом заданных ограничений многопроцессорной системы [Текст] / C.B. Волобуев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы IX международной конференции, Курск, 2010 г. Курск: КурскГТУ, 2010. С. 162-164.

Патенты на изобретение

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

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

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

Соискатель С. В. Волобуев

Подписано в печать 24.11.10. Формат 60x84 1/16. Усл. печ. л. 1,0. Тираж 120 экз. Закат 1042. Издательство Юго-Западного государственного университета

305040, г. Курск, ул. 50 лет Октября, 94 Отпечатано: ПБОЮЛ Киселева О.В. (ОГРН 304463202600213)

ВВЕДЕНИЕ

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 тыс. эквивалентных двухвходовых вентилей на процессор для всех практически значимых случаев, что позволяет сохранить приемлемую сложность СБИС ОМК. Получены аналитические и экспериментальные зависимости времени синхронизации при использовании разработанного устройства в качестве модуля координирующей среды ОМК, показывающие линейный рост указанного времени от диаметра мультикомпьютера.

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.