Размещено на http://www.allbest.ru/

АВТОРЕФЕРАТ

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

кандидата технических наук

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

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

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

и систем управления

Курск - 2014

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

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

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

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

Заслуженный деятель науки РФ

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

Минайлов Виктор Викторович

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

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

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

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

Автореферат разослан «___»____________2014 г.

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

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

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

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

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

Вопросами организации межпроцессорного взаимодействия в параллельных системах занимались многие отечественные и зарубежные ученые, в частности, А.В. Каляев, И.В. Каляев, В.В. Воеводин, Вл.В. Воеводин, А.В. Корнеев, И.И. Левин, А.П. Типикин, И.В. Зотов, 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 порядка медленнее по сравнению аппаратно реализованными процедурами и поэтому не нашли применения в мультикомпьютерах. Гибридный подход к барьерной синхронизации предполагает введение незначительных расширений в структуру стандартных коммуникационных аппаратных средств (например, барьерных регистров и логических схем), которые не меняют архитектуры коммуникационной среды вычислительной системы. Аппаратные решения, в противоположность гибридным, предусматривают введение отдельной управляющей коммуникационной сети, логически отображенной на стандартную (базовую) коммуникационную среду системы. Эта управляющая сеть может иметь такую же топологию, что и базовая среда, но может и отличаться от неё по топологии.

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

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

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

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

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

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

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

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

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

Синхронизация ветвей считаетсяобеспеченной, если в некоторый момент , , выполняется условие синхронизации:

, (1)

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

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

. (2)

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

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

,

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

Пусть - некоторая ветвь, назначенная на модуль . Тогда состояние модуля по отношению к барьеру представляется следующим образом:

, (3)

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

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

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

;

.

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

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

Логика функционирования ячеек в фазе синхронизации определяется выражением

, (4)

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

Логика функционирования ячеек в фазе восстановления определяется формулой

, (5)

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

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

; (6)

. (7)

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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

(8)

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

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

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

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

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

Значения признаков определяются выражениями:

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

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

. (9)

Единицей изменения величины является эквивалентный вентиль (ЭВ) - двухвходовый вентиль, реализующий любую булеву функцию двух переменных из множества {И, ИЛИ, И-НЕ, ИЛИ-НЕ}.

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

Рис. 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 содержатся результаты сравнительной оценки гибкости разработанных аппаратных средств. В качестве характеристик гибкости выбраны инвариантность к конфигурации барьерных групп, масштабируемость координирующей среды и расширяемость на случай d-мерной матрицы. Из табл. 2 видно, что по совокупности характеристик гибкости предложенный подход превосходит лучшие известные аналоги (методы, отмеченные символом *, относятся к подклассу гибридных).

Таблица 2

Наименование методаили решения	Инвариантность к конфигурации барьерных групп	Масштабируемость	Расширяемость на случай d-мерной матрицы
Древовидная барьерная сеть CM-5	Не обеспечивается (допускаются только барьерные группы мощностью степени двойки).	Плохая (при добавлении новых процессоров в систему нужна полная перестройка барьерной среды).	Плохая. Плохо согласуется с матричной топологией.
Распределенный аппаратный барьер Delgado-Kofuji	Не обеспечивается (барьерные группы должны размещаться в прямоугольных сплошных областях матрицы).	Средняя (жесткое ограничение на число параллельно выполняемых барьеров).	Средняя. Применим только к двумерным матрицам.
MDBS-сеть	Частичная (синхронизируемые процессы должны быть размещены в соседних процессорах).	Хорошая (ограничено число барьеров в системе).	Средняя. Применима только к двумерным матрицам.
Метод многоадресных пакетов Panda*	Полная.	Средняя (длина сообщения сильно зависит от мощности барьерных групп).	Хорошая. Нет ограничений.
Барьерное дерево BTM*	Полная.	Хорошая (ограничено число барьерных регистров).	Средняя. Применимо только к двумерным матрицам.
Синхронизатор DVBSS	Полная.	Средняя (наличие физических обратных связей между угловыми модулями матрицы усложняет расширение системы).	Хорошая. Нет ограничений.
Предлагаемый подход	Полная.	Хорошая (ограничено число физических слоев координирующей среды).	Хорошая. Нет ограничений.

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

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

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

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

На рис. 8 представлены графики зависимости среднего времени синхронизации от числа модулей в составе мультикомпьютера N, полученные при различных значениях p. Из рис. 8 следует, что для максимально возможных на текущий момент конфигураций ОММК (10Ч10 - система TILE-Gx100) значения не превышают 20ч25 мкс при любых практически обоснованных значениях p.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размещено на Allbest.ru