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

ИВАНОВ АЛЕКСАНДР АЛЕКСАНДРОВИЧ

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

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

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

КУРСК-2005

Работа выполнена на кафедре «Вычислительная техника» Курского государственного технического университета

Научный руководитель: доктор технических наук, профессор

Титов В.С.

Официальные оппоненты: доктор технических наук, профессор

Атакищев О. И. кандидат технических наук Беляев Ю.В.

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

Защита состоится 28 декабря 2005 г. в ^ часов на заседании диссертационного совета Д212.105.02 при Курском государственном техническом университете по адресу: 305040, Курск, ул. 50 лет Октября, 94 (конференц-зал).

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

Автореферат разослан «¿<Р» УУ 2005 г.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 305040, Курск, ул. 50 лет Октября, 94, КГТУ, ученому секретарю диссертационного совета Д212.105.02.

Ученый секретарь диссертационного совета кандидат техн. наук, доцент

►Титенко Е.А.

<2. BSm

2255176

3

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

Актуальность работы. Одним из перспективных архитектурных подклассов параллельных вычислительных систем (ВС) являются мультикомпьютеры с распределенной памятью (МРР-системы). Отличительная особенность таких систем - разделение физической памяти между процессорами (модулями) и организация их взаимодействия через коммуникационную сеть. Примерами подобных МРР-систем являются Cray ТЗЕ и 0rigin2000.

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

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

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

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

В настоящее время известно широкое разнообразие подходов к барьерной синхронизации в МРР-системах (J. R. Anderson, Т. A. Johnson, R. R. Hoare, Т. Muhammad и др.). Разработаны многочисленные варианты их реализации, как программные, так и аппаратные. При этом наиболее широко представлены решения программного уровня (Dissemination barrier, Butterfly barrier, Tree-based barriers и др.). Аппаратные решения, обладающие значительно большим быстродействием, пока не получили широкого распространения (DBM, Cyclical Cascade Barrier, СМ-5 Barrier Control Network и др.). Известные аппаратные решения носят, как правило, централизованный характер и не являются распределенными (DBM, Cyclical Cascade Barrier), что ограничивает возможность включения в систему новых процессоров (усложняет наращивание системы).

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

Работа выполнена при поддержке гранта Министерства образования РФ «Столетовские гранты-2003», а также в рамках совместных работ с ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2005 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

синхронизации и распределенных устрс

[и на ее основе.

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

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

2. Разработка распределенной децентрализованной аппаратно-ориентированной процедуры барьерной синхронизации.

3. Доказательство корректности разработанной процедуры на основе аппарата сетей Петри.

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

Методы исследования. При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных на кафедре ВТ КурскГТУ под руководством доц. Зотова И.В.

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

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

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

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

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

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

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

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

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

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

Техническое решение устройства синхронизации в МРР-системе выполнено на уровне иЬвбрстсния (патент № 2249849).

I м ■ '

Реализация и внедрение.

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

Апробация работы.

Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавание-2003» (г. Курск, 2003), НТК «Образование, наука, производство» (г. Белгород, 2004), НТК «КЛИН-2004» (г. Ульяновск, 2004).

Публикации.

Результаты диссертационной работы отражены в 5 публикациях, в числе которых 1 статья и I патент на изобретение.

В работах, опубликованных в соавторстве, лично соискателем предложены: в [1, 2] - алгоритм организации взаимодействия распределенных устройств синхронизации, [3] - распределенная децентрализованная аппаратно-ориентироваиная процедура барьерной синхронизации, [5] - структурно-функциональная организация распределенной системы барьерной синхронизации, в том числе узлового блока управления синхронизацией.

На защиту выносятся:

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

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

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

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

Объем и структура работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 131 страницу текста и поясняется 21 рисунком и 2 таблицами; список литературы включает 60 наименований; приложения содержат 40 страниц.

Области возможного использования.

Результаты диссертационной работы могут быть непосредственно использованы в коммерческих МРР-системах с матричной топологией (системы Cray, Intel, Thinking Machines). Кроме того, возможно их применение в специализированных параллельных системах, например, в параллельных

логических контроллерах, а также во встраиваемых микропроцессорных системах управления нижнего уровня иерархии АСУТП.

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

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

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

При построении МРР-систем особо значима разработка процедур координации параллельных вычислительных процессов. Их эффективность существенно влияет на многие важные характеристики системы, включая производительность, аппаратно-программную сложность и гибкость. Одной из важных задач координации является барьерная синхронизация. Цель ее решения -согласование моментов активизации определенных групп процессов с моментами завершения других групп процессов. Необходимость подобного согласнования возникает как в задачах с так называемым «мелкозернистым» (fine-grain) параллелизмом, так и в задачах, допускающих выделение крупных слабосвязанных фрагментов (coarse-grain). Например, весьма часто оно требуется при осуществлении матричных вычислений.

Представленные на настоящий момент решения задачи барьерной синхронизации реализуются преимущественно программно (Dissemination barrier, Butterfly barrier, Tree-based barriers и др.), что обеспечивает гибкость средств синхронизации, яо резко снижает быстродействие системы. Альтернативные им аппаратные решения (DBM, Cyclical Cascade Barrier, СМ-5 Barrier Control Network и др.) обладают весьма высоким быстродействием (один акт синхронизации за десятки микросекунд), однако характеризуются пониженной гибкостью. В частности, они носят централизованный характер и не являются распределенными (DBM, Cyclical Cascade Barrier). А это ограничивает возможность включения в систему новых процессоров (усложняет наращивание системы) и снижает ее потенциал для перспективных применений.

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

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

МРР-систему будем представлять топологической моделью в виде графа H=<M,U>, множество вершин М которого соответствует множеству процессоров, а множество дуг UcMxM отражает межпроцессорные связи. Вершины графа Н

отобразим на множество элементов гипотетической матрицы Я*, включающей Л^ строк и N2 столбцов, N^N2, М>1, так, что

(тц,т,ь+1))с (/,/ = = 1; {та,)е и, г = 1,ЛГ, -1,] = 1,Ы2\

