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

Апробация работы. Основные положения и результаты диссертационной работы были заслушаны и получили одобрение на Международной научно-технической конференции «Распознавание – 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-м измерении, . Модуль с порядковым номером будем условно обозначать как .