Содержание к диссертации
Введение
1. Архитектура и координационные процессы однокристальных матричных мультикомпьютеров 10
1.1. Особенности архитектуры однокристальных матричных мультикомпьютеров 10
1.2. Координационные процессы в мультикомпьютерах. Процедура барьерной синхронизации 13
1.3. Методы, процедуры и средства барьерной синхронизации 17
Выводы 31
2. Организация барьерной синхронизации на основе виртуально-многослойной конвейерной координирующей среды 32
2.1. Принципы организации виртуально-многослойной координирующей среды 32
2.2. Концептуальный базис разработанного метода барьерной синхронизации 34
2.3. Особенности разработанного метода барьерной синхронизации 41
2.3.1. Определение индикаторных функций и условий синхронизации 41
2.3.2. Определение топологии физических слоев координирующей среды 44
2.3.3. Определение логической конфигурации физических слоев координирующей среды 46
2.3.4. Виртуализация физических слоев координирующей среды 51
2.3.5. Определение логической конфигурации виртуальной координирующей среды 55
2.3.6. Организация тактовой синхронизации виртуальной координирующей среды 61
2.3.7. Инвариантность разработанного метода к конфигурации барьерных групп 63
Выводы 65
3. Структурно-функциональная организация распределенной координирующей среды с виртуальными каналами 67
3.1. Синтез базовой схемы ячейки координирующей среды 67
3.2. Синтез схемы ячейки координирующей среды с виртуальными каналами 70
3.3. Синтез схемы ячейки координирующей среды с многоразрядными виртуальными каналами 77
3.4. Оценка аппаратной сложности ячейки координирующей среды и гибкости разработанных аппаратных средств 93
Выводы 99
4. Исследование функционирования разработанной ячейки в составе координирующей среды матричного мультикомпьютера 100
4.1. Методика проведения исследований 100
4.2. Особенности используемого языка имитационного моделирования 102
4.3. Особенности используемых инструментальных средств имитационного моделирования 104
4.4. Результаты имитационного моделирования 110
Выводы 113
Заключение 114
Библиографический список
- Координационные процессы в мультикомпьютерах. Процедура барьерной синхронизации
- Особенности разработанного метода барьерной синхронизации
- Синтез схемы ячейки координирующей среды с многоразрядными виртуальными каналами
- Особенности используемых инструментальных средств имитационного моделирования
Координационные процессы в мультикомпьютерах. Процедура барьерной синхронизации
За последние три десятилетия было разработано широкое многообразие методов, способов и средств барьерной синхронизации, используемых на раз-личных уровнях параллелизма и ориентированных на параллельные вычисли-тельные системы разных архитектурных классов. В зависимости от уровня реа-лизации существующие решения можно разделить на три класса [15]: про-граммные [22, 34, 35, 36, 54, 63, 64, 72, 75, 76, 80, 99, 103, 104], гибридные (про-граммно-аппаратные) [23, 24, 30, 31, 32, 46, 50, 62, 65, 74, 77, 86, 88, 90, 92, 94, 102] и аппаратные [1, 8, 9, 10, 16, 25, 26, 27, 28, 29, 30, 33, 44, 45, 47, 48, 55, 56, 58, 59, 60, 61, 66, 69, 70, 71, 73, 78, 82, 83, 87, 89, 91, 101, 106]. Программные решения полностью базируются на использовании стандартного коммуникаци-онного оборудования и протоколов и обычно представляются в виде набора специализированных системных утилит. Будучи весьма гибкими, масштаби-руемыми и простыми, программно реализованные процедуры барьерной син-хронизации, как правило, на 1-3 порядка медленнее аппаратно реализованных процедур и поэтому не нашли применения в мультикомпьютерах. В связи с этим в дальнейшем мы исключаем из рассмотрения методы синхронизации, предполагающие чисто программное воплощение.
Гибридный подход к барьерной синхронизации предполагает введение незначительных расширений в структуру стандартных коммуникационных ап-паратных средств (например, барьерных регистров и логических схем), которые не меняют архитектуры коммуникационной среды вычислительной системы. Аппаратные решения, в противоположность гибридным, предусматривают вве-дение отдельной управляющей коммуникационной сети, логически отображен-ной на стандартную (базовую) коммуникационную среду системы. Эта управ-ляющая сеть может иметь такую же топологию, что и базовая среда, но может и отличаться от неё по топологии.
Многие известные методы барьерной синхронизации, ориентированные на матричные мультикомпьютеры рассматриваемого класса, предполагают гиб-ридную реализацию [23, 24, 30, 31, 32, 46, 50, 62, 65, 74, 77, 86, 88, 90, 92, 94, 102]. Гибридные решения, как правило, базируются на стандартных коммуни-кационных протоколах, определяющих функционирование типовых коммуни-кационных сетей, и используют специализированные аппаратные средства на уровне отдельных узловых маршрутизаторов. Они имеют распределенный ха-рактер и топологически согласованы с вычислительной системой, что позволя-ет достичь высокой масштабируемости и гибкости среды барьерной синхрони-зации. Узким местом гибридных решений является существенный дополни-тельный трафик, снижающий реальную пропускную способность коммуника-ционной сети.
Основным способом сокращения дополнительного служебного трафика является объединение процессов-участников барьерной синхронизации в логи-ческие структуры (например, деревья) таким образом, чтобы каждый процесс взаимодействовал с как можно меньшим числом других участников. В сочета-нии с механизмом многоадресных сообщений [86], гибридный подход к барь-ерной синхронизации обеспечивает малые значения среднего времени синхро-низации, которые во многих случаях приемлемы для практики, а также его хо-рошую асимптотику. Недостатками гибридного подхода являются: большие временные затраты на формирование и удаление барьерных групп; значитель-ный слабо прогнозируемый поток служебных сообщений, не несущих никаких данных, обрабатываемых процессорными модулями (который стремительно возрастает с увеличением числа барьеров в программе и числа участников ба-рьерных групп); сложность гарантировать отсутствие блокировок и дисбаланса в коммуникационной сети.
Методы барьерной синхронизации, ориентированные на аппаратную реа-лизацию, не предполагают выдачи дополнительных служебных сообщений в базовую коммуникационную сеть мультикомпьютера, поскольку управляющие межпроцессорные взаимодействия осуществляются через отдельную барьер-ную сеть (которая, как правило, многократно проще базовой сети). Для под-держки барьерной синхронизации на уровне каждого модуля вводятся специ-альные логические схемы и регистры, подключенные к барьерной сети. Разли-чия между аппаратными решениями определяются главным образом топологи-ей барьерной сети, а также логическими функциями объединения барьерных сигналов. В их основе может лежать сеть с шинной [70, 91], кольцевой [71], матричной [1, 8, 9, 16, 29, 48, 58, 101] или древовидной [60, 66, 82, 83] тополо-гией либо их комбинация [56, 87].
Аппаратные средства барьерной синхронизации уже нашли применение в ряде коммерческих систем, например, в системах Thinking machines CM-5 [57] и Cray T3D [73]. Так, барьерная среда системы CM-5 [57] организована в виде двух одноразрядных бинарных деревьев. Одно из них функционирует только в фазе ожидания (дерево ожидания), а другое в фазе активизации (дерево активи-зации). С целью поддержки параллельных барьеров в CM-5 используется набор одновременно работающих «древовидных» барьерных сред. Каждая среда ста-вится в соответствие определенной группе синхронизируемых параллельных процессов. Любая группа может динамически разбиваться на группы меньшей мощности, и наоборот, любые группы могут объединяться в группы большей мощности. При разбиении и объединении групп происходит разделение и со-единение барьерных сред. Аналогичным образом организована барьерная среда параллельной системы Cray T3D [73].
Организация элементарной (одноразрядной) барьерной среды системы CM-5 представлена на рис. 1.2 (в данном случае рассматривается 8-процессорная конфигурация). Дерево ожидания среды состоит из элементов И, а дерево активизации – из повторителей (D). Каждый процессорный модуль связан с деревом ожидания через флаг готовности x. Этот флаг устанавливается в единичное состояние в момент завершения модулем параллельной ветви и сбрасывается по окончании текущего барьерного эпизода. Эпизод считается завершенным, как только по сигналу из дерева активизации будет установлен флаг запуска z.
При разбиении барьерной группы на подгруппы осуществляется разделе-ние барьерной среды на фрагменты. Разделение обеспечивается перекоммута-цией некоторых связей в деревьях ожидания и активизации, в результате чего формируется множество не связанных друг с другом пар поддеревьев. Процесс разделения иллюстрируется схемой, отражающей разбиение группы ветвей на три подгруппы и изображенной на рис. 1.3.
Особенности разработанного метода барьерной синхронизации
Идея применения виртуально-многослойной координирующей среды для аппаратной поддержки барьерной синхронизации в мультикомпьютерах впер-вые нашла свое отражение в работах [11, 106]. Однако авторам не удалось рас-пространить данную идею на однокристальные системы, поскольку предло-женная ими организация ВМКС с множеством «длинных» обратных связей ме-жду «угловыми» модулями матричной структуры сложна для размещения на кристалле. Кроме того, подобные обратные связи вносят дополнительную за-держку в процесс распространения координирующих сигналов и увеличивают среднее время синхронизации. Применение такой организации ВМКС в круп-номасштабных системах (не СБИС) также сопряжено с определенными трудно-стями. В частности, существенно усложняется добавление в мультикомпьютер новых процессорных модулей из-за необходимости физической перекоммута-ции обратных связей. В данном разделе излагается новый метод барьерной синхронизации на основе ВМКС, позволяющий преодолеть указанные недостатки известного подхода.
Виртуально-многослойная координирующая среда представляет собой сеть из однотипных ячеек, называемых барьерными модулями. Каждый барьер-ный модуль соответствует «своему» процессорному модулю мультикомпьюте-ра, при этом топология ВМКС в значительной степени либо полностью совпа-дает с топологией ОММК. Барьерный модуль решает следующие основные за-дачи: 1) хранит данные об отображении барьеров, входящих в реализуемые па-раллельные программы, на ВМКС; 2) фиксирует признаки завершения парал-лельных процессов соответствующим ему процессорным модулем; 3) управля-ет распространением двоичных сигналов, отражающих состояние всех выпол-няемых мультикомпьютером барьеров (завершен / не завершен); 4) обеспечива-ет запуск данного процессорного модуля при завершении ожидаемого барьера.
Барьерные модули имеют секционированную физическую организацию. Все секции идентичны и функционируют параллельно. В любой момент време-ни секция способна работать лишь с одним барьером, но при этом последова-тельно выполняющиеся барьеры (синхронизация которых осуществляется в разное время) могут назначаться на одну и ту же секцию. Совокупность секций всех барьерных модулей с соответствующими связями образует одноразрядный слой ВМКС. Организованная таким образом координирующая среда способна синхронизировать до n параллельных барьеров, где n – число секций в барьер-ных модулях (или число слоев координирующей среды). Число синхронизи-руемых последовательно выполняемых барьеров не ограничено. Для преодоления ограничения на максимально возможное число синхро-низируемых параллельных барьеров (которое свойственно известным методам распределенной барьерной синхронизации) каждому слою ВМКС ставится в соответствие множество виртуальных слоев, каждый из которых по своим воз-можностям идентичен физическому слою. В результате на каждую секцию ка-ждого барьерного модуля отображаются виртуальные секции, входящие в соот-ветствующие виртуальные слои. Виртуальная секция способна работать лишь с одним барьером одновременно. Это же справедливо и для соответствующего виртуального слоя в целом. Однако физический слой при такой организации координирующей среды способен одновременно работать с несколькими барь-ерами, в том числе и параллельными. С другой стороны, в пределах всей коор-динирующей среды в одном физическом слое активны сразу несколько вирту-альных слоев. Их активность обеспечивается конвейерным переключением виртуальных секций в физических барьерных модулях. Тактовая синхрониза-ция этого процесса обеспечивается путем параллельного распространения «волн» тактовых импульсов от одного углового модуля ОММК через всю мат-рицу к другому угловому модулю и одновременно в обратном направлении (например, от левого верхнего к правому нижнему и обратно, если речь идет о двумерной матричной топологии).
Для формализации описания созданного метода барьерной синхрониза-ции условимся использовать концептуальный базис и обозначения, введенные в монографии [11]. Структуру ОММК представим в виде графа , где – мно-жество вершин, соответствующее множеству процессорных модулей мульти-компьютера, а – множество дуг, отражающее связи между модулями. Для ка-ждого модуля зададим составной порядковый номер вида , , где – число процессоров в i-м измерении, . Модуль с поряд-ковым номером будем обозначать как . При такой нумерации процессоров вершины, соответствующие модулям и , будут связаны в графе H ребром, если и только если: .
Иными словами, вершины будут связаны ребром лишь тогда, когда порядковые номера соответствующих модулей отличаются на 1 в единственном измерении.
Мультикомпьютер, представленный описанным способом, условно обо-значим через . ОММК выполняет множество параллельных программ , которые могут быть загружены и активизированы одновременно либо посту-пать в систему в определенном порядке. В дальнейшем условимся рассматри-вать одну из программ множества , например, некоторую программу , при этом действие всех теоретических положений будем распространять на любую программу из . Пусть программа представлена параллельной граф-схемой (ПарГСА) с множеством операторных и условных вершин и с множеством дуг , причем на множестве заданы отношения сле-дования , связи , альтернативы и параллельности [2].
Каждой паре множеств такой, что , соответст-вует некоторый барьер программы. Однако, парам множеств , для кото-рых , не соответствует никаких барьеров. В связи с этим поставим в соответствие таким парам фиктивные барьеры. Мно-жество всех барьеров, в том числе фиктивных, обозначим через . При этом -множество ветвей, соответствующее барьеру , будем обозначать как , а -множество – . Каждую ветвь программы будем представлять текущим состоянием: «ак-тивна» либо «пассивна». Состояние «активна» означает, что данная ветвь вы-полняется в соответствующем модуле в текущий момент времени, а состояние «пассивна» говорит о том, что ветвь не выполняется. Если ветвь не входит в циклы, то ее «пассивность» означает, что она еще не выполнялась вовсе или уже завершена; если ветвь находится внутри циклов, то ее «пассивность» будем рассматривать только в рамках одной итерации самого вложенного цикла. Формально состояние любой ветви условимся задавать индика-торной функцией: , если ветвь в момент времени активна (т.е. вы-полняется в некотором модуле), иначе.
Синтез схемы ячейки координирующей среды с многоразрядными виртуальными каналами
Виртуализация физического слоя , как показано на рис. 2.9, обеспечи-вается введением статического регистра, состоящего из p триггеров. Триггеры содержат текущие значения индикаторных функций для всех барьеров , назначенных на виртуальные слои . Коммутирую-щие элементы DX и MX реализуют функции ячеек и соответственно. Вход T служит для приема тактовых импульсов для управления записью данных в триггеры. Правила и схемы формирования значений а также механизм тактовой синхронизации рабо-ты координирующей среды подробно рассматриваются в дальнейшем.
При текущий модуль не влияет на значения индикаторных функций ( ). Их новые значения формируются объединением по И значений, приходящих от соседних модулей, и заносятся в соответствующие триггеры (согласно номеру активного виртуального слоя). При значение индикаторной функции определяется состоянием ветви , выпол-няемой текущим модулем, причем оно учитывается только в тот момент, когда активен требуемый виртуальный слой ( ). Полученное значение заносится в -й триггер (если ветвь не завершена, то ноль, если завершена, то едини-ца). Логика работы ячейки в составе сети восстановления в це-лом аналогична и может быть описана схемой, изображенной на рис. 2.10. На-значение элементов этой схемы не отличается от вышеприведенной схемы (см. рис. 2.9).
Организация тактовой синхронизации виртуальной координирующей среды С целью обеспечения согласованной работы ячеек координирующей сре-ды с учетом виртуализации физических слоев необходима разработка соответ-ствующего механизма их тактовой синхронизации. Одним их подобных меха-низмов является распределенная синхронизация циркулирующими волнами тактовых импульсов (DCW-clocking), описанная в работе [106]. Непосредствен-ное использование DCW-синхронизации в нашем случае не представляется возможным из-за различия топологических структур координирующей среды, поэтому примем этот подход за основу и разработаем на его базе модифициро-ванный распределенный механизм тактовой синхронизации, применимый к ОММК произвольной размерности.
Сущность предлагаемого модифицированного механизма DCW-синхронизации заключается в следующем. Серии тактовых импульсов от про-цессорных модулей и передаются в координирую-щую среду и независимо распространяются по прямым и обратным фронтам со-ответственно. Появление тактовых импульсов в ячейках некоторого фронта (прямого или обратного) взаимно синхронизировано, что обеспечивает одновре-менное их переключение. От ячейки прямого фронта тактовый импульс пе-редается в соседние ячейки, входящие в следующий прямой фронт , а от ячейки обратного фронта – соседям, входящим в обратный фронт . По-сле прохождения через все фронты импульсы прекращают распространение. Та-ким образом, процесс продвижения тактовых импульсов через координирующую среду напоминает распространение двух серий «волн» синхроимпульсов. Первая серия распространяется от модуля в направлении модуля и обеспечивает переключение ячеек сети синхронизации, а вторая серия движется от модуля в направлении модуля и управляет переключением ячеек сети восстановления. Частота сле-дования волн тактовых импульсов может быть установлена произвольным обра-зом на основе деления системной тактовой частоты процессорных модулей схематично иллюстрирует порядок распространения тактовых импульсов в координирующей среде двумерного ОММК в соответствии с раз-работанным механизмом тактовой синхронизации (здесь представлено распро-странение импульсов в сети синхронизации, для сети восстановления порядок аналогичен с точностью до направления следования волн). Для упрощения на данном рисунке отдельные ячейки отображены квадратами, а связи между ни-ми условно не показаны. Подобный порядок передачи тактовых импульсов ячейкам координи-рующей среды позволяет организовать конвейерное переключение виртуаль-ных слоев и тем самым ускорить процесс барьерной синхронизации. При дос-таточно высокой частоте следования тактовых импульсов и, соответственно, при большом числе волн, покрывающих матрицу ОММК, один и тот же вирту-альный слой может быть одновременно активен в ячейках нескольких фронтов.
Особенности используемых инструментальных средств имитационного моделирования
Первоначально текущий модуль не входит ни в одну барьерную группу, поэтому регистр 1.3 данной ячейки содержит только еди-ничные значения. При формировании очередной барьерной группы выделяется физический слой и первый свободный виртуальный слой в нем, в которых будет протекать барьерная синхронизации ветвей указанной группы (в целях повышения скоро-сти работы координирующей среды первоначально заполняется первый вирту-альный слой всех физических слоев, затем второй, и т.д. до заданного значения p). Эти процессы протекают под управлением распределенной операционной системы, которая ведет журнал соответствия коммуникаторов (номеров барь-ерных групп) слоям координирующей среды. В журнале для каждого коммуни-катора хранится пара номеров соответствующих слоев – физического и виртуального . По завершении формирования барьерной группы номер физического слоя записывается в регистр 1.6, а номер виртуального слоя – в регистр 1.5. Кроме того, в регистре 1.3 происходит обнуление бита , соответствующего паре слоев и . Таким образом индициру-ется участие данного модуля в сформированной барьерной группе. Одновре-менно в регистр 1.4 заносится максимальный номер виртуального слоя . Первоначально , однако как только достигнет текущее значе-ние , в регистр 1.4 всех ячеек будет записано увеличенное на 1 значение. Управление величиной также возлагается на операционную систему. Зна-чение из регистра 1.4 поступает на информационные входы счетчиков 4.1 и 4.2 и устанавливает для них новые коэффициенты пересчета. Так как перво-начально , счетчики 4.1 и 4.2 будут сохранять нулевое состояние. В дальнейшем, когда превысит 1, счетчики будут переключаться импульсами волн и , чем будет обеспечиваться последовательный перебор номе-ров активных виртуальных слоев. При удалении барьерной группы в регистре 1.3 происходит установка би-та , соответствующего паре слоев и , в единицу. В регистры 1.6 и 1.5 при этом заносятся номера слоев для очередной барьерной группы, в которой будет участвовать текущий модуль, либо нули, если такой группы нет. Если при удалении барьерной группы максимальный номер ис-пользуемого виртуального слоя становится меньше , то в регистры 1.4 всех ячеек записывается уменьшенное на 1 значение . В результате коэф-фициент пересчета счетчиков 4.1 и 4.2 уменьшится на 1.
Рассмотрим работу ячейки в режиме индикации окончания параллельной ветви. Сразу после выполнения параллельной ветви , завершающейся неко-торым барьером , процессорный модуль выдает в ячейку единичное значение признака . В результате триггер 7.3 переводится в состояние логической единицы. Сигнал с прямого выхода данного триггера открывает элементы И 14.1, 14.2 и блок элементов И 11. Как только номер активного виртуального слоя для фазы синхронизации из счетчика 4.1 становится равным но-меру текущего виртуального слоя из регистра 1.5, компаратор 6.1 вы-дает единичный сигнал. Этот сигнал проходит через открытый элемент И 14.1 и разрешает работу дешифратора 5.2. Далее на том выходе дешифратора 5.2, ко-торый соответствует текущему физическому слою , появляется еди-ница. Эта единица через соответствующий элемент блока 17 проходит на одно-именный элемент блока 13. До появления единицы, на выходе блока элементов ИЛИ 17 находится нулевой уровень сигнала ( ), снимаемый через буфер 8.i с соответствующего разряда регистра 1.3.
Во всех ячейках, кроме , указанный элемент блока 13 безус-ловно открывается, чем обеспечивается формирование единичного значения , как только единицы поступят на все входы A.1, A.2, …, A.d. В ячей-ке блок элементов И 13 дополнительно блокируется сигналом с вы-хода блока элементов ИЛИ 16 до тех пор, пока мультиплексор 3.2 в соответст-вующем разряде не выдаст нулевое значение.
В этом режиме триггер 7.3 по-прежнему находится в единичном состоя-нии, поэтому элемент И 14.2 и блок элементов И 11 открыты. Как только ком-паратор 6.2 устанавливает совпадение номера текущего виртуального слоя с номером активного в фазе восстановления виртуального слоя , на его выходе формируется сигнал логической единицы. Этот сигнал через элемент И 14.2 воздействует на дешифратор 5.3 и разрешает его работу. В результате номер текущего физического слоя , поступающий из реги-стра 1.6, преобразуется в соответствующий унитарный код, что приводит к от-крытию соответствующего элемента в составе блока 11. Поскольку из соответ-ствующего регистра группы 1.2 через мультиплексор 3.2 на этот же элемент блока 11 также поступает единица, блок 11 выдает ненулевое значение и эле-мент ИЛИ 24 формирует единичный уровень сигнала, подготавливающий к ра-боте одновибратор 23. С появлением очередного импульса волны на выходе одновибрато-ра 26 регистры группы 1.2 переключаются в новое состояние, соответствующее текущему виртуальному слою. Если при этом разряд регистров, соответствую-щий слоям , , переключится в нулевое состояние, значит в данную ячейку от соседних ячеек поступило значение функции , означающее выполнение условия восстановления. В этом случае на выходе блока элементов И 11 снова появится нулевое значение и уровень сигнала на выходе элемента ИЛИ 24 станет нуле-вым. В результате одновибратор 23 выдаст импульс . Этот им-пульс пройдет на выход K ячейки и разрешит текущему процессорному моду-лю продолжить функционирование. Кроме того, импульс через элемент ИЛИ 18 немедленно сбросит триггер 7.3, блокируя элементы 14.1, 14.2 и блок 11.
Рассмотрим подробнее порядок распространения значений индикаторных функций через ячейку в фазах синхронизации и восстановления.
В фазе синхронизации значения индикаторных функций распространяют-ся через ячейки по цепям, образованным блоком элементов И 13, демультип-лексором 2.1, группой регистров 1.1, мультиплексором 3.1 и блоком элементов И 10. В ячейке к этому процессу подключаются блок инверто-ров 19 и буфер 9, а блок элементов И 10, напротив, закрывается и не участвует в передаче значений индикаторных функций.