(«ЛГл»'тп )6 ' =!»^; . ■«и )е У = 1.^2.

где т,,е£/ - процессор, расположенный на пересечении /-й строки и у'-го столбца матрицы

Я', /' = 1, ЛГ,, 7 -1, . Систему, представленную описанным способом, обозначим как

Система А^ реализует некоторое множество профамм У={ПЦ}. Далее, не нарушая общности, условимся рассматривать одну из программ множества Ч*, например, П„, однако действие всех положений будем распространять на любую программу из ЧЛ Предположим, что программа П„ представлена в виде параллельной граф-схемы С„ с множеством операторных и условных вершин К„ и с множеством дуг ЕиСУ,,*. Уи, при этом на множестве Уи определены отношения следования ц связи <р, альтернативы у/ и параллельности т. Введем понятие ветви программы.

Определение 1. Под ветвью будем понимать любое максимальное по включению подмножество вершин В, = |аЛ ,а1г.....а^ ]сг Уи такое, что

(К><\„)б£,„с = 1,?- 1)Л{Уа1с еВ„с = 1,д-1: {а1с,ак)е£„=>* =

В граф-схеме выделим множество ветвей Д, = \В1>В2,...,В^\.

Определение 2. Ветви Ва,ВреО„ будем считать параллельными, если и только если Ва, ахеВр\ а]СМК.

Зададим пару отображений (%„ : У„ —> М, х*„ : Ц, -> А/) так, чтобы выполнялось условие

^а/,ае<=Уи,а/б)а);: ^Ц-)*

Каждую ветвь Д^Д,, для которой ^ > 1, разобьем на подмножества

(подветви) сД, так, что

(Уау.а, е Вгх,ге{1,2,...,р,},(ах,а/)еЕы: %(а/)= х(ае))л

лЦ, е в;,а, е в;,((ле,аА)е 5>((в4,а,)е х(а„)).

В дальнейшем ветвями условимся называть собственно ветви ВсеД, такие, что = 1, а также подветви В[ ветвей В,еД, таких, что

Множество ветвей программы О,, обозначим как О* и распространим область определения отображения х',, на множество Б'и.

На множестве £)* определим отношение непосредственного предшествования еи с; О* х Ц*. Будем говорить, что ветвь Ва непосредственно

s

предшествует ветви Bp, т.е. Вае„Вр, если и только если 3а^еВа, ageBp: (а^ая)&Е„. Определение 3. Всякое максимальное по включению подмножество попарно параллельных ветвей J с D* такое, что VB„eJ: ВаЕ„Вр, Вр<= D*U\J, будем называть множеством синхронизации, или ./-множеством.

Определение 4. Всякое максимальное по включению подмножество попарно параллельных ветвей F с D'u такое, что VBaeF, BpeJ: Bps„Ba, где J- некоторое J-множество, назовем множеством распараллеливания для./, или F-множеством.

Каждой паре множеств {FJ) соответствует вершина синхронизации и / или распараллеливания (далее - барьер). Пусть at — некоторый барьер. Тогда соответствующее ему J-множество ветвей обозначим через J{ai), а F-множество -через F\ai). Множество барьеров в программе П„ обозначим как Уи.

