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

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

...

Введение 3
1.Характеристика задачи обеспечения барьерной синхронизации 5
2.Концепция и технология параллельного программирования неоднородных систем на кристалле 11
Заключение 20
Список литературы 21

Современная технология дает возможность создания СБИС емкостью свыше 2 млрд транзисторов, позволяя реализовать на одной микросхеме мощные мультикомпьютеры, содержащие 100 и более процессорных модулей. Типичными представителями таких однокристальных систем являются матричные мультикомпьютеры фирмы Tilera, объединяющие от 32 до 100 процессорных элементов, связанных коммуникационной средой в двухмерную матричную структуру [1].
Функционирование мультикомпьютеров сопряжено с выполнением ряда коммуникационных операций, к числу которых относится барьерная синхронизация. Она заключается в согласовании моментов завершения и запуска параллельных ветвей программы в определенной ее точке (называемой барьером) и предполагает приостановку выполнения некоторых ветвей (процессов) до наступления условия си нхронизации, при котором все требуемые процессы достигли барьера [2]. Недостаточно эффективная организация синхронизации может значительно увеличить общее время выполнения параллельной программы, ограничивая производительность мультикомпьютера.
Реализация барьерной синхронизации на программном уровне связана с необходимостью передачи большого числа служебных сообщений между взаимодействующими процессами, в связи с чем на практике большее распространение получила синхронизация на аппаратном уровне. Идея подобной аппаратной синхронизации уже нашла воплощение во многих коммерческих системах и широко представлена в литературе в форме различных аппаратно-ориентированных процедур синхронизации [3]. На современном этапе развития вычислительной техники особый интерес представляют распределенные аппаратные процедуры синхронизации, которые, с одной стороны, органично вписываются в архитектуру однокристальных мультикомпьютеров, а с другой стороны, позволяют достичь более высокой скорости межпроцессорного взаимодействия при сохранении уровня гибкости и масштабируемости, присущего программно реализованным процедурам синхронизации.

