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

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

Бредихин Руслан Владимирович

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

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

27 НОЯ 2014

005556084

Курск-2014

005556084

Работа выполнена в Юго-Западном государственном университете

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

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

Официальные оппоненты: Подвальный Семён Леонидович

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

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

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

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

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

С диссертацией можно ознакомиться в библиотеке ЮЗГУ и на официальном сайте университета swsu.ru.

[ с

Автореферат разослан « /у»14 г

Ученый секретарь совета Д 212.105.02___Евгений Анатольевич Титенко

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

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

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

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

Вопросами организации межпроцессорного взаимодействия в параллельных системах занимались многие отечественные и зарубежные ученые, в частности, A.B. Каляев, И.В. Каляев, В.В. Воеводин, Вл.В. Воеводин, A.B. Корнеев, И.И. Левин, А.П. Типикин, И.В. Зотов, E.D. Brooks, D.K. Panda, J. Wu, M. O'Keefe, W.E. Cohen и др. За последние три десятилетия было разработано широкое многообразие методов, процедур и средств барьерной синхронизации, используемых на различных уровнях параллелизма и ориентированных на параллельные вычислительные системы разных архитектурных классов. Для систем рассматриваемого класса наиболее перспективны аппаратно-ориентированные методы распределенной барьерной синхронизации, обладающие наилучшими скоростными характеристиками и адаптированные к СБИС-реализации. Однако известные аппаратно-ориентированные методы характеризуются недостаточной гибкостью, накладывая жесткие ограничения на конфигурацию барьерных групп и/или количество барьеров в приложении, которые вступают в противоречие с действующими стандартами параллельного программирования (в частности, MPI 3.0) и не позволяют эффективно использовать эти методы на практике.

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

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

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

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

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

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

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

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

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

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

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

Результаты, выносимые на защиту, и их научная новизна:

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

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

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

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертационной работы были заслушаны и получили одобрение на Международной научно-технической конференции «Распознавание - 2013» (г. Курск, 2013 г.), на I Региональной научно-технической конференции «Информационные системы и технол'о-

гии» (г. Курск, 2012 г.), а также на научных семинарах кафедры вычислительной техники ЮЗГУ (ранее КурскГТУ) с 2009 по 2014 г.

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

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

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

Области возможного использования. Результаты диссертационной работы могут найти применение при создании перспективных матричных СБИС-мультикомпьютеров, подобных однокристальным системам TILE-Gx, а также при построении крупномасштабных мультикомпьютеров (аналогичных выпускаемым фирмами Cray, IBM, HP), объединяющих тысячи - сотни тысяч идентичных процессорных узлов многомерной матричной коммуникационной средой, и локальных сетей ЭВМ, организованных в матричные структуры.

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

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

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

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

Программные решения полностью базируются на использовании стандартного коммуникационного оборудования и протоколов и обычно представляются в виде набора специализированных системных утилит. Будучи весьма гибкими, масштабируемыми и простыми, программно реализованные процедуры барьерной синхронизации, как правило, на 1-3 порядка медленнее по сравнению с аппаратно реализованными процедурами и поэтому не нашли применения в мультикомпьютерах. Гибридный подход к барьерной синхронизации предполагает введение незначительных расширений в структуру стандартных коммуникационных аппаратных средств (например, барьерных регистров и логических схем), которые не меняют архитектуры коммуникационной среды вычислительной системы. Аппаратные решения, в противоположность гибридным, предусматривают введение отдельной управляющей коммуникационной сети, логически отображенной на стандартную (базовую) коммуникационную среду системы. Эта управляющая сеть может иметь такую же топологию, что и базовая среда, но может и отличаться от неё по топологии.

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

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

Аппаратные методы и средства барьерной синхронизации уже нашли применение в первых коммерческих мультикомпьютерах (Cray T3D, Thinking Machines СМ-5, Fujitsu АР1000). Однако ввиду наличия жестких ограничений на конфигурацию барьерных групп и/или количество барьеров в параллельных программах их эффективное применение в современных и перспективных системах, в т.ч. ОММК, в соответствии со стандартом MPI практически невозможно. Таким образом, существует необходимость проведения дальнейших исследований и разработки методов и аппаратных средств, обеспечивающих повышение гибкости среды синхронизации в

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

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

Виртуально-многослойная координирующая среда представляет собой сеть из однотипных ячеек, называемых барьерными модулями. Каждый барьерный модуль соответствует «своему» процессорному модулю мультикомпьютера и решает следующие основные задачи: 1) хранение данных об отображении барьеров, входящих в реализуемые параллельные программы, на ВМКС; 2) фиксация признаков завершения параллельных процессов соответствующим ему процессорным модулем-3) управление распространением двоичных сигналов, отражающих состояние всех выполняемых мультикомпьютером барьеров (завершен / не завершен); 4) обеспечение запуска данного процессорного модуля при завершении ожидаемого барьера.

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

