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




Скачать 338.53 Kb.
страница 1/2
Дата 26.09.2016
Размер 338.53 Kb.
  1   2


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

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

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

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

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

Аппаратные методы и средства барьерной синхронизации уже нашли применение в первых коммерческих мультикомпьютерах (Cray T3D, Thinking Machines CM-5, Fujitsu AP1000). Однако ввиду наличия жестких ограничений на конфигурацию барьерных групп и/или количество барьеров в параллельных программах их эффективное применение в современных и перспективных системах, в т.ч. ОММК, в соответствии со стандартом 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). Активные виртуальные ячейки и связи выделены жирными линиями. Из рисунка следует, что в каждой физической ячейке происходит последовательное циклическое переключение виртуальных слоев, причем в пределах одного фронта переключения осуществляются синхронно. В то же время ячейки фронта с меньшим порядковым номером переключаются с запаздыванием относительно текущего фронта, а ячейки фронта с большим порядковым номером, наоборот, – с опережением. Величина запаздывания / опережения (в тактах) пропорциональна разности номеров фронтов. Аналогично происходит активизация виртуальных слоев в сети восстановления.

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

(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
  1   2


База данных защищена авторским правом ©infoeto.ru 2022
обратиться к администрации
Как написать курсовую работу | Как написать хороший реферат
    Главная страница