С точки зрения интерфейса это обычно реализуется посредством проверки handle, возвращаемого неблокирующей операцией.В случае использования односторонних операций необходимо принимать специальные меры для получения гарантий того, что все отправленные пакеты были получены и исполнены, так как приемник не располагает информацией о данных, которые ему посылались (ввиду посылки их без его ведома), а отправитель может не располагать информацией о состоянии доставки пакетов.Как следствие, при использовании для сетевых обменов односторонних коммуникаций, необходимо иметь тот или иной механизм, позволяющий предоставить гарантии барьерной синхронизации.Подтверждения всех пакетов. Данный метод используется, например, в суперкомпьютерах фирмы Cray [1]. С одной стороны, из недостатков можно отметить значительную долю служебного трафика, уходящую на доставку подтверждений. С другой стороны, предоставление тех или иных синхронизационных гарантий реализуется относительно просто.Детерминированный порядок передачи пакетов. С одной стороны, позволяет исключить необходимость хранения неподтвержденных пакетов. С другой стороны, детерминированная маршрутизация (являющаяся одним из основных способов достижения детерминированного порядка передачи) имеет ряд недостатков.Подсчет пакетов требует больших буферов (для ряда синхронизационных гарантий - по числу узлов) для хранения информации о счетчиках.Сеть состоит из множества узлов, включающих в себя вычислительную часть (процессор) и коммникационную, состоящую из адаптера коммуникационной сети и маршрутизатора. Сеть имеет топологию «многомерный тор». Каждый узел представляет собой вычислительный узел (обычно, на базе платформы с одним или несколькими процессорами с архитектурой х86) с подключенным (по интерфейс PCI Express) адаптером коммуникационной сети.Вычислительный узел может выполнять операции с памятью удаленных узлов сети посредством пакетов, записываемых в определенный регион адаптера и обрабатываемых адаптером по их получении Для работы с памятью узла адаптер использует пакеты memory write и memory read request стандарт PCI Express.Доступны следующие операции:запись в память удаленного узла (без подтверждения; блокирующая/неблокирующая);чтение из памяти удаленного узла (без оповещения);атомарные операции в памяти удаленного узла (без возврата значения, без подтверждения).Так как возможны блокировки вида запрос/ответ, записи могут выполняться по двум виртуальным каналам: блокирующему (vcl) и неблокирующему (vcO). Чтения и атомарные операции выполняются только по блокирующему каналу, ответы на чтения посылаются только по неблокирующему каналу.Операции при инжекции их в сеть разбиваются на пакеты (сообщения), каждый из которых маршрутизируется независимо (и в случае адаптивной маршрутизации маршруты у пакетов различны). Помимо сообщений, созданных в рамках выполнения операций, могут использоваться служебные сообщения.Пакеты передаются по сети посредством связей (линков) между узлами (передача от одного узла соседнему по линку называется хопом или переходом) согласно правилам маршрутизации [2, 3]. Пакеты чогут передаваться как детерминированно, так и адаптивно.Барьерная синхронизация (наряду с иными коллективными операциями) является важным аспектом работы сети именно ввиду нетривиальности эффективности своей реализации. 2.Концепция и технология параллельного программирования неоднородных систем на кристаллеМногопроцессорные системы на кристалле (Multiprocessor Systems-on-Chips, СнК) - одно из ключевых современных приложений технологий сверхбольших интегральных схем. Требования приложений и ограничения реализации вынуждают создавать заказные, нестандартные, неоднородные архитектуры для оптимизации скорости вычислений, энергопотребления, стоимости, размеров и других критериев.Одним из важнейших вопросов в области разработки СнК является технологии и средства программирования таких систем. В коллективах, создающих СнК, существуют программные средства, позволяющие разработать необходимый код для функционирования системы: компиляторы для ядер, загрузчики, возможно, отладчики. Отсутствие единой схемы приложения не позволяет обеспечить эффективный процесс сборки и тестирования приложения, простоту адаптации ПО для изменяющихся задач и конфигураций системы, сделать разработку ПО доступной не только их проектировщикам, но и заказчикам.При таком подходе не удается объединить описание схемы программы (обычно графическое) и кодирование функций (обычно текстовое) в единую среду разработки. Это особенно актуально для разработки параллельных приложений, поскольку не позволяет контролировать ключевые вопросы: эффективность разработанного приложения; возможность модификации при изменении алгоритма или конфигурации платформы; взаимодействие одновременно выполняемых в системе задач, верификацию схемы приложения.Концепция программирования неоднородных СнК. Ключевыми особенностями предлагаемого подхода являются следующие:формальная модель параллельных вычислений как основа детерминированности и алгоритмической полноты вычислений;графическое представление и универсальный графический язык программирования для естественного описания схемы взаимодействия между компонентами программы с реализацией функциональных кодов модулей на традиционных языках программирования;интегрированная среда разработки приложений для комплексной унифицированной разработки ПО для неоднородных СнК.Рассмотрим последовательно все уровни предлагаемой концепции.Формальная АРП-модель параллельных вычислений. В основе предлагаемой концепции лежит формальная математическая модель динамических параллельных вычислений в распределенных архитектурах, АРП-модель [1; 2], которая является параллельной асинхронной моделью с полностью децентрализованным управлением. Общая АРП-модель определяется в терминах схемы параллельной программы. Схема представляется в виде направленного графа. Вершины графа представляют операторы и объекты-данные. Дуги графа соответствуют указателям, которые связывают операторы с соответствующими объектами-данными.АРП-модель формально определяет наиболее общий тип параллельных вычислений - динамические параллельные вычисления. Схема параллельной программы изменяется, в общем случае, на каждом шаге вычислений - изменяется сам граф, а не только пометки вершин, как это делается, например, в модели потоков данных или сетях Петри.АРП-модель предоставляет набор механизмов верификации схемы программы и построения согласованных вычислений. Верификация позволяет проверять поведение схемы программы «по построению» по ряду ключевых вопросов: зацикливание программы, наличие тупиков и др. Согласованные вычисления позволяют рассматривать выполнения параллельной программы, например, как последовательное для ее отладки и т. д.Графический язык параллельного программирования VPL. Язык VPL [3] основан на формальной АРП-мо- дели и предназначен для программирования динамических параллельных вычислений.В общей АРП-модели каждая операторная вершина может порождать любой фрагмент схемы программы. В языке VPL возможность порождать запрограммированный пользователем фрагмент схемы программы предоставляется только специальному классу управляющих операторов. Управляющие операторы могут включать в себя другие операторы и объекты-данные, которые будут порождены при срабатывании оператора. Эти операторы являются основным инструментом управления параллельным вычислением в программах на языке VPL: они управляют структурой схемы параллельной программы в процессе ее работы. Данный инструментарий также реализует иерархическое структурирование параллельной программы и организацию вычислений, зависящих от значений данных, что является необходимым для алгоритмической полноты языка программирования.Для остальных типов операторов язык программирования VPL определяет только общую, рамочную интерпретацию: такие операторы при срабатывании не могут порождать новые фрагменты схемы программы. Сама интерпретация будет задаваться программистом на последовательном языке программирования, например на языке С. Такой тип операторов называется «терминальными операторами». Терминальные операторы являются средством описания преобразований данных. Они читают данные, поступившие на вход, производят некоторую обработку данных (реализуют некоторую задачу обработки данных), формируют данные и записывают их на выход. Программа интерпретации оператора определяет функцию, которая будет запущена при вызове экземпляра оператора параллельной программы.Концепция программирования в АРП-модели на языке VPL. Существенная особенность архитектуры СнК - разнородность, специализация и малая производительность вычислительных модулей. Вследствие этого программы для СнК являются среднегранулярными, т. е. выполняемые блоки кода соответствуют уровню функций и процедур обычных программ.Для среднегранулярных программ естественным является разделение процесса разработки на программирование схемы параллельной программы и программирование ее компонент. Таким образом, должны использоваться два взаимодействующих уровня программирования:программирование схемы параллельной программы в виде сети операторов и объектов-данных в графической нотации языка VPL;программирования последовательных программ процессов на традиционных языках программирования (C, Embedded C, Assembler и т. д.).Все взаимодействия операторов друг с другом или с объектами-данными явно представляются на уровне схемы параллельной программы (рис. 1). Таким образом, они могут контролироваться и верифицироваться.Операторы взаимодействуют через объекты-данные (дуги в классическом графе потоков данных могут рассматриваться как частный случай объектов-данных). Объекты- данные являются абстракцией хранилищ и коммуникационных каналов, которые существуют вне операторов.Важным свойством предлагаемой концепции является запрет на управление параллельными вычислениями из программ отдельных операторов. Это предохраняет взаимодействия в параллельной программе от ненаблюдаемости, а схему от хаотичности и невозможности верификации.Интегрированная среда и практическое применение.Для создания ПО для неоднородных СнК в рамках предлагаемого подхода разработан пакет VIPE: VPL Integrated Programming Environment (рис. 2), который обеспечивает выполнение всего комплекса процедур от исходного алгоритма до получения готовой программы.Комплекс разработки ПО VIPE состоит из следующих компонент:визуальная интерактивная среда разработки схем параллельных программ на языке VPL;построитель размещений элементов схем программ на вычислительных модулях неоднородной СнК и расписаний их выполнения [4];транслятор схемы программы и функциональных модулей в загрузочные модули программного симулятора платформы;компилятор объектных кодов функций и схемы программы, генерация выполняемого на неоднородной СнК кода, линковка загружаемых в СнК модулей;программный симулятор неоднородной СнК с интерпретатором VPL.Комплекс VIPE обладает следующими ключевыми свойствами:поддерживает раздельное программирование схемы параллельной программы и последовательного кода ее элементов; поддерживает линовку модулей на традиционных языках программированияРис. 1. Параллельная программа - сеть операторов и объектов-данныхРис. 2. Схема VPL Integrated Programming EnvironmentМатематика, механика, информатикаподдерживает программирование как статических, так и динамических параллельных вычислений;поддерживает адаптацию размещения схемы программы под изменения спецификации платформы;производит набор трансформаций схемы программы;имеет расширяемую модульную структуру, позволяющую разрабатывать новые модули для поддержки различных последовательных языков и спецификаций платформ.Пример программирования в комплексе VIPE. Рассмотрим применение предложенной концепции программирования неоднородных СнК на примере задачи расчета прохождения набора луча через оптическую систему, которая рассматривается как совокупность оптических поверхностей и источников лучей с заданными характеристиками. Лучи имеют следующие параметры: координаты по осям, углы отклонений по осям, интенсивность, номер поверхности, на которой находится луч.В качестве объекта распараллеливания выберем лучи, так как при расчете их больше, чем поверхностей, а кроме того, их количество изменяется в ходе вычислений из- за эффектов отражения и поглощения.Кратко алгоритм будет выглядеть следующим образом:Загружаются из файлов параметры оптических поверхностей и характеристики начального набора лучей.Запускается параллельный цикл, каждая итерация которого рассчитывает прохождение одного луча через одну поверхность:Определяется номер поверхности для расчета.Характеристики поверхности запрашиваются из хранилища.Рассчитываются два новых луча: прямой и отраженный.Каждый из них либо удаляется из расчета (ниже пороговой интенсивности), отправляется на выход системы (расчет луча окончен) или возвращается в буфер для дальнейшего расчета.