Структура мультикомпьютера представляется в виде графа II =<М,и> где М - множество вершин, соответствующее множеству процессорных модулей а *£/ -множество дуг, отражающее связи между модулями. Каждому модулю поставим в соответствие порядковый номер вида х, = 1>АГ,, где М, - число модулей

в /-м измерении, / = !,</. Модуль с порядковым номером (*„*,,...,*„) будем условно обозначать как т{х1,хг,...,х11).

Пусть мультикомпьютер выполняет некоторое множество параллельных программ У = {О;}. В каждой программе П„ 4имеется множество ветвей (участков)

£>*, которые находятся в отношениях параллельности, альтернативы либо предшествования (следования). Формально состояние ветви Вр е В'и задается индикаторной функцией др(() такой, что: = если ветвь Вр в момент { активна (т.е. выполняется некоторым модулем т(х1,х2,...,ха)), др(0 = 0 в противном случае.

Пусть Уи - множество барьеров программы Пц. Обозначим через J(as) множество ветвей, сходящихся в барьере а, в Уи. Определим для каждого барьера е Уи индикаторную функцию е {0,1}, удовлетворяющую следующим условиям:

2,(() = 0, если хотя бы одна ветвь В, еЛа^) в момент / активна, 25(() = 1 иначе, полагая 21 (0) = 0. Ясно, что 2, (() = ^ л .

Синхронизация ветвей J(as) считается обеспеченной, если в некоторый момент С, (/' > 0) л * со), выполняется условие синхронизации:

^(0 = 0^1, (1)

где запись 0 —> 1 (1 —> 0) означает переход значения функции из 0 в 1 (из 1 в 0).

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

3Г, (/* > О Л (г' * оо): 2, (О = 1 -> 0. (2)

Временные интервалы формирования условий (1) и (2) называются соответственно фазой синхронизации и фазой восстановления.

Каждому процессорному модулю т(х1,х2,...,х11) сопоставляется двоичный

вектор устанавливающий соответствие между модулями и барьерами

данной программы. Назовем ^■^■■"^•••■Л) вектором соответствия:

где п — число физических слоев (разрядность) координирующей среды, ар — число виртуальных слоев в каждом физическом слое (глубина виртуализации ВМКС), причем = 0, если за модулем т(х1,х2,...,х11) закреплена ветвь программы, завершающаяся барьером а,, в противном случае у^*'-*1'^ =1 (в этом случае модуль т(х1,х2,...,ха) не должен оказывать влияния на процесс синхронизации ветвей, сходящихся в барьере а,).

Пусть Вр eJ{a¡) — некоторая ветвь, назначенная на модуль т(х1,х2,...,хс/). Тогда состояние модуля т(х{,х2,...,ха) по отношению к барьеру а, представляется следующим образом:

(3)

где (г) = у^л*--**) \/<;р(г). Тогда согласно формуле (3) условие синхрониза-

ции (1) будет обеспечено в момент ¡' завершения последней ещё не завершенной

ветви множества ./(а,), назначенной на некоторый модуль т(х[,х'г,... х'): = .....

Таким образом, для обеспечения синхронизации в ОММК необходимо вычисление множества индикаторных функций для всех барьеров по текущим значениям признаков -'<>(,)} и оперативная рассылка «уведомлений» о наступлении события (/') = 0 1 всем модулям, ожидающим завершение барьера а,.

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

чим как с,{хх,хг,...,ха). Введем на множестве ячеек С, координирующей среды сети синхронизации Я, и восстановления Н1 соответственно. Вершины, соответствующие

ячейкам с,(хх,х2,...,ха) и с,(х;,х'2.....х'Л), свяжем в сетях Н, и Н, дугами, если и

только если соответственно:

V/ = (*,. = х;) л (*,. = х) -1)

Сети Н, и Н, определяют порядок распространения условий (1) и (2) в слое К, соответственно. На рис. 1 в качестве иллюстрации представлены сети Я, и Я, для двумерного матричного мультикомпьютера.

*;=2,лгу >

х1*Щ •

"ОггОтгОтг

(2,1)

С/С1.3) Тс,(2,3) уе,(3.3)

lO.fi) с,(2,^,) с,(3,Л^)

с,С,. 1)

с,(^„2)

О^СЬтОгг

(2.3) ^,(3,3)

с,(Аг,.Л',)

|(",.1)

Рис. 1. Сети синхронизации (а) и восстановления (б) слоя К, двумерного ОММК

Логика функционирования ячеек {сД*,,^,...,^)} в фазе синхронизации определяется выражением

где (/) - значение индикаторной функции, снимаемое с прямого выхода

ячейки с1{х1,х2,...,х11), з — номер барьера, соответствующего слою К1, причем если Э/е{1,2,...,£/}: х, = 0, то предполагается 2]г"*г Л> (/) = 1 (значение с прямого выхода «несуществующей» ячейки всегда равно 1).

Логика функционирования ячеек [с1(х1,х2,...,х11)} в фазе восстановления определяется формулой

^ (() = г'1'*11'"1*' (/) л (г) л... л л+1) (г), (5)

где — значение индикаторной функции, снимаемое с инверсного выхода

ячейки с1(х1,х2,...,х</), причем если 3/е{1,2,...,</}: х, = /V, +1, то предполагается

21(Г"Г2 ,Г',) (?) = 0 (значение с инверсного выхода «несуществующей» ячейки всегда равно 0).

Для связывания сетей синхронизации и восстановления в единый слой К, и обеспечения реентерабельности процесса синхронизации предполагается:

Формулы (4)-(7) позволяют синтезировать логическую конфигурацию физического слоя координирующей среды для ОММК произвольной размерности. Ее устойчивое начальное состояние обеспечивается при наличии хотя бы одного нулевого значения г'*"*1"1''(г).

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

Пусть - множество виртуальных слоев, размещенных в

физическом слое К¡. Ячейке с,(х1,х2,...,х<1) слоя /Г, поставим в соответствие множество виртуальных ячеек (дг,,лг2,...,лг^,)}, / = 1 ,р, и пару коммутирующих ячеек

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

4- Т ~

А, (х1,х2,...,х^ и по выходу - с вершиной (х1,х2,...,хс/). Также в сети Н, связываются пары вершин Л, (х^х2,...,ха) и (х^х^,...^), если и только если: V/ * у, / = : (х, = х;) л (*, = х; + •

Аналогично в сети Н, дугами соединяются все вершины, соответствующие ячейкам множества |с)(х1,х2,...,х(/)|, по входу с вершиной к}(х1,х2,...,х(}) и по вы-

ходу - с вершиной к^хих2,,..,ха). Также в сети Я, соединяются пары вершин к, (х1,х2,...,х{/) и к, (хх,х2,-..,хс1), если и только если:

V/

Сети Я, и Я, определяют порядок включения (активизации) виртуальных слоев для распространения условий (1) и (2) в слое К, соответственно. На рис. 2 в качестве иллюстрации представлены сети Я, и Н, для двумерного ОММК. Жирным выделен один из виртуальных слоев. Логическая конфигурация виртуальных слоев аналогична представленной выше для физического слоя и в общем виде описывается формулами (4)-(7).

Рис. 2. Виртуальные сети синхронизации (а) и восстановления (б) слоя К двумерного мультикомпьютера

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

Множество ячеек С, слоя разбивается на максимальные по включению подмножества С°, С], С..., С/, С/+! таким образом, чтобы в подмножество С/, ] = вошли все ячейки, которые находятся на расстоянии у от вершины с, (1,1,..., 1), и принимается С,° = {с,(1Д,...,1)}, С?*1 = {«>,(*„ЛГ2>...,*„)}. Аналогично множество ячеек С, слоя К, разбивается на максимальные по включению подмножества С°, С}, С, С?, СГ таким образом, чтобы в подмножество С/, / = вошли все ячейки, которые находятся на расстоянии у от вершины сДЛ^,...,^), и принимается

СГ ={с,(1Л,--Л)}, 2,...,Л^)}. Подмножества С/ и С/ называются

соответственно прямыми и обратными фронтами.

Описанные правила формирования прямых и обратных фронтов проиллюстрированы на рис. 3 на примере двумерного ОММК.

Рис. 3. Порядок формирования прямых и обратных фронтов для двумерного ОММК

Пусть для фронта С/ в текущий момент времени активным будет виртуальный слой К\, Тогда для фронта С/41 активным считается слой , если

г < р, и слой К), если г = р. Для фронта С/~', таким образом, активным будет слой

К[ 1 при г > 1 и слой К[ при г = 1. Аналогично определяется активность виртуальных слоев и для обратных фронтов. Отметим, что в пределах одного фронта (прямого или обратного) во всех ячейках активен один и тот же виртуальный слой.

Описанный порядок активизации виртуальных слоев иллюстрируется на примере среды синхронизации двумерного ОММК в конфигурации 4x4 при р = 5 (см. рис. 4). Активные виртуальные ячейки и связи выделены жирными линиями. Из рисунка следует, что в каждой физической ячейке происходит последовательное циклическое переключение виртуальных слоев, причем в _ , гт пределах одного фронта переключения

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

двумерного ОММК ковым номером переключаются с !запаз-

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

С учетом особенностей разработанного механизма виртуализации координирующей среды текущее состояние произвольного модуля т{х„хг,...,х„) по отношению к барьеру а1 определяется в следующем виде:

г^--""' (г) =

= (8)

где г, е {1,2,...,р) - номер активного виртуального слоя для фронта С/, содержащего ячейку с, О,, х2,..., Х<1 ); г] е (1,2,..., р) - номер виртуального слоя, на который назначен барьер а<^(7) отражает состояние ветви Вк^(а,), выполняемой модулем т(хх,х2,...,х,). Согласно формуле (8) = если активен виртуальный

слой, на который назначен ¿-й барьер, при этом модуль т(х1,х2,...,ха) уже не выполняет ветвь Вк eJ(as) либо данный модуль вообще не является участником барьерной группы. Иными словами, состояние ветви Вк учитывается только при совпадении номеров двух виртуальных слоев - активного для ячейки с,(х1,х2,...,х ) и соответствующего барьеру а5.

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

/ / /

\ / 1

А ✓ / /

✓ \ /

X /■ /

/ N /

/ ✓ \ /

✓ <Г \ / / / /

У

/ / \

л\ ✓ /

/ \ / /

/ /Г ✓ X /

¿4 ✓ / / \ /

? / У

/ / / у \ /

/ / А/

✓ / /• / л / 1

У

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

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

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

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

Функциональная схема разработанной ячейки изображена на рис. 6, где жирными линиями выделены блоки элементов и шины, латинскими буквами обозначены входы и выходы ячейки. Дополнительно входы и выходы размечены наименованиями переменных и функций, которые на них подаются или с них снимаются. Через к'(х1,х2,..,,Х11) и п"(х1,х1,..,,хс1) на рис. 6 обозначены координатные признаки текущего модуля, а(х,,л;2,...,л^) - признак активизации текущего модуля, и С1УЛ - волны тактовых импульсов в сетях синхронизации и восстановления соответственно, /г^Л'-^* и у<*|.х2-л> _ номера текущих физического и виртуального слоев соответственно, Утю - максимальный номер используемого виртуального слоя, И0 — сигнал системного сброса.

Значения признаков п'(х1,х2,...,х,1') определяются выражениями:

, . Г1, если х, = х2 = ... = хЛ = 1;

тг{х1,х2,...,х„) = \

[О для всех остальных модулей,

Г1,если(х1=Аг1)л(х2 = Аг2)л...л(х,,=Л',);

71 [Х1,Х2,...,Х1/) — <

[О для всех остальных модулей.

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

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

Е0 =3[к^2 п\п +2)+2[1с^2 /1(4р+15) + р(23п-2) +2п(с1+1) +20. (9) Единицей изменения величины Е0 является эквивалентный вентиль (ЭВ) - двухвхо-довый вентиль, реализующий любую булеву функцию двух переменных из множества {И, ИЛИ, И-НЕ, ИЛИ-НЕ}.

В табл. 1 представлены значения аппаратной сложности Е координирующей среды двумерного матричного мультикомпьютера (с1 = 2), полученные на основе формулы (9): Е = N¡N2Ea. Значения выражены в ЭВ и получены в предположении, что N. = N..

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

Анализ данных, сведенных в табл. 1, показывает, что координирующая среда на основе разработанной ячейки во всех практически значимых случаях реализуется на одной микросхеме. При этом аппаратная сложность отдельной ячейки остается в пределах 30 тысяч ЭВ, что на два-три порядка ниже логической емкости современных микросхем.

Таблица 1

п,р

4 8 16 32 64 128

4, 4 9792 39168 156672 626688 2506752 10027008

8, 8 31872 127488 509952 2039808 8159232 32636928

16, 16 112192 448768 1795072 7180288 28721152 114884608

32, 32 416384 1665536 6662144 26648576 106594304 426377216

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

сти характеристик гибкости предложенный подход превосходит лучшие известные аналоги (методы, отмеченные символом *, относятся к подклассу гибридных). ___ _ ___ _ Таблица 2

Наименование метода или решения Инвариантность к конфигурации барьерных групп Масштабируемость Расширяемость на случай ¿-мерной матрицы

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

Распределенный аппаратный барьер Delgado-Kofiiji Не обеспечивается (барьерные группы должны размещаться в прямоугольных сплошных областях матрицы) Средняя (жесткое ограничение на число параллельно выполняемых барьеров) Средняя. Применим только к двумерным матрицам

MDBS-сеть Частичная(синхронизируемые процессы должны быть размещены в соседних процессорах) Хорошая (ограничено число барьеров в системе) Средняя. Применима только к двумерным матрицам

Метод многоадресных пакетов Panda« Полная Средняя (длина сообщения сильно зависит от мощности барьерных групп) Хорошая. Нет ограничений

Барьерное дерево ВТМ* Полная Хорошая (ограничено число барьерных регистров) Средняя. Применимо только к двумерным матрицам

Синхронизатор DVBSS Полная Средняя (наличие физических обратных связей между угловыми модулями матрицы усложняет расширение системы) Хорошая. Нет ограничений

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

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

Оценка среднего времени синхронизации Дг выполнялась на основе имитационного моделирования. Моделирование проводилось только для двумерного ОММК, поскольку реализация СБИС-систем более высокой размерности на данном этапе затруднительна. Исследования осуществлялись в предположении, что N1 = Ы2, а количество синхронизируемых и активизируемых ветвей для каждого барьера одинаково. Число синхронизируемых / активизируемых ветвей при этом выбиралось из диапазона от 2 до N = 2, а их распределение между модулями мультикомпьютера варьировалось равновероятно. Время распространения значений индикаторных функций через ячейку, а также моменты завершения ветвей множеств J (аз) определялись согласно усеченному нормальному распределению. Каждое значение величины А1 рассчитывалось путем усреднения по 500 итерациям, что обеспечило достаточную точность с учетом методической погрешности имитационного моделирования.

Моделирование позволило подтвердить, что среднее время синхронизации At слабо зависит от разрядности координирующей среды п, поскольку физические слои практически не оказывают влияния друг на друга. График зависимости величины At от глубины виртуализации координирующей среды р приведен на рис. 7. Зависимость соответствует мультикомпьютеру с организацией 8x8 и получена в предположении, что задержка одного ЭВ составляет в среднем 1 не, а время обмена данными между процессорным модулем и ячейкой не превышает 150 не (определено экспериментально).

Анализ этой зависимости показывает, что она с достоверно-

1 л 4 ^ О / в Ci 1011 11-сч

стью прогнозирования не менее

0,98 близка к линейной. Таким „ , ^ .

обпазом для всех ппяктиw«-™ График зависимости среднего времени синхронизации

uupajoM, для всех практически от пЫзины Вфт\'ализации координирующей среды

достижимых значений р среднее

время синхронизации не превышает 20-30 мкс. В то же время при малых значениях р (9 и меньше) оно не превосходит 10 мкс. Указанные значения соизмеримы с оценками времени синхронизации, полученными при аналогичных допущениях для известных аппаратных и гибридных методов барьерной синхронизации.

На рис. 8 представлены графики зависимости среднего времени синхронизации At от числа модулей в составе мультикомпыотера N, полученные при различ-t, мкс ных значениях р. Из рис. 8 следует, что

для максимально возможных на текущий момент конфигураций ОММК (10x10 -система TILE-Gxl00) значения At не превышают 20^-25 мкс при любых практически обоснованных значениях р.

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

В приложениях приведен листинг

программного модуля имитационного

25 81 169 289 441 625 841 1089 и моделирования, а также представлены

Рис. S. Графики зависимости среднего времени синхронизации аКТЫ О ВНвДреНИИ результатов ДИССврТа-

сп числа процессоров в состаэе ОММК при различной глубине „„„ „„ ,,„„„,,„„„„,,_____ „

шртуализацни координирующей среды

ЧИП и а предприятиях и в учеоныи процесс.

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

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

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

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

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи по перечню ведущих рецензируемых научных журналов и изданий

1. Аппаратная реализация барьерной синхронизации в матричных мультикомпьютерах [Текст] / И.В.Зотов, А.А.Бурмака, Р.В.Бредихин, Ю.О.Сухочев И Информационно-измерительные и управляющие системы. 2013. №8. С. 41-45.

2. Бредихин, Р.В. Об организации встроенного аппаратного взаимоконтроля в логических мультиконтроллерах [Текст] / Р.В.Бредихин, Ньян Лин, ИВ.Зотов // Изв. Вузов. Приборостроение 2013. Т.56,№6. С. 44-49. ' 1

3. Принципы организации встроенного аппаратного межмодульного взаимоконтроля в матричных логических мультиконтроллерах [Текст] / И.В.Зотов, Р.В.Бредихин, Л.А.Лисицин, Ньян Лин // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение. 2013. №1. С. 202-208.

4. Аппаратно-ориентированные методы управления межпроцессорной координацией в параллельных системах с распределенной памятью [Текст] / И.В.Зотов, ДО.Бобынцев, Р.В.Бредихин, Ньян Лин // Известия Юго-Западного государственного университета. Серия: Управление^ вычислительная техника, информатика. Медицинское приборостроение. 2013. №1. С. 43-48.

5. Бредихин, Р.В. Распределенная процедура циклической барьерной синхронизации для однокристальных матричных мультикомпьютеров [Текст] / Р.В.Бредихин, И.В.Зотов // Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика Медицинское приборостроение. 2012. №2. Ч. 1. С. 48-54.

Стать я в международном рецензируемом научном издании

6. Bredikhin, R.V. A distributed parallel pipelined hardware-level barrier synchronization method for mesh-connected multicomputer [Text] / Igor V. Zotov, Ruslan V. Bredikhin, Evgeni A Titenko // International Review on Computers and Software (I.RE.CO.S.). September 2013. Vol.8. No 9. PP. 2254-2261.

Материалы конференций

7. Бредихин, Р.В. Распределенная координирующая среда матричного мультиконтроллера с многослойными виртуальными каналами [Текст] / Р.В.Бредихин, М.Е.Леонов, И.В.Зотов // Информационные системы и технологии: материалы докладов I Региональной научно-технической конференции. Курск, 2012. С. 197-199.

8. Макаров, Д. И. Модель ячейки координирующей среды мультиконтроллера с интегрированными средствами аппаратного контроля модулей [Текст] / Д.И.Макаров, Р.В.Бредихин И.В.Зотов // Информационные системы и технологии: материалы докладов I Региональной научно^ технической конференции. Курск, 2012. С. 56-59.

9. Бредихин, Р.В. Организация барьерной ринхронизации в матричных мультикомпьютерах на основе виртуально-многослойной конвейерной координирующей среды [Текст] / Р.В.Бреднхин, И В. Зотов, Ю.О.Сухочев // Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации: материалы Международной научно-технической конференции. Курск, 2013. С. 232-235.

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

10. Свидетельство об официальной регистрации программы для ЭВМ №2011612774 / Бредихин Р.В. и др. заявл. 14.02.2011; per. 06.04.2011.

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