Процедуру синхронизации будем задавать парой S=(L,/>), где L - система соотношений, составляющая логическую основу процедуры; Р - описание динамики. Пусть J{aj)c D* - некоторое J-множество. Будем говорить, что процедура Н обеспечивает синхронизацию ветвей множества J(ai) (в символической форме - I ./(а<)), если характеристика L процедуры Е включает индикаторную переменную {0,l}, удовлетворяющую следующим условиям. Условие A. Xi(t) = 0, если хотя бы одна ветвь BseJ(ai) в момент t не завершена, *,(/)= 1 иначе.

Условие В. Г-С Ф оо, где t, t" - моменты времени такие, что x,(t')= 1 ~>0, *,(*")= 0 -»1; запись 1->0 (0->1) означает изменение значения из 1 в 0 (из 0 в 1). Определение 5. Процедуру синхронизации Е назовем универсальной для системы tJ™, если Vj(a,)c D*, \ D*uм)еЛ": Щв/), где Х- множество всевозможных отображений вида х*„ '■ D*,, —» М.

Формализованную оценку процедуры синхронизации можно выполнить на основе следующих критериев эффективности: минимум времени организации синхронизации 71(H); минимум удельной структурной сложности ^(н).

Время организации синхронизации Т(Е) вычисляется по формуле:

Г(Е)= шах ( max (г+(Я-)}- max (г"(в.)} ->min,

где т+(Ва), т(Вр) - промежутки времени от начала выполнения программы Q„ до моментов активизации ветви Ва и завершения ветви Bp соответственно.

Структурную сложность W(E) процедуры Е определим как минимальное число эквивалентных логических элементов, необходимых для реализации модели в системе N^. Под эквивалентным логическим элементом при этом будем понимать абстрактный логический элемент, реализующий любую булеву функцию базиса {a,v,1}. Под удельной структурной сложностью W(e) будем понимать минимальное число эквивалентных логических элементов, необходимых для реализации процедуры, в расчете на один процессор системы //Я).

В основе разработанной процедуры лежит отображение условий

синхронизации параллельных процессов флагами, формируемыми в множестве каналов синхронизации {Кь Кг, ..., К„}, п-шах{|К1(|], каждый из которых

соответствует определенному ./-множеству (барьеру). Канал К|, I = 1,п, представляет собой однородную среду (распределенный синхронизатор), ячейки которой распределены между процессорами.

Процедура базируется на понятиях понятия вектора соответствия, признака текущего состояния процесса и признака текущего состояния процессора по отношению к барьеру.

Вектор соответствия для процессора / = 1,ЛГ,, } = , имеет вид

I* («)= На-М... ,<(«)),

[0, если (£>:Ц)пУ(а/)5,0)л(кц|>/);

[1, если {Ои[т11)п^а,)= 0)у \Уи\<1), Текущее состояние ветви (процесса) Я, е определяется флагом

1, если (С(0 = 0)л ^ < V

1, если ветвь в момент / активна, (0 =" т е- выполняете я модулем т1}; О иначе.

Текущее состояние процессора ти( г = 1, А',, у = 1, , по отношению к барьеру а) определяется признаком г/ (<) в виде

где — признак состояния ветви Ва е 0*(/иу)г\./(л;).

Условие синхронизации процессов множества Да)) имеет вид

Алгоритм организации синхронизации ветвей множества У(а/) в системе

Л»

основан на выполнении последовательности циклов синхронизации в канале АГ/. Каждый цикл включает два этапа: (а) опрос состояния ветвей ВаеУ(я/) и формирование признака 2.рЛ\ (Ь) активизация ветвей ВреГ\а!) и восстановление исходного значения У.рО. Значение признака по окончании //-го этапа очередного цикла синхронизации определяется следующим обобщенным соотношением

2 =(">2 г"^ г» - 2/ л л при > 1)л 0 >

' ' ' ' ' 1^лг>риО = 1КО = 1),(0)г^о, где — значение признака '¿\ на выходе (у)-й ячейки канала К,. При этом момент завершения ветвей задается условием

0') = ^ ^ (/')=0 1, а момент активизации ветви Вр е Б*(»и )п.Г(а/) — условием

г?((")= 1-^0.

В третьей главе рассматривается структурно-функциональная организация центрального микропрограммируемого процессора синхронизации специализированной матричной МРР-системы с многоузловой решетчатой топологией на основе разработанной процедуры и распределенных однотипных устройств барьерной синхронизации (патент № 2249849).

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

В состав процессора входят следующие элементы и блоки: блок 1 памяти программ; регистр 2 адреса; регистр 3 команд; мультиплексор 4 логических условий; коммутатор 6 адреса; блок 10 синхронизации (генератор импульсов); первый 14 второй 12 третий 13 элементы ИЛИ; регистр 5 вектора соответствия; буферный 7 регистр; первый 8 и второй 9 дешифраторы номера вершины синхронизации; блок 11 элементов ИЛИ; первый 16 и второй 15 одновибраторы; элемент 17 задержки; группа узловых блоков 18.1-18.ц управления синхронизацией.

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

рис.2.

Блок управления синхронизацией реализует функции одного устройства синхронизации и содержит: триггер 21.1 наличия соседа слева; триггер 21.2 наличия соседа снизу; группа элементов НЕ 31.1,31.2,31.3,31.4; группа элементов И 23.1,23.2,23.3,23.4; элементы ИЛИ первый 19 второй 20 третий 24 четвертый 28 пятый 26; первый 22 и второй 37 элементы И, коммутатор 25; триггер 30 и триггер 29 разрешения запуска.

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

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

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

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

Мультиплексор 4 логических условий служит для опроса значений логических условий на входе 32 процессора и модификации младшего

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

Регистр 5 вектора соответствия введен с целью хранения вектора в''(к) в течение времени исполнения к-й программы.

Коммутатор 6 адреса обеспечивает выбор направления приема исполнительного адреса следующей команды.

Буферный регистр 7 предназначен для временной фиксации исполнительного адреса следующей команды в процессе запуска текущего процессора после завершения некоторой группы параллельных участков программы. Необходимость такой фиксации обусловлена исчезновением информации на выходах 3.2 и 3.3 регистра 3 (вследствие сброса регистра 3 в момент завершения группы параллельных участков) до момента фактической записи адреса следующей команды в регистр 2.

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

Дешифратор 9 обеспечивает преобразование кода номера вершины синхронизации а1( определяющей момент последующего запуска текущего процессора, в соответствующий унитарный код, а также блокировку / открытие элементов И 12.1—12.я.

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

Триггеры наличия соседа слева 21.1 и наличия соседа снизу 21.2 вместе с элементами НЕ 31.1 и 31.2 служат для индикации наличия соседних микроконтроллеров слева и снизу соответственно, и при отсутствии соседних микроконтроллеров, совместно с элементами И 23.1, 23.2, 23.3, 23.4, блокируют распространение сигналов управления синхронизацией.

Элемент И 22 служит для блокировки прохождения сигнала управления синхронизацией в случае невыполнения условий участков синхронизации в текущем процессоре.

Коммутатор 25 вместе с элементом НЕ 31.3 служит для инвертирования сигнала управления синхронизацией.

Триггер 29 разрешения запуска служит для фиксации сигнала окончания параллельного участка текущего процессора.

Триггер 30 вместе с элементом НЕ 31.4 служит для хранения признака расположения текущего процессора.

32

11

33

Б

Т. 7

К

1г

Б

1

.С

ч12

40

о-

34 Г | 35.1°-

I

(35Г

С

36.1_ Зб2

(37)

(36)

10

1317

15

Г 37Ло-372о-

38.^

37л

34

(38Ь, 38.Ь —

У

3)

43

42^

18.1

41. п

42л

18.п

Рис. 1 Функциональная схема центрального процессора синхронизации

(44)

:(45)

-о

/14

16

18.1

19 > 1

.20

31 1

Б тт

21 1

Я

31 2

Б тг

212

К

,22

&

231

I

23 3

31.3

-23 2

"О"

■и

23 4 •

в ТТ

О 29

чС

,24

.25

& 1 '

&

п

28

-27

31 4х

\С тт

30

О

441 -О

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

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

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

Используя аналитический подход, получена верхняя оценка времени организации синхронизации ЦЕ).

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

Теорема. Верхняя граница времени синхронизации ТЩ) составляет 2 в (Ы,+Ы2).

Следствие 1. Учитывая, что Л^-Л^, асимптотика времени синхронизации ДН) составит величину = Л', = .

Следствие 2. Учитывая, что ()~ Иг, асимптотика времени синхронизации составит где 0- среднее число синхронизируемых процессов.

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

На рис.4 показана зависимость времени синхронизации, Т, от количества синхронизируемых процессов £>, при NlяN2 равных 10,20 и 30 (/V равно 100,400, и 900). На рис.5 показана зависимость времени синхронизации, Т, от числа процессоров системы, при фиксированном (2 равном 5 и 25. На рис.6 дополнительно показана зависимость времени синхронизации, Т, от количества синхронизируемых процессов, в предельном случае, при 0 = N.

Рис.3. Сеть Петри, представляющая процедуру синхронизации

Сравнение полученных экспериментальных результатов с данными для лучших аналогов позволяет установить, что созданная процедура требует меньше времени на синхронизацию произвольного количества процессов. Так, максимальное время синхронизации согласно рис.4 в системе содержащей 900 процессоров составляет 3.8 мкс, а в системе содержащей 128 процессоров (см. рис.6) - менее чем за 1 мкс. В системе СМ-5 (Thinking Machines) содержащей 128 процессоров глобальная барьерная синхронизация выполняется за 5 мкс. С точки зрения аппаратной сложности разработанное устройство синхронизации обладает как минимум 10-кратным преимуществом перед лучшими из аналогов: число входящих в него вентилей составляет 300 4- 40Q и не зависит от числа процессоров системы. Например, при Q=N = 1024 число вентилей в одном устройстве синхронизации равно примерно 3040 тысяч, что в известных аналогах достигается уже при 128 процессорах.

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

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

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

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

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

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

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

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

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

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

Т, нс 3800 3500 3200 2900 2600 2300 2000 1700 1400 1100 800

20

35

50

65

80

-N=100 -N=400 -N=900

95

Рис. 4. Зависимости времени синхронизации, Т, от числа синхронизируемых процессов, Q

Т, не 4400 3900 3400 2900 2400 1900 1400 900 400

¡¡Ш

25

175 325 475 625 775 925 1075 1225

N

Рис. 5. Зависимости времени синхронизации, Т, от числа процессоров системы, М,

при фиксированном ()

Т,нс 1400 1200 1000 800 600 400

16 36 56 76 96 116 136 156 176 196 216 236 256 276 (

Рис.6. Зависимость времени синхронизации, Т, <тг числа синхронизируемых процессов, (), при допущении, что <2 = Ы

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

1. Иванов A.A. Алгоритмы межпроцессорного взаимодействия в отказоустойчивых многопроцессорных системах [Текст] / Иванов A.A., Джихад Абдель-Джалиль, Ватутин Э.И., Зотов И.В. // Сборник научных статей "Методы и системы обработки информации". М.: Изд-во "Горячая линия - телеком", 2004, Ч. 2. С. 117-125.

2. Иванов A.A. Процедура передачи сообщений в коммутаторе однородной вычислительной системы [Текст] / Иванов A.A., Зотов И.В. // «Распознавание-2003»: Сборник материалов VI Международной конференции. Курск, 2003. Ч. 2 С.227-229.

3. Иванов A.A. Среда для барьерной синхронизации параллельных процессов в матричных вычислительных системах [Текст] / Иванов A.A. Виноградов C.B. // Континуальные алгебраические логики, исчисления и нейроинформалгика в науке и технике: материалы Международной научно-технической конференции. Ульяновск. 2004. Том 3. С. 55-57.

4. Иванов A.A. Децентрализованная аппаратная модель барьерной синхронизации для матричных вычислительных систем [Текст] / Иванов A.A. // Образование, наука и призводство: материалы Международного студенческого форума. Белгород. 2004. С. 34.

5. Патент 2249849 Российская Федерация, МПК7 G06F15/163. Модуль для обмена сообщениями / Иванов A.A., Зотов И.В., Анпилогов Е.Г., Ефремов В.В.; заявитель и патентообладатель КурскГТУ. - Ks 2003129963/09; заявл. 08.10.2003; опубл. 10.04.2005, Бюл. №10. - Зс.

ИД №06430 от 10.12.01 Подписано в печать 25.11.05 . Формат 60x84 1/16 . Печатных листов 1 . Тираж 100 экз. Заказ .

Курский государственный технический университет, Издательско-полиграфический центр Курского государственного технического университета, 305040, Курск, ул. 50 лет Октября, 94.

V

Г

№2512 б

РЫБ Русский фонд

2006-4 28512

ВВЕДЕНИЕ

1. ЗАДАЧИ СИНХРОНИЗАЦИИ В ПАРАЛЛЕЛЬНЫХ СИСТЕМАХ

1.1. Архитектура современных параллельных систем

1.2. Межпроцессорное взаимодействие в параллельных системах

1.3. Задача синхронизации и подходы к ее решению

1.4. Методы барьерной синхронизации 48 Выводы

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

2.1. Модель параллельной системы

2.2. Содержательная характеристика и формализованное 58 представление задачи обеспечения синхронизации

2.3. Характеристика процедуры синхронизации

2.4. Алгоритм взаимодействия синхронизируемых процессов

2.5. Примеры использования процедуры синхронизации

Выводы 3. УСТРОЙСТВО СИНХРОНИЗАЦИИ НА ОСНОВЕ СОЗДАННОЙ 67 ПРОЦЕДУРЫ

3.1. Функциональная организация матричной МРР-системы

3.2. Анализ работы системы при рассмотрении соответствующих 80 режимов функционирования процессоров

Выводы

4. ДОКАЗАТЕЛЬСТВО КОРРЕКТНОСТИ СОЗДАННОЙ 100 ПРОЦЕДУРЫ И ОЦЕНКА ПРЕИМУЩЕСТВ РАЗРАБОТАННОЙ ПРОЦЕДУРЫ И УСТРОЙСТВА

4.1. Представление процедуры синхронизации в виде сети Петри

4.2 Доказательство корректности процедуры синхронизации

4.3 Аналитическая оценка аппаратной сложности устройства 105 синхронизации

4.4 Аналитическая оценка созданной процедуры синхронизации

4.5 Экспериментальная оценка созданной процедуры 107 синхронизации

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

4.5.2. Архитектура экспериментальных программных средств

4.5.3. Результаты эксперимента

Актуальность работы. Одним из перспективных архитектурных подклассов параллельных вычислительных систем (ВС) являются мультикомпьютеры с распределенной памятью (МРР-системы). Отличительная особенность таких систем - разделение физической памяти между процессорами (модулями) и организация их взаимодействия через коммуникационную сеть. Примерами подобных МРР-систем являются Cray ТЗЕ и 0rigin2000.

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

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

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

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

В настоящее время известно широкое разнообразие подходов к барьерной синхронизации в МРР-системах (J. R. Anderson, Т. A. Johnson, R. R. Hoare, Т. Muhammad и др.). Разработаны многочисленные варианты их реализации, как программные, так и аппаратные. При этом наиболее широко представлены решения программного уровня (Dissemination barrier, Butterfly barrier, Tree-based barriers и др.)- Аппаратные решения, обладающие значительно большим быстродействием, пока не получили широкого распространения (DBM, Cyclical Cascade Barrier, СМ-5 Barrier Control Network и др.)- Известные аппаратные решения носят, как правило, централизованный характер и не являются распределенными (DBM, Cyclical Cascade Barrier), что ограничивает возможность включения в систему новых процессоров (усложняет наращивание системы).

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

Работа выполнена при поддержке гранта Министерства образования РФ «Столетовские гранты-2003», а также в рамках совместных работ с ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года. Основная часть диссертационной работы выполнена в рамках плана научно-исследовательских работ Курского государственного технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2005 годах, утвержденному начальником управления планирования и финансирования научных исследований.

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

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

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

2. Разработка распределенной децентрализованной аппаратно-ориентированной процедуры барьерной синхронизации.

3. Доказательство корректности разработанной процедуры на основе аппарата сетей Петри.

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

Методы исследования. При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных на кафедре ВТ КурскГТУ под руководством доц. Зотова И.В.

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

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

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

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

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

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

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

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

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

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

Техническое решение устройства синхронизации в МРР-системе выполнено на уровне изобретения (патент № 2249849).

Реализация и внедрение.

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

Апробация работы.

Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавание-2003» (г. Курск,

2003), НТК «Образование, наука, производство» (г. Белгород, 2004), НТК «КЛИН-2004» (г. Ульяновск, 2004).

Публикации.

Результаты диссертационной работы отражены в 5 публикациях, в числе которых 1 статья и 1 патент на изобретение.

На защиту выносятся:

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

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

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

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

Объем и структура работы.

Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 131 страницу текста и поясняется 21 рисунком и 2 таблицами; список литературы включает 60 наименований; приложения содержат 40 страниц.

Выводы

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

1. Some Computer Organisations and Their Effectiveness Text. / Flynn M. // IEEE Trans. Computers. 1972. V.21. N 9. P.948-960

2. Completing an MIMD Multiprocessor Taxonomy Text. / Johnson E.E. // Computer Architecture News. 1988. V. 16. N 2. P.44-48.

3. Корхов Архитектуры и топологии многопроцессорных вычислительных систем. Электронный ресурс. / А. Богданов, В. Мареев, Е. Станкова, В. // http://www.informika.ru

4. A cluster structure as an interconnection network for large multimicrocomputer systems Text. / Wu S.B., Liu M.T. // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 254-264.

5. A survey of interconnection networks Text. / Feng T.-Y. // IEEE Computer, 1981. vol.14, № 12. PP. 12-27

6. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. // Автоматика и вычислительная техника, 1987. № 3. С. 31-43.

7. The binary tree as an interconnection network: applications of multiprocessor systems and VLSI Text. / Horowitz E., Zorat A. // IEEE Transactions on Computers, 1981. vol. C. 30, № 4. PP. 247-253.л

8. Design of HM p a hierarchical multimicroprocessor for general-purpose applications Text. / Schin K.G., Lee Y.-H., Sasidhar J. // IEEE Transactions on Computers, 1982. vol. C. 31, № 11. PP. 10451053.

9. X-tree: a tree structured multiprocessor computer architecture Text. / Despain A.M., Patterson D.A. // Proceedings of 5th Symp. on Computer Architecture, Palo Alto, Calif., 1978. PP. 144-151.

10. Design and Implementation of a Packet Switched Routing Chip Text. / Kupta P., McKeown N. // Proceedings of Hot Interconnects 6. Stanford, 1998. PP. 77-84.

11. Topological properties of hypercubes Text. / Saad Y., Schults M.U. // IEEE Transactions, 1988. vol. C. 37, № 7. PP. 867-872.

12. Электронный ресурс. //www.parallel.ru

13. Апраксин Ю.К. Алгоритмы маршрутизации для сетей с коммутацией сообщений Текст. / Апраксин Ю.К., Запевалин

14. A.А., Кирюхин В.В. // Автоматика и вычислительная техника, 1982. №2. С. 87-92.

15. Practical algorithms for online routing on fixed and reconfigurable meshes Text. / Herbordt M.C., Corbertt J.C., Weems C.C. // J. Paral. Distrib. Comput., 1994. vol.20, No.3. PP. 341-356.

16. Packet routing on grids of processors Text. / Kunde M. // Lecture Notes in Computer Science, New York: Springer-Verlag, 1998. vol.401. PP. 129-136.

17. Лукьянов А.В. Адаптивное управление маршрутизацией в коммуникационных сетях с коммутацией пакетов Текст. / Лукьянов А.В., Первозванский А.А. // Автоматика и вычислительная техника, 1983. №1. С. 60-65.

18. Шеметов В.В. Гибридные алгоритмы маршрутизации для информационно-вычислительных сетей Текст. // Автоматика и вычислительная техника, 1986. №1. С. 50-53.

19. Шеметов В.В. Децентрализованные алгоритмы маршрутизации для коммуникационных сетей с коммутацией пакетов Текст. // Автоматика и вычислительная техника, 1985. №6. С. 17-26.

20. Cray ТЗЕ Users Guide. 2-nd edition Text. / Juha Haataja, Ville Savolainen // 1998, Center for Scientific Computing, Finland

21. И.В. Зотов Организация и синтез микропрограммных мультимикроконтроллеров Текст. / И.В. Зотов, В.А. Колосков,

22. B.C. Титов, К.А. Сапронов, А.П. Волков // Курск: Изд-во «Курск», 1999. 59 с.

23. Дийкстра Э. Взаимодействие последовательных процессов Текст. // Языки программирования. М.: Мир, 1972 - С.9-86.

24. Synchronization techniques for distributed systems: an overview Text. / Mee V.J., Hura G.S. // Microelectron. Reliab. 1992. -Vol.32, No. 1/2.-PP. 175-197.

25. Synchronization with eventcounts and sequencers Text. / Reed D.P. // Commun. ACM. 1979. - Vol.22, No. 2. - PP. 115-123.

26. Simulation and Analysis of Barrier Synchronization Methods Final Report Text. / James R. Anderson // May 29, 1995 Advisor: David Lilja EE5492H Spring Quarter 1995

27. Cyclical cascade chains: a dynamic barrier synchronization mechanism for multiprocessor systems Text. / T. A. Johnson, R. R. Hoare // University of Pittsburgh, Department of Electrical Engineering Pittsburgh,PA 15261 2001

28. Hardware Barrier Synchronization For A Cluster Of Personal Computers Text. / Tariq Muhammad // Master of Science in Electrical Engineering May 1995

29. Barrier synchronization for distributed memory massively parallel processing systems Text. / Oberlin, Steven M. // US5434995: Dec. 10, 1993 24p.

30. Subset Barrier Synchronization on a Private-Memory Parallel System Text. / A. Feldmann, T. Gross, D. O'Hallaron, T. Strieker // Commun. ACM 1992.

31. Патент 2168198 Российская Федерация, МПК7 G06F9/28 Микроконтроллерная сеть / Зотов И.В. // заявл. 13.09.1999; опубл. 27.05.2001, БИ №15 21 с.

32. Харченко B.C. Декомпозиция параллельных матричных схем алгоритмов в задачах синтеза микроконтроллерных сетей Текст. / Харченко B.C., Кальченко С.Б., Сазонов А.Е. // АВТ. — 1990. — №4. — С. 81-89.

33. Котов В.Е. Сети Петри Текст. // Главная редакция физико-математической литературы. М.: Наука. - 1984. - С. 5-9.

34. Питерсон Дж. Теория сетей Петри и моделирование систем Текст. // Пер. с англ. М.: Мир - 1984. - С. 8-14.

35. Электронный ресурс. // http://www.myri.com/

36. Советов Б.Я. Моделирование систем Текст. / Советов Б.Я., Яковлев С.А. // М.: Высшая школа, 2001. 273 с.

37. Иванов А.А. Процедура передачи сообщений в коммутаторе однородной вычислительной системы Текст. / Иванов А.А., Зотов И.В. // «Распознавание-2003»: Сборник материалов VI Международной конференции. Курск, 2003. Ч. 2 С.227-229 .

38. Иванов А.А. Децентрализованная аппаратная модель барьерной синхронизации для матричных вычислительных систем Текст. / Иванов А.А. // Образование, наука и призводство: материалы Международного студенческого форума. Белгород. 2004. С. 34.

39. Патент 2249849 Российская Федерация, МПК7 G06F15/163. Модуль для обмена сообщениями / Иванов А.А., Зотов И.В., Анпилогов Е.Г., Ефремов В.В.; заявитель и патентообладатель

40. КурскГТУ. № 2003129963/09; заявл. 08.10.2003; опубл. 10.04.2005, Бюл. №10. - Зс.

41. Zero-Cost Synchronization in a Modified BSP Model Text. / R.D. Alpert, J.F. Philbin. // Technical report, NEC Research Institute, 1997.

42. Practical Barrier Synchronization Text. / J.M.D. Hill, D.B. Skillicorn. // Technical Report PRG-TR-16-96, Oxford University Computing Laboratory, 1996.

43. Communication structures for large networks of microcomputers Text. / Wittie L.D // IEEE Transactions on Computers, 1981. vol. C.30, №4. PP. 264-273.

44. The cube-connected connected cycles: a versatile network for parallel computation Text. / Perparata P.P., Vuillemin J. // Commun. OfACM., 1981. vol. 24, №5. PP. 300-309.

45. A survey of interconnection methods for reconflgurable parallel processing systems Text. / Siegel H.J., McMillen R.J., Mueller P.T. // In: AFIPS Conf. Proc., Washington, D.C., 1979. vol.29. №2. PP. 108115.

46. Кристофидес H. Теория графов. Алгоритмический подход Текст. //М.: Мир, 1978. 432 с.

47. Корн Г. Справочник по математике для научных работником иинженеров Текст. / Корн Г., Корн Т. // М.: Наука, 1968. 720 с.

48. Степанян С.О. Коммуникационные сети в многопроцессорных ЭВМ Текст. // Автоматика и вычислительная техника, 1987. № 3. С. 31-43.

49. Communication structures for large networks of microcomputers Text. / Wittie L.D. // IEEE Transactions on Computers, 1981. vol. C. 30, №4. PP. 264-273.

50. Comparing barrier algorithms Text. / Arenstorf N., Jordan H. // Parallel Computing 12,2- 1989, 157-170.

51. The butterfly barrier Text. / Brooks E. // International Journal Parallel Programming 15,4 1987, 295-307.

52. Subset barrier synchronization: Communication models and implementation Text. / Feldmann A. //Tech. Rep. CMU-CS-92-136, School of Computer Science, Carnege Mellon University, 1992.

53. Two algorithms for barrier synchronization Text. / Yensgen D., Finkel R., Manberg U. // International Journal on Parallel Programming 17, 1 1988, 1-17.

54. Barrier MIMD architecture: Design and compilation Text. / CTKeefe M., Dietz H. // Tech. Rep. TR-EE 90-50, School of Electrical Engineering Purdue University, August 1990.

55. Two-Phase Barrier: A Synchronization Primitive for Improving the Processor Utilization Text. / I. Jung, J. Hyun, J. Lee, J. Ma // International Journal of Parallel Programming, Vol. 29, No.6, 2001.

56. Fast, Contention-Free Combining Tree Barriers Text. / M.L. Scott, J.M. Mellor-Crummey // International Journal of Parallel Programming, 22(4): 449-481, 1994.

57. Communicable Memory and Lazy Barriers for Bulk Synchronous Parallelism in BSPk Text. / A. Fahmy, A. Heddaya // Technical Report BU-CS-96-012, Boston University, 1996.

58. Questions and Answers about BSP Text. / D.B. Skillicorn, J.M.D. Hill, W.F. McColl // Technical Report PRG-TR-15-96, Oxford University Computing Laboratory, 1996.

59. Object-Oriented Aggregate Networks, doctoral thesis Text. / R. Hoare // School of Electrical and Computer Engineering. West Lafayette, IN: Purdue University, 1993.

60. Highly Parallel Computing Text. / G. Almasi, A. Gottlieb // Second Edition. Redwood City, CA: The Benjamin/Cummings Publishing Company, Inc., 1994.

61. ClusterNet: An Object-Oriented Cluster Network Text. / R. Hoare // Inetrnational Parallel and Distirbuted Processing Symposium, Workshop on Personal Computers based Networks of Workstations, Cancun, Mexico, 2000.