Содержание к диссертации
Введение
1. Задачи синхронизации в параллельных системах 11
1.1. Архитектура современных параллельных систем 11
1.2. Межпроцессорное взаимодействие в параллельных системах 14
1.3. Задача синхронизации и подходы к ее решению 38
1.4. Методы барьерной синхронизации 48
Выводы 54
2. Процедура барьерной синхронизации и алгоритм взаимодействия синхронизируемых процессов
2.1. Модель параллельной системы 55
2.2. Содержательная характеристика и формализованное представление задачи обеспечения синхронизации 58
2.3. Характеристика процедуры синхронизации 61
2.4. Алгоритм взаимодействия синхронизируемых процессов 62
2.5. Примеры использования процедуры синхронизации 64
Выводы 66
3. Устройство синхронизации на основе созданной процедуры
3.1. Функциональная организация матричной МРР-системы 67
3.2. Анализ работы системы при рассмотрении соответствующих режимов функционирования процессоров 80
Выводы 99
4. Доказательство корректности созданной процедуры и оценка преимуществ разработанной процедуры и устройства
4.1. Представление процедуры синхронизации в виде сети Петри 100
4.2 Доказательство корректности процедуры синхронизации 104
4.3 Аналитическая оценка аппаратной сложности устройства синхронизации 105
4.4 Аналитическая оценка созданной процедуры синхронизации 106
4.5 Экспериментальная оценка созданной процедуры синхронизации 107
4.5.1. Постановка эксперимента 107
4.5.2. Архитектура экспериментальных программных средств 112
4.5.3. Результаты эксперимента 120
Выводы 122
Заключение 123
Библиографріческии список 125
Приложения 132
- Межпроцессорное взаимодействие в параллельных системах
- Содержательная характеристика и формализованное представление задачи обеспечения синхронизации
- Анализ работы системы при рассмотрении соответствующих режимов функционирования процессоров
- Архитектура экспериментальных программных средств
Введение к работе
Актуальность работы. Одним из перспективных архитектурных подклассов параллельных вычислительных систем (ВС) являются мультикомпьютеры с распределенной памятью (МРР-системы). Отличительная особенность таких систем - разделение физической памяти между процессорами (модулями) и организация их взаимодействия через коммуникационную сеть. Примерами подобных МРР-систем являются Cray ТЗЕ и Origin2000.
При построении МРР-систем особую значимость приобретает создание процедур и средств координации вычислительных процессов, параллельно протекающих в разных процессорах (параллельных процессов). Их эффективность существенно влияет на многие важные характеристики системы, включая производительность, аппаратно-программную сложность и гибкость.
Одной из ключевых задач координации параллельных процессов является барьерная синхронизация. Цель ее решения - согласование моментов активизации определенных групп процессов с моментами завершения других групп процессов.
Объект исследования — параллельные вычислительные процессы в МРР-системах с матричной топологией с незамкнутыми границами.
Предмет исследования - процедура и аппаратные средства распределенной барьерной синхронизации.
В настоящее время известно широкое разнообразие подходов к барьерной синхронизации в МРР-системах (J. R. Anderson, Т. A. Johnson, R. R. Hoare, Т. Muhammad и др.). Разработаны многочисленные варианты их реализации, как программные, так и аппаратные. При этом наиболее широко представлены решения программного уровня (Dissemination
5 barrier, Butterfly barrier, Tree-based barriers и др.)- Аппаратные решения, обладающие значительно большим быстродействием, пока не получили широкого распространения (DBM, Cyclical Cascade Barrier, СМ-5 Barrier Control Network и др.)- Известные аппаратные решения носят, как правило, централизованный характер и не являются распределенными (DBM, Cyclical Cascade Barrier), что ограничивает возможность включения в систему новых процессоров (усложняет наращивание системы).
В связи с вышеизложенным, актуальной научно-технической задачей
является создание быстродействующих децентрализованных
распределенных устройств и процедур барьерной синхронизации в МРР-системах.
Работа выполнена при поддержке гранта Министерства образования
РФ «Столетовские гранты-2003», а также в рамках совместных работ с
ОКБ «Авиаавтоматика» по договору №1.121.03 от 22 августа 2003 года.
Основная часть диссертационной работы выполнена в рамках плана
научно-исследовательских работ Курского государственного
технического университета по единому заказ-наряду Министерства образования Российской Федерации в 1998-2005 годах, утвержденному начальником управления планирования и финансирования научных исследований.
Целью диссертационной работы является упрощение наращивания
МРР-системы с матричной топологией на основе создания
распределенной децентрализованной аппаратно-ориентированной
процедуры барьерной синхронизации и распределенных устройств синхронизации на ее основе.
В соответствии с поставленной целью в работе решаются следующие задачи:
Сравнительный анализ существующих процедур барьерной синхронизации в МРР-системах.
Разработка распределенной децентрализованной аппаратно-ориентированной процедуры барьерной синхронизации.
Доказательство корректности разработанной процедуры на основе аппарата сетей Петри.
Исследование зависимости времени синхронизации от числа процессоров системы и числа синхронизируемых процессов, а также анализ аппаратной сложности устройства синхронизации.
Методы исследования. При решении поставленных задач использовались методы теории множеств, теории графов, теории вероятностей, теории проектирования ЭВМ, теории автоматов и математической статистики. Экспериментальные исследования проводились на основе библиотеки классов имитационного моделирования и визуальной среды программирования, разработанных на кафедре ВТ КурскГТУ под руководством доц. Зотова И.В.
Научная новизна результатов диссертационной работы:
Создана распределенная децентрализованная аппаратно-ориентированная процедура барьерной синхронизации, основанная на косвенном взаимодействии процессов через коммуникационную сеть идентичных устройств синхронизации.
Получено доказательство корректности процедуры синхронизации, путем анализа графа достижимых маркировок сети Петри, описывающей созданную процедуру.
Разработан алгоритм организации взаимодействия распределенных устройств синхронизации, позволяющий повысить скорость проверки условий барьерной синхронизации.
Практическая ценность работы заключается в следующем:
1. Созданная процедура обеспечивает синхронизацию
произвольного множества процессов за время порядка 1 мкс, что в 5 раз меньше, чем в лучших известных аппаратных решениях.
Разработана структурно-функциональная организация распределенной системы барьерной синхронизации, в том числе центрального микропрограммируемого процессора и узлового блока управления синхронизацией.
Упрощение наращиваемости системы (включение в МРР-систему новых процессоров и узловых блоков управления синхронизации) достигнуто за счет однотипности узловых блоков и регулярности межузловых связей.
Экспериментально на имитационной модели установлено отсутствие зависимости времени организации синхронизации от числа синхронизируемых процессов.
Аппаратная сложность устройства синхронизации на порядок ниже, чем у известных аппаратных аналогов.
Техническое решение устройства синхронизации в МРР-системе выполнено на уровне изобретения (патент № 2249849).
Реализация и внедрение. Ряд результатов, полученных в диссертационной работе, был использован при производстве изделий в ОАО «Счетмаш» (г. Курск), а также применяется в учебном процессе на кафедре вычислительной техники КурскГТУ в рамках дисциплины «Теоретические основы проектирования отказоустойчивых мультимикропроцессоров».
Апробация работы.
Основные положения диссертационной работы докладывались и получили положительную оценку на НТК «Распознавание-2003» (г. Курск,
8 2003), НТК «Образование, наука, производство» (г. Белгород, 2004), НТК
«КЛИН-2004» (г. Ульяновск, 2004).
Публикации.
Результаты диссертационной работы отражены в 5 публикациях, в числе которых 1 статья и 1 патент на изобретение.
На защиту выносятся:
1. Распределенная децентрализованная аппаратно-ориентированная
процедура барьерной синхронизации, позволяющая на основе
организации косвенного коллективного взаимодействия процессов через
сеть устройств синхронизации, повысить скорость проверки выполнения
условий синхронизации.
Доказательство корректности разработанной процедуры барьерной синхронизации на основе исследования графа достижимых маркировок сети Петри и установления ее живости и ограниченности.
Структурно-функциональная организация системы барьерной синхронизации, отличающаяся однотипностью разработанных узловых блоков управления синхронизации и регулярностью межузловых связей и, благодаря этому, позволяющая упростить наращиваемость системы.
Алгоритм организации взаимодействия распределенных устройств синхронизации, позволяющий повысить скорость проверки условий барьерной синхронизации.
Объем и структура работы.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 131 страницу текста и поясняется 21 рисунком и 2 таблицами; список литературы включает 60 наименований; приложения содержат 40 страниц.
Области возможного использования.
Результаты диссертационной работы могут быть непосредственно
9 использованы в коммерческих МРР-системах с матричной топологией
(системы Cray, Intel, Thinking Machines). Кроме того, возможно их
применение в специализированных параллельных системах, например, в
параллельных логических контроллерах, а также во встраиваемых
микропроцессорных системах управления нижнего уровня иерархии
АСУТП.
Во введении обоснована актуальность темы диссертации,
сформулированы цель, основные задачи исследований, выносимые на
защиту положения, отмечена научная новизна и практическая ценность
работы.
В первой главе рассматривается архитектура современных параллельных вычислительных систем, выделяется подкласс массивно-паралельных систем, обсуждаются основные коммуникационные задачи в подобных системах, формулируется задача организации барьерной синхронизации, рассматриваются известные процедуры барьерной синхронизации (программного и аппаратного уровней).
Во второй главе дается постановка задачи барьерной синхронизации параллельных процессов в МРР-системе с матричной топологией, формулируется распределенная децентрализованная процедура барьерной синхронизации и алгоритм взаимодействия синхронизируемых процессов.
В третьей главе рассматривается структурно-функциональная организация центрального микропрограммируемого процессора синхронизации специализированной матричной МРР-системы с многоузловой решетчатой топологией на основе разработанной процедуры и распределенных однотипных устройств барьерной синхронизации.
В четвертой главе проводится доказательство корректности
10 созданной процедуры на основе анализа графа достижимых маркировок
сети Петри, выполняется оценка преимуществ разработанной процедуры и
устройства перед известными аналогами по критериям минимального
времени организации синхронизации и удельной структурной сложности.
В заключении сформулированы основные результаты
диссертационной работы.
В приложениях приводятся листинги программ имитационного
моделирования, акты внедрения.
Межпроцессорное взаимодействие в параллельных системах
Важнейшим элементом архитектуры любых высокопроизводительных вычислительных систем, в том числе и МРР систем, являются средства обмена данными между процессором и оперативной памятью, процессором и другими устройствами, между различными процессорами. Организация внутренних коммуникаций вычислительной системы определяется ее топологией.
Статические системы с шинной организацией позволяют минимизировать число межмодульных линий связи (рис. 1.1а) [4]. Достоинством такой организации является практическая независимость числа межмодульных соединений от числа процессорных элементов (ПЭ), а также простота подключения дополнительных ПЭ. Однако такие ВС не позволяют объединять значительное (N 10 - 20) число ПЭ. Это обусловлено критичностью системы к росту межпроцессорного обмена, а также ограничениями электрического характера. При одновременной генерации сообщений каждым ПЭ время ожидания освобождения шины системы равняется — условных временных интервалов, хотя рассматриваемые структуры не предполагают транзитной передачи сообщений. Другим недостатком шинных структур является низкая надежность, которая фактически определяется надежностью общей шины.
Одним из путей совершенствования структур с общей шиной является использование ВС с мультишинной организацией, включающих N 1 шин. Однако, несмотря на повышенную надежность, мультишинная организация обладает высокой удельной сложностью. Например, при использовании N1 = N общих шин затраты на каналы связи зависят от размерности ВС как 0(N").
Другим способом совершенствования структур с общей шиной является переход к иерархическим шинным ВС [4] (рис. 1.16), принцип структурно-топологического построения которых предписывает разбиение множества ПЭ на совокупность не сравнимых по включению пересекающихся подмножеств, каждому из которых соответствует собственная общая шина. Обмен информацией между ПЭ, входящими в различные подмножества таких систем, производится за счет транзитной передачи сообщений через общие для этих подмножеств элементы.
Максимально возможное быстродействие систем достигается при их реализации в виде полносвязных структур [5]. Особенностью таких структур является единичное расстояние между любой парой ПЭ (рис. 1.2). Каждая пара ПЭ в полносвязной структуре соединяется индивидуальным двунаправленным каналом и, таким образом, межпроцессорный обмен информацией осуществляется без транзитной передачи сообщений (ретрансляции). Рассматриваемые структуры позволяют строить ВС достаточно высокой надежности, поскольку отказ любого ПЭ не нарушает связей между другими ПЭ, а выход из строя канала связи между і-м и j-м ПЭ исключает возможность взаимодействия только і-го и j-ro ПЭ. С другой стороны полносвязные структуры не могут служить эффективной основой для построения многопроцессорных систем (N 10) вследствие квадратичного роста числа межпроцессорных связей, высокой удельной сложности и чрезвычайно низкой загрузки каналов связи.
Большое распространение получили матричные и кольцевые матричные структуры, примеры которых показаны на рис.1.3а-г [6]. В матричной структуре отдельные ПЭ размещаются вблизи узлов прямоугольной сетки или матрицы размером NjxN2, при этом каждый элемент идентифицируется номерами строки и столбца, соответствующими его расположению в пределах матрицы. В простом случае (рис. 1.3а) каждый элемент, за исключением крайних, непосредственно подключается к четырем другим элементам, находящимся слева, справа, сверху, снизу от него, и взаимодействие между произвольными элементами матричной структуры осуществляется через транзитную передачу сообщений через промежуточные ПЭ. Достоинствами матричных структур является малая и не зависящая от размерности системы удельная сложность, простота наращивания числа ПЭ, возможность построения ВС с высокой надежностью и живучестью.
Кольцевые матричные структуры отличаются от матричных наличием связей между крайними элементами строки (столбца), что обеспечивает некоторое уменьшение среднего времени задержки сообщения (рис. 1.36). При построении ВС с кольцевой матричной структурой наряду с двунаправленными каналами возможно использование однонаправленных каналов связи, что позволяет существенно снизить удельную сложность. Один из вариантов кольцевой матричной структуры с однонаправленными каналами связи представлен на рис. 1.3 в. Серьезным недостатком матричных и матричных кольцевых структур является существенный рост среднего времени передачи межмодульных сообщений от размерности ВС.
Помимо матричных и матричных кольцевых структур с четырьмя соседями распространение получили матричные структуры, в которых каждый элемент имеет непосредственные связи с восемью соседними узлами: сверху, снизу, справа, слева, слева-снизу, слева-сверху, справа-сверху, справа-снизу (рис. 1.3г) [6]. Увеличение числа непосредственных связей, несмотря на некоторый рост удельной сложности, позволяет снизить диаметр системы и, следовательно, снизить среднее время передачи сообщений и загрузку каналов. Одним из частных случаев реализации матричной структуры с увеличением числа непосредственных связей является систолическая матрица, в которой число каналов непосредственных связей уменьшено до шести (отсутствуют связи в одном из диагональных направлений).
Содержательная характеристика и формализованное представление задачи обеспечения синхронизации
Такими условиями являются исправность каналов связи, их загрузка, число сообщений, пребывающих в очередях и др. В зависимости от характера информации, используемой при формировании маршрутов сообщений, адаптивные алгоритмы разделяют на локальные и глобальные. При работе локальных адаптивных алгоритмов выбор направлений выдачи сообщений осуществляется с учетом информации, отражающей текущее состояние только смежных (соседних) узлов. Напротив, глобальные алгоритмы используют информацию о состоянии всех узлов и каналов системы, которая, как правило, представляется в виде совокупности усредненных значений параметров системы в текущий момент времени. Адаптивные алгоритмы маршрутизации отражены в литературе [16,17,18].
Для обеспечения максимума производительности ВС создаются библиотеки передачи сообщений, учитывающие особенности каждой отдельно взятой машины. Это способствует написанию эффективных, но ориентированных только на одну машину программ. Вместе с тем разработчики ПО предлагают множество сред передачи сообщений, независимых от конкретной платформы. Каждая такая среда имеет интерфейс в виде набора процедур или функций (как правило, их кодируют в двух вариантах - для языков С и для Fortran). Наиболее известны из них EXPRESS компании Parasoft и PVM (Parallel Virtual Machine), созданный Oak Ridge National Laboratory. В 1994 г. был разработан и принят стандартный интерфейс передачи сообщений MPI (Message Passing Interface Standard). Он готовился с 1992 по 1994 гг. группой Message Passing Interface Forum, в которую вошли представители более 40 организаций из Европы и Америки. MPI - это процедурный интерфейс для языков С и Fortran. Он включает в себя функции, необходимые для организации передачи сообщений точка -точка, для коллективных обменов. Стандарт явно вводит следующие понятия: группы процессов, с которыми можно оперировать как с конечными множествами, и коммуникаторы, реализующие контекст для передачи сообщений. Благодаря понятию контекста становится возможным построение стандартных библиотек программ. MPI предусматривает передачу сообщений в гетерогенной среде и обеспечивает трансляцию данных из формы, необходимой одному процессору, в вид, пригодный для другого. Стандарт допускает как программирование в стиле SPMD, так и программы, состоящие из нескольких текстуально различных частей, каждая из которых загружается на отдельный процессор. В настоящее время подготовлено несколько реализаций MPI.
В стандарте объединены наиболее удачные аспекты большинства предшественников: поддержка разнотипных процессоров (обслуживается автоматическое преобразование пересылаемых данных), синхронная и асинхронная передача сообщений, их передача без блокировки, широковещательный режим "один - многие", барьерная синхронизация, рассылка элементов массива группе процессоров (scatter) и сбор массива из данных, распределенных по нескольким вычислительным узлам (gather), функции редукции, которые определяются на данных, распределенных по группе процессоров. Наиболее важным новшеством, делающим MPI жизнеспособным стандартом, является понятие коммуникатора, задающего контекст передачи сообщений один - многим. Благодаря ему стало возможным проектирование и кодирование стандартных библиотек параллельных алгоритмов.
За последние годы появились альтернативы системам с передачей сообщений. Идея виртуальной общей памяти: имеется система с распределенной памятью, каждый процессор поддерживает страничную виртуальную память, но в отличие от традиционных систем виртуальной памяти, подкачивающих недостающую страницу с магнитного диска, в случае возникновения исключительной ситуации при отсутствии страницы в локальной памяти процессора она запрашивается у другого процессора системы и передается в виде сообщения.
Эта система нашла успешное воплощение в суперкомпьютере CRAYT3D [19]. Компьютер CRAY T3D - это массивно-параллельный компьютер с распределенной памятью, объединяющий от 32 до 2048 процессоров. Каждый процессор имеет непосредственный доступ только к своей локальной памяти, а доступ к данным, расположенным в памяти других процессоров, выполняется другими, более сложными способами.
CRAY T3D подключается к хост-компьютеру (главному или ведущему), роль которого, в частности, может исполнять CRAY Y-MP С90. Вся предварительная обработка и подготовка программ, выполняемых на CRAY T3D, проходит на хосте (например, компиляция). Связь хост-машины и T3D идет через высокоскоростной канал передачи данных с производительностью 200 Мбайт/с. За счет высокоскоростной коммуникационной аппаратуры время обращения к локальной странице лишь в несколько раз меньше, чем время обращения к странице, расположенной в памяти другого процессора.
Массивно-параллельный компьютер CRAY T3D работает на тактовой частоте 150MHz и имеет в своем составе три основные компоненты: сеть межпроцессорного взаимодействия (или по-другому коммуникационную сеть), вычислительные узлы и узлы ввода/вывода.
Попытки реализовать обращения к локальной странице без мощной коммуникационной аппаратуры оказались неудачными. Чередующиеся обращения к одной странице со стороны нескольких процессоров вызывали "эффект пинг-понга", и система большую часть времени тратила на страничный обмен.
Другой способ уйти от прикладного программирования с помощью передачи сообщений предлагают языки, использующие параллелизм данных, например экспериментальный язык HPF (High Performancy Fortran). Пользователь задает распределение данных по процессорам (неудачное расположение данных может вызвать существенное увеличение накладных расходов), а компилятор автоматически генерирует вызовы функций синхронизации и передачи сообщений. Он автоматически распараллеливает циклы, учитывая при этом зависимость по данным между витками цикла.
Программа на языке HPF существенно короче функционально идентичной, но применяющей вызовы функций пакета обмена сообщениями напрямую. Последним при программировании параллельных систем отводится, вероятно, та же роль, что и языку ассемблера в современном программировании: к ним будут прибегать лишь для реализации систем поддержки времени выполнения языков, использующих параллелизм данных, да при написании библиотечных алгоритмов, от которых требуется максимальная эффективность.
Анализ работы системы при рассмотрении соответствующих режимов функционирования процессоров
Решение этих недостатков находят в применении сочетания аппаратной и микропрограммной реализации. В результате повышается эффективность средств синхронизации и некоторых случаях уменьшается время, необходимое для определения состояния синхронизируемых процессов, но при этом снижается универсальность механизмов, что приводит к разработки отдельных моделей для определенных классов структур МРР.
Модели, разработанные для применения в МРР и мультипрограммных системах с полносвязной организацией.
Отличительная особенность - опрос состояния параллельных участков по вектору состояния, закрепляемому либо за одним, либо за каждым модулем МРР. Каждый модуль при активизации или переходе в пассивное состояние может непосредственно модифицировать значения соответствующих ему компонент векторов состояния, закрепленных за остальными модулями. Путем выдачи управляющих сигналов по индивидуальным каналам связи. Т.е. модули МРР в любой момент времени имеют информацию о текущем состоянии каждого из выполненных участков алгоритма управления. Модели с такой организацией синхронизации обладают низкой гибкостью, что выдвигает ряд дополнительных ограничений при распределении участков алгоритма и усложняет процесс синтеза МРР.
Для повышения гибкости используют модель синхронизации, которая отличается от описанной выше способом опроса состояния параллельных участков. В данной модели каждый модуль получает информацию не только о текущем состоянии модулей, активизированных с его стороны, но и о состоянии других модулей, что допускает множество режимов синхронизации. Кроме того, эта модель позволяет осуществлять синхронизацию параллельных участков средствами любого модуля.
Описанные выше модели, вследствие выраженной структурной специализации не могут быть использованы для построения МРР-систем с неполносвязной структурой. В основе модели удовлетворяющей этому требованию лежит понятие состояние модуля МРР по отношению к вершине синхронизации параллельных участков. Процедура синхронизации заключается в формировании и передачи номера заданной вершины синхронизации, преобразовании этого номера в множество признаков текущего состояния модулей по отношению к данной вершине, формировании обобщенного признака состояния и последующем опросе этого признака одним из модулей. Важным свойством модели является то, что она не требует наличия информации о числе синхронизируемых участков и о способе их распределения, хотя это условие является необходимым для моделей, использующих вектор состояния.
Другая модель синхронизации - это модель с транзитным режимом взаимодействия процессоров. Основой модели является понятие текущего числа ожидаемых событий, которое представляет количество параллельных участков алгоритма, не завершенных к данному моменту времени. Каждое событие есть окончание очередного из синхронизирующих участков. Рассматриваются только группы параллельных участков, сходящихся в единой вершине синхронизации. Максимальное число синхронизируемых участков в данной модели ограничивается размерностью МРР и разрядностью межмодульных каналов связи. Отличие от других моделей - это возможность одновременной работы любого процессора в режиме ведущего по отношению к нескольким вершинам синхронизации, что позволяет исключить ограничения на порядок закрепления таких вершин за модулями МРР. Оперативность синхронизации определяется быстродействием средств передачи. Но хотя данная модель применима к МРР-систем широкого класса, она не экономична из-за использования блоков памяти для хранения условий синхронизации. Решение этой проблемы заключается в оптимизации способа представления условий синхронизации - модель с кольцевой структурой. Условия в этой модели представляются в формате микрокоманд и размещении их в блоке памяти микропрограмм ведущих микроконтроллеров. Ключевой особенностью процедурной характеристики модели является формирование и опрос значения условия синхронизации на основе многократной ретрансляции специальной команды опроса через все модули МРР. Данная модель не только сохраняет свойства описанных ранее моделей, но и позволяет отказаться от дополнительных средств для хранения условий синхронизации. Оперативность синхронизации определяется размерностью МРР и пропускной способностью средств ретрансляции межмодульных сообщений.
Одним из наиболее известных способов синхронизации процессов является барьерная синхронизация. Цель ее решения — согласование моментов активизации определенных групп процессов с моментами завершения других групп процессов. Необходимость подобного согласования возникает как в задачах с так называемым «мелкозернистым» (fine-grain) параллелизмом, так и в задачах, допускающих выделение крупных слабосвязанных фрагментов (coarse-grain). Например, оно требуется при осуществлении матричных вычислений.
Представленные на настоящий момент решения задачи барьерной синхронизации реализуются преимущественно программно (Dissemination barrier, Butterfly barrier, Tree-based barriers и др.), что обеспечивает гибкость средств синхронизации, но резко снижает быстродействие системы. Альтернативные им аппаратные решения (DBM, Cyclical Cascade Barrier, СМ-5 Barrier Control Network и др.) обладают весьма высоким быстродействием (один акт синхронизации за десятки микросекунд), однако характеризуются пониженной гибкостью. В частности, они носят централизованный характер и не являются распределенными (DBM, Cyclical Cascade Barrier). А это ограничивает возможность включения в систему новых процессоров (усложняет наращивание системы) и снижает ее потенциал для перспективных применений.
Барьер - это точка в программе, при достижении которой каждый процесс должен ждать до тех пор, пока остальные процессы также не дойдут до барьера. Лишь после этого события все процессы могут продолжать работу дальше.
Архитектура экспериментальных программных средств
В МКС межмодульная передача управления в явном виде отсутствует; выполняется только процедура синхронизации. При этом запуск участков программ, реализуемых различными модулями, происходит при выполнении соответствующих условий синхронизации. Таким условием при запуске участков, непосредственно следующих за подмножеством других (параллельных) участков, является синхронизация (завершение) всех участков данного подмножества. При запуске участков, следующих за единственным участком, в качестве условия выступает завершение этого единственного участка. Для задания момента активизации некоторого участка z j (е) (где е — порядковый номер данного участка для (i.j)-ro модуля, 1 — номер программы) этому участку ставится в соответствие номер непосредственно предшествующей ему вершины синхронизации ai (если активизируемому участку непосредственно предшествует единственный участок программы, то вершина щ считается фиктивной). Запуск участка z /\e) происходит после выполнения вершины а/, т.е. как только завершаются все непосредственно предшествующие ему участки программы. В предлагаемой сети указанные адреса формируются непосредственно модулями, реализующими запускаемые участки (модулями — приемниками управления), в результате самонастройки. Адрес А[(е + 1) начала следующего (е+1)-го участка, выполняемого (i.j)-M модулем, указывается в заключительной команде предшествующего (е-го) участка программы. Для задания адресов начальных участков модулей {А, (1)} используются команды настройки формата Фі (рис.3.2). За каждым модулем сети закрепляется R таких команд, R — число программ, реализуемых микроконтроллерной сетью (число программ в реализуемом комплексе). Каждая из R команд настройки определяет адрес А}J (1) первой команды, выполняемой (i.j)-м модулем при реализации 1-й программы, т.е. адрес начального участка (i.j)-ro модуля. (Если (i.j)-H модуль не участвует в процессе выполнения 1-й программы, то команда Фі содержит только нули.) Команды настройки Фі размещаются в блоке 1 памяти программ (рис.3.3) по начальным адресам от 1 до R включительно. Команда настройки, а, следовательно, и реализуемая программа однозначно задается адресом при обращении к блоку 1.
Процесс синхронизации параллельных участков в предлагаемой МКС осуществляется на основе распространения и опроса отдельных сигналов завершения групп параллельных участков. Каждый такой сигнал распространяется в отдельном канале управления синхронизацией, который соответствует одной из вершин синхронизации (слияния) параллельных участков. Канал управления синхронизацией представляет собой совокупность элементов различных модулей МКС и соответствующих связей, обеспечивающих протекание процесса синхронизации определенной группы параллельных участков.
Для обеспечения синхронизации произвольных групп параллельных участков за каждым модулем МКС закрепляется вектор, задающий соответствие между множеством вершин синхронизации программы и данным модулем. (i.j)-My модулю сети, i = l,M, j = l,N, в общем случае соответствует R различных векторов, каждый из которых отвечает определенной программе. Вектор соответствия для (i.j)-ro модуля описан во второй главе формулами 2.8 и 2.9. Синхронизация группы параллельных участков осуществляется на основе циклического распространения сигнала di завершения группы участков. Сигнал di формируется (I.N)-M модулем сети (рис.3.1). В исходном состоянии di=0 (параллельные участки не завершены) и, следовательно, d, = 1. Процесс синхронизации включает две фазы — формирование признака окончания синхронизируемых участков и передачу этого признака всем модулям МКС. Первая из указанных фаз начинается с подачи единичного сигнала d,. Единичный сигнал d,распространяется от (l.N)-ro модуля вниз и влево через все модули МКС ко всем крайним левым и крайним нижним клеткам. Крайние клетки определяются триггерами наличия соседа слева Л и и наличия соседа снизу ЛІи . Если Лг у ="1" то это значит что присутствует связь с соседом слева , и сигнал передастся этому соседу. Если Л4; ="1" то это значит что присутствует связь с соседом снизу , и сигнал передастся этому соседу. В противном случае единичный сигнал d, по обратной связи передастся на выход модуля следующим образом: на верхний если сигнал пришел сверху, и на правый если сигнал пришел справа. Затем начинается обратное распространение единичного сигнала d, через МКС к модулю (1.N). Распространение сигнала d, через некоторый модуль nijj происходит следующим образом. Если of =1, то появление единичных сигналов dj на нижнем и левом входах (i.j)-ro модуля обусловливает формирование единичного сигнала d, на его выходе. Если 0/ =0, то формирование единичного сигнала d, на выходе (i.j)-ro модуля происходит только при условии завершения синхронизируемого участка, реализуемого (i.j)-M модулем. Состояние синхронизируемого участка определяется значением сигнала — признака описанного во второй главе формулами 2.10 и 2.11. В случае если синхронизируемый участок не завершен, на выходе (i.j)-го модуля устанавливается нулевой сигнал. Данный сигнал формирует нулевые сигналы на выходах всех модулей, расположенных выше и / или правее (i.j)_ro модуля. На выходе (l.N)-ro модуля, соответственно, также будет нулевой сигнал di=0. Как только происходит завершение синхронизируемого участка, единичный сигнал d, передается на выход (i.j)-ro модуля и поступает на (i-l.j)-u и (i.j+І)-й модули. После завершения всех параллельных участков группы Ъ\ сигнал d{ пройдет на входы (l.N)-ro модуля и на выходе (l.N)-ro модуля, таким образом, будет сформирован сигнал dj=l, сообщающий об окончании синхронизируемых параллельных участков. На этом первая фаза синхронизации завершается. Вторая фаза синхронизации начинается с инвертирования сигнала dj. Получаемый нулевой сигнал djтакже распространяется от (l.N)-ro модуля вниз и влево через все модули МКС ко всем крайним левым и крайним нижним клеткам как и в предыдущей фазе, затем сигнал распространяется через все модули МКС до модуля с номером I.N. В процессе распространения сигнала происходит запуск всех модулей, ожидающих завершение параллельных участков группы Ъ\. Признаком запуска модуля является переход сигнала dt из единицы в нуль (1 — 0). Вторая фаза и процесс синхронизации параллельных участков в целом завершаются после появления нулевого сигнала на выходе (l.N)-ro модуля.
