Cтруктурно-ориентированные версии алгоритмы Dissemination, Recursive Doubling и Combining Tree

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

В настоящее время широкое распространение получили распределенные вычислительные системы (ВС).

В архитектурном плане распределенная ВС представляется множеством взаимодействующих элементарных машин, оснащенных средствами коммуникаций и внешними устройствами. Элементарная машина (ЭМ) - это основной функциональный и структурный элемент ВС; конфигурация ЭМ допускает варьирование в широких пределах - от процессорного ядра до ЭВМ.

Все основные ресурсы распределенных ВС (арифметико-логические устройства, память, средства управления и коммуникаций) являются логически и технически рассредоточенными.

Число ЭМ в распределённых ВС допускает варьирование от нескольких единиц до сотен тысяч [1].

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

Ее можно представить в виде графа, вершины которого - ветви параллельной программы, а ребра - информационные обмены между ними.

Время выполнения параллельных программ на распределенных ВС существенно зависит от того, насколько они эффективно вложены в систему. Под эффективным вложением понимается такое распределение ветвей параллельной программы между ЭМ системы, при котором достигаются минимумы накладных расходов на межмашинные обмены информацией и дисбаланса загрузки ЭМ [16].

В данной работе разработаны и реализованы в библиотеке TopoMPI структурно-ориентированные версии алгоритмы Dissemination, Recursive Doubling и Combining Tree.

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



1. ПОНЯТИЯ О ВС

1.1 Модель коллектива вычислителей

программа вычислительный дифференцированный обмен

К созданию вычислительных систем существуют два основных подхода [1]:

построение электронных вычислительных машин (ЭВМ), моделирующих процесс выполнения алгоритма одиночным человеком-вычислителем;

построение вычислительных систем (ВС), имитирующих процесс выполнения алгоритма коллективом людей-вычислителей.

ЭВМ является аппаратурно-программным комплексом, основным на модели вычислителя, которое предназначено для автоматического выполнения логико-вычислительной работы: ввода, обработки, хранения и вывода информации. Согласно концепции машины Фон-Неймана, воплощающей в себе идеи модели вычислителя, конструктивными принципами построения ЭВМ являются:

последовательная обработка информации;

фиксированность структуры;

неоднородность составляющих устройств и связей между ними.

Использование модели вычислителя для построения высокопроизводительных вычислительных средств ограничено теоретическими и техническими пределами скорости выполнения операций (возможностями элементной базы и фундаментальными физическими законами). Это привело к созданию вычислительных средств, основанных на модели коллектива вычислителей. Под коллективом вычислителей понимается совокупность вычислительных машин, программно-аппаратурным способом настраиваемая на решение общей задачи.

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

параллелизм при обработке информации;

программируемость структуры;

однородность конструкции.

Видно, что модель коллектива вычислителей основывается на диалектическом отрицании принципов, лежащих в основе модели вычислителя.

Параллелизм при обработке информации предполагает представление алгоритма решения задач с помощью параллельных программ.

Параллельная программа - это совокупность связанных ветвей-программ, выполняющих одновременную (параллельную) работу над выделенными им данными и, при необходимости, взаимодействующих между собой.

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

Программируемость структуры предполагает возможность автоматической (программной) настройки проблемно-ориентированных (виртуальных) конфигураций и их перенастройки в процессе функционирования с целью обеспечения адекватности структурам и параметрам решаемых задач и достижения эффективности при заданных условиях эксплуатации.

Конструктивная однородность заключается в формировании коллектива вычислителей из совокупности одинаковых элементов (модулей), однородным образом соединенных между собой.

Вычислительное средство, базирующееся на модели коллектива вычислителей, называется вычислительной системой [1].

Наиболее полно принципы модели коллектива вычислителей воплощены в ВС с программируемой структурой. Разработка теоретических основ и принципов технической реализации, а также создание первых ВС с программируемой структурой были осуществлены в СССР к началу 70-х годов XX в.

Классификация ВС

ВС классифицируют по различным признакам. Наиболее общей является классификация, предложенная в 1966 М. Дж. Флинном. В зависимости от числа обрабатываемых вычислительным средством потоков команд и данных, выделено четыре класса архитектур: SISD (Single Instruction stream / Single Data stream), SIMD (Single Instruction stream / Multiple Data stream), MISD (Multiple Instruction stream / Single Data stream), MIMD (Multiple Instruction stream / Multiple Data stream). Первый класс - SISD - относится к ЭВМ. Архитектуры MISD, SIMD, MIMD относятся к ВС. В соответствии с этими архитектурами допустимо построение нескольких типов ВС: 1) конвейерные ВС, 2) матричные ВС, 3) мультипроцессорные ВС, 4) распределенные ВС, 5) кластерные ВС, 6) пространственно-распределенные мультикластерные ВС.

Архитектура конвейерных ВС является предельным вариантом развития архитектуры последовательной ЭВМ. В основе таких систем лежит конвейерный способ обработки информации, а их функциональная структура представляется в виде “последовательности” связанных элементарных блоков обработки информации. Все блоки работают параллельно, но каждый из них реализует лишь свою операцию над данными одного и того же потока. Конвейерные ВС принадлежат классу MISD-систем.

Матричные ВС основываются на принципе массового параллелизма, в них обеспечивается возможность одновременной реализации большого числа операций на элементарных процессорах (ЭП), “объединенных” в матрицу. Каждый ЭП - композиция из арифметико-логического устройства (АЛУ) и локальной памяти (ЛП); последняя предназначается для хранения части данных. Поток команд на матрицу ЭП формируется устройством управления (следовательно, оно имеет в своём составе память для хранения программ обработки данных). Такие ВС имеют SIMD-архитектуру в классическом виде.

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

Распределенные ВС - мультипроцессорные ВС с MIMD-архитектурой, в которых нет единого ресурса (общей памяти). Основные компоненты распределенной ВС (такие, как коммутатор, устройство управления, арифметико-логическое устройство или процессор, память) допускают представление в виде композиции из одинаковых элементов (локальных коммутаторов и устройств управления, локальных процессоров и модулей памяти).

Вычислительные системы с программируемой структурой полностью основываются на модели коллектива вычислителей и являются композицией взаимосвязанных элементарных машин. Каждая ЭМ в своем составе обязательно имеет локальный коммутатор (ЛК), процессор и память; может иметь также внешние устройства. Локальная память ЭМ предназначается для хранения части данных и ветви параллельной программы. Архитектура ВС с программируемой структурой относится к типу MIMD. Такие ВС по своим потенциальным архитектурным возможностям не уступают ни одному из перечисленных выше классов систем.

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

К пространственно-распределенным ВС относят макросистемы - системы сложной конфигурации, в которых в качестве функциональных элементов выступают пространственно-рассредоточенные вычислительные средства, основанные на моделях вычислителя и коллектива вычислителей, и сети связи, обеспечивающие взаимный теледоступ между средствами обработки информации.

Концепция вычислительных систем с программируемой структурой была сформулирована в Сибирском отделении АН СССР, первая такая система (“Минск-222”) была построена в 1965 - 1966 гг.

В 90-х годах 20 столетия получают широкое распространение кластерные вычислительные системы. В наиболее общей трактовке, кластерная ВС или кластер - это композиция множества вычислителей, сети связей между ними и программного обеспечения, предназначенная для параллельной обработки информации (реализации параллельных алгоритмов решения сложных задач). При формировании кластерной ВС могут быть использованы как стандартные промышленные компоненты, так и специально созданные средства.

Начало XXI в. ознаменовалось созданием пространственно-распределенных мультикластерных ВС как макроколлективов рассредоточенных кластеров, взаимодействующих между собой через локальные и глобальные сети (включая всемирную сеть Internet).

Архитектура современных ВС существенно отличается от изначальных канонов, доминирующее большинство систем являются мультиархитектурными. В зависимости от уровня рассмотрения их функциональных структур, они могут выглядеть и как MISD, и как SIMD, и как MIMD.



1.2 Распределенные ВС

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

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

К структурам современных ВС предъявляется ряд требований [1].

Простота вложения параллельного алгоритма решения сложной задачи в структуру ВС. Структура ВС должна быть адекватна достаточно широкому классу решаемых задач; настройка проблемно-ориентированных виртуальных конфигураций не должна быть связана со значительными накладными расходами.

Удобство адресации элементарных машин и “переноса” подсистем в пределах вычислительной системы. Вычислительная система должна предоставлять возможность пользователям создавать параллельные программы с виртуальными адресами ЭМ. Следовательно, структура ВС должна позволять реализовать простейший “механизм” преобразования виртуальных адресов ЭМ в реальные (физические) адреса машин системы. Необходимость организации одновременного решения нескольких задач на ВС (т.е. необходимость разделения пространства элементарных машин между задачами) обосновывает требование простоты перемещения подсистем в пределах системы (при сохранении их топологических свойств).

Осуществимость принципа близкодействия и минимума задержек при межмашинных передачах информации в ВС. Принцип близкодействия предопределяет реализацию обменов информацией между “удалёнными” друг от друга ЭМ через промежуточные машины системы. Следовательно, в условиях ограниченности числа связей у каждой ЭМ структура должна обеспечивать минимум задержек при “транзитных” передачах информации.

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

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

Коммутируемость структуры ВС. Вычислительная система должна быть приспособлена к реализации групповых межмашинных обменов информацией. Следовательно, структура ВС должна обладать способностью осуществлять заданное число одновременных непересекающихся взаимодействий между элементарными машинами.

Живучесть структуры ВС. Важным требованием к ВС в целом является обеспечение работоспособности при отказе её компонентов или даже подсистем. Основой функциональной целостности ВС как коллектива элементарных машин является живучесть структуры. Под последним понимается способность структуры ВС обеспечить связность требуемого числа работоспособных ЭМ в системе при ненадёжных линиях межмашинных связей.

Технологичность структур ВС. Структура сети межмашинных связей ВС не должна предъявлять особых требований к элементной базе, к технологии изготовления микропроцессорных БИС. Системы должны быть восприимчивы к массовой технологии, их “вычислительное ядро” должно формироваться из массовых микропроцессорных БИС. Последнее позволит достичь приемлемых значений технико-экономических показателей ВС.

Структурные задержки при передачах информации между машинами ВС определяются расстоянием (в смысле теории графов) между вершинами структуры, сопоставленными взаимодействующим машинам [1, 8]. Для оценки структурных задержек в вычислительных системах используются диаметр и средний диаметр структуры. Диаметр есть максимальное расстояние, определённое на множестве кратчайших путей между парами вершин структуры ВС:

,	(1.1)

а средний диаметр - 

,	(1.2)

где - расстояние, т.е. минимальное число рёбер, образующих путь из вершины в вершину; ; - число вершин, находящихся на расстоянии от любой выделенной вершины (однородного) графа .

Показателем оценивающим структурную коммутируемость ВС, является вектор-функция

, ,	(1.3)

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

Структурная живучесть ВС оценивается вектор-функцией

, ,	(1.4)

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

Для оценки производительности каналов связи между ЭМ системы используют [6] показатели: пропускная способность и латентность. Пропускная способность канала связи (bandwidth, throughput, channel
capacity) - наибольшее количество информации, передаваемой по каналу связи в единицу времени. Латентность (latency) - это задержка при передаче информации между ЭМ системы, вызванная программными и аппаратурными накладными расходами.

Введённые показатели позволяют осуществить с достаточной полнотой анализ структурных возможностей ВС.

Наиболее полно перечисленным выше требованиям удовлетворяют однородные структуры (т.е. описываемые однородными графами) [1, 6, 7, 8]. Такие структуры являются перспективными для формирования масштабируемых и больше масштабных вычислительных систем (в частности, ВС с программируемой структурой).

В компьютерной индустрии получили распространение n-мерные структуры вычислительных систем, известные сейчас как циркулянтные (CirculantSructures). Впервые они были определены и исследованы в Отделе вычислительных систем Института математики СО АН СССР в начале 70-х годов и первоначально назывались _графами [8]. По определению -граф или циркулянтная структура есть граф вида: , в котором:

- число вершин или порядок графа;

вершины помечены целыми числами по модулю , следовательно,

вершина соединена ребром (или является смежной) с вершинами

- множество целых чисел, называемых образующими, таких, что а для чисел наибольшим общим делителем является 1;

- размерность графа;

2n - степень вершины в графе.

В качестве примера рассмотрим -граф (рис. 1.1) или двумерный циркулянт вида: .

Графы вида , т.е. -графы или циркулянты с единичной образующей (LoopNetworks - петлевые структуры) интенсивно изучаются в последнее время. Циркулянтные структуры широко внедрены в практику вычислительных систем.

Целые числа отмечающие вершины -графа, называют адресами. Адресация вершин в таких структурах называется диофантовой (в честь древнегреческого математика из Александрии Диофанта, Diophantos, 3 век). В циркулянтных структурах при полном переносе какой-либо подструктуры (всех вершин подструктуры на одно и то же расстояние в одном из направлений) сохраняются все её свойства и адресация вершин. Следовательно, при диофантовой адресации элементарных машин ВС можно простыми средствами реконфигурации осуществить виртуальную адресацию вершин-машин и, следовательно, создавать отказоустойчивые параллельные программы, реализовывать мультипрограммные режимы обработки информации, исключать отказавшие вершины-машины из подсистем, а значит обеспечить живучесть ВС.

При этом алгоритм работы реконфигуратора структуры ВС сводится к изменению адресов у всех машин подсистемы по формуле:

, ,	(1.5)

где i - номер ЭМ, исключаемой из подсистемы, а j - номер машины, включаемый в подсистему,

В качестве структур ВС, допускающих масштабирование (изменение числа машин) без коренной перекоммутации уже имеющихся межмашинных связей, используются -графы [1, 6, 7] (введённые также в Отделе вычислительных систем ИМ СО АН СССР). В такие графы вкладываются -графы; -граф - это неориентированный однородный граф с числом и степенями вершин, соответственно, и v и значением обхвата g (рис. 1.2).

В -графах каждая вершина при входит в не менее v кратчайших простых циклов длиной (длина кратчайшего цикл в графе называется обхватом). При -граф является простым циклом с вершинами.

В зависимости от сложности задач и характера их поступления в теории вычислительных систем выделяют два основные режима функционирования ВС с программируемой структурой [1, 8]: моно- и мультипрограммный режимы.

В монопрограммном режиме для решения задачи используются все ресурсы ВС. Задача представляется в виде параллельной программы, число ветвей в которой либо фиксировано, либо допускает варьирование в заданном диапазоне. В качестве единицы ресурса выступает элементарная машина ВС. Все машины используются для решения задачи. Если максимальное число ветвей в параллельной программе менее общего числа ЭМ в системе, то “избыточные” машины используются для повышения надёжности функционирования ВС.

К мультипрограммным относят режимы [1, 8]:

обработки наборов задач;

обслуживания потоков задач.

При работе ВС в этих режимах одновременно решается несколько задач, следовательно, ресурсы системы делятся между ним.

При организации функционирования ВС в случае обработки набора задач учитывается не только количество задач в наборе, но их параметры: число ветвей в программе (точнее, число машин, на которых она будет выполняться), время решения или вероятностный закон распределения времени решения и др. Алгоритмы организации функционирования ВС [8] задают распределение задач по машинам и последовательность выполнения задач на них. В результате становится известным, в каком промежутке времени и на каких машинах (или на какой подсистеме) будет решаться любая задача набора.

Обслуживание потока задач на ВС - принципиально отличается от обработки наборов: задачи поступают в случайные моменты времени, их параметры случайны, следовательно, детерминированный выбор подсистем для решения тех или иных задач исключён. Для режима потока задач применяются методы и алгоритмы [8], обеспечивающие стохастически оптимальное функционирование вычислительных систем.

При работе ВС в любом из мультипрограммных режимов система представляется в виде композиции подсистем различных рангов. По мере решения задач эта композиция “автоматически” (с помощью операционной системы) реконфигурируется так, чтобы обеспечить её адекватность текущей мультипрограммной ситуации. Любая подсистема обладает всеми архитектурными свойствами системы, поэтому её организация при решении выделенной ей задачи может осуществляться теми же методами, что и организация работы всей ВС в первом режиме.

1.3 Кластерные ВС

Кластерные технологии стали логическим продолжением развития идей, заложенных в архитектуре MPP систем. Если процессорный модуль в MPP системе представляет собой законченную вычислительную систему, то следующий шаг напрашивается сам собой: почему бы в качестве таких вычислительных узлов не использовать обычные серийно выпускаемые компьютеры. Развитие коммуникационных технологий, а именно, появление высокоскоростного сетевого оборудования и специального программного обеспечения, такого как система MPI, реализующего механизм передачи сообщений над стандартными сетевыми протоколами, сделали кластерные технологии общедоступными. Сегодня не составляет большого труда создать небольшую кластерную систему, объединив вычислительные мощности компьютеров отдельной лаборатории или учебного класса.

Привлекательной чертой кластерных технологий является то, что они позволяют для достижения необходимой производительности объединять в единые вычислительные системы компьютеры самого разного типа, начиная от персональных компьютеров и заканчивая мощными суперкомпьютерами. Широкое распространение кластерные технологии получили как средство создания систем суперкомпьютерного класса из составных частей массового производства, что значительно удешевляет стоимость вычислительной системы.

Конечно, о полной эквивалентности этих систем говорить не приходится. Производительность систем с распределенной памятью очень сильно зависит от производительности коммуникационной среды. Коммуникационную среду можно достаточно полно охарактеризовать двумя параметрами: латентностью - временем задержки при посылке сообщения, и пропускной способностью - скоростью передачи информации. К примеру для компьютера Cray T3D эти параметры составляют соответственно 1 мкс и 480 Мб/сек, а для кластера, в котором в качестве коммуникационной среды использована сеть FastEthernet, 100 мкс и 10 Мб/сек. Это отчасти объясняет очень высокую стоимость суперкомпьютеров. При таких параметрах, как у рассматриваемого кластера, найдется не так много задач, которые могут эффективно решаться на достаточно большом числе процессоров.

Если говорить кратко, то кластер - это связанный набор полноценных компьютеров, используемый в качестве единого вычислительного ресурса. Преимущества кластерной системы перед набором независимых компьютеров очевидны. Во-первых, разработано множество диспетчерских систем пакетной обработки заданий, позволяющих послать задание на обработку кластеру в целом, а не какому-то отдельному компьютеру. Эти диспетчерские системы автоматически распределяют задания по свободным вычислительным узлам или буферизуют их при отсутствии таковых, что позволяет обеспечить более равномерную и эффективную загрузку компьютеров. Во-вторых, появляется возможность совместного использования вычислительных ресурсов нескольких компьютеров для решения одной задачи.

Для создания кластеров обычно используются либо простые однопроцессорные персональные компьютеры, либо двух- или четырех- процессорные SMP-серверы. При этом не накладывается никаких ограничений на состав и архитектуру узлов. Каждый из узлов может функционировать под управлением своей собственной операционной системы. Чаще всего используются стандартные ОС: Linux, FreeBSD, Solaris, Tru64 Unix, Windows NT. В тех случаях, когда узлы кластера неоднородны, то говорят о гетерогенных кластерах.

При создании кластеров можно выделить два подхода. Первый подход применяется при создании небольших кластерных систем. В кластер объединяются полнофункциональные компьютеры, которые продолжают работать и как самостоятельные единицы, например, компьютеры учебного класса или рабочие станции лаборатории. Второй подход применяется в тех случаях, когда целенаправленно создается мощный вычислительный ресурс. Тогда системные блоки компьютеров компактно размещаются в специальных стойках, а для управления системой и для запуска задач выделяется один или несколько полнофункциональных компьютеров, называемых хост-компьютерами. В этом случае нет необходимости снабжать компьютеры вычислительных узлов графическими картами, мониторами, дисковыми накопителями и другим периферийным оборудованием, что значительно удешевляет стоимость системы.

Разработано множество технологий соединения компьютеров в кластер. Наиболее широко в данное время используется технология FastEthernet. Это обусловлено простотой ее использования и низкой стоимостью коммуникационного оборудования. Однако за это приходится расплачиваться заведомо недостаточной скоростью обменов. В самом деле, это оборудование обеспечивает максимальную скорость обмена между узлами 10 Мб/сек, тогда как скорость обмена с оперативной памятью составляет 250 Мб/сек и выше. Разработчики пакета подпрограмм ScaLAPACK, предназначенного для решения задач линейной алгебры на многопроцессорных системах, в которых велика доля коммуникационных операций, формулируют следующим образом требование к многопроцессорной системе: "Скорость межпроцессорных обменов между двумя узлами, измеренная в Мб/сек, должна быть не менее 1/10 пиковой производительности вычислительного узла, измеренной в Mflops". Таким образом, если в качестве вычислительных узлов использовать компьютеры класса Pentium III 500 Мгц (пиковая производительность 500 Mflops), то аппаратура FastEthernet обеспечивает только 1/5 от требуемой скорости. Частично это положение может поправить переход на технологии GigabitEthernet.

Ряд фирм предлагают специализированные кластерные решения на основе более скоростных сетей, таких как SCI фирмы ScaliComputer (~100 Мб/сек) и Mirynet (~120 Мб/сек). Активно включились в поддержку кластерных технологий и фирмы-производители высокопроизводительных рабочих станций (SUN, HP, SiliconGraphics).

1.4 Параллельные программы и алгоритмы

Понятие параллельного алгоритма относится к фундаментальным в теории вычислительных систем. Параллельный алгоритм - это описание процесса обработки информации, ориентированное на реализацию в коллективе вычислителей. Такой алгоритм, в отличие от последовательного, предусматривает одновременное выполнение множества операций в пределах одного шага вычислений и как последовательный алгоритм сохраняет зависимость последующих этапов от результатов предыдущих.

Параллельный алгоритм решения общей задачи составляет основу параллельной программы, которая, в свою очередь, влияет на алгоритм функционирования коллектива вычислителей. Запись параллельного алгоритма на языке программирования, доступном коллективу вычислителей, и называют параллельной программой, а сам язык - параллельным. Параллельные алгоритмы и программы следует разрабатывать для тех задач, которые недоступны для решения на средствах, основанных на модели вычислителя. Эти задачи принято называть сложными или трудоемкими [1].

Методы и алгоритмы обработки информации, решения задач, как правило, - последовательные. Процесс “приспособления” методов к реализации на коллективе вычислителей или процесс “расщепления” последовательных алгоритмов решения сложных задач называется распараллеливанием.

Теоретическая и практическая деятельность по созданию параллельных алгоритмов и программ обработки информации называется параллельным программированием.

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



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

Пусть - количество операций, которые необходимо выполнить при решении задачи на ВС; n - число параллельных ветвей или число вычислителей, на которых решается задача, ; Тогда задачу, для которой выполняется условие

,	(1.6)

будем называть сложной, или системной, или трудоемкой, или с большим объемом вычислений [1].

В соотношении (1.6) - эмпирический коэффициент, . Очевидно, что имеет место зависимость от быстродействия каналов связей между вычислителями: при, где - время обращения к локальной памяти в вычислителе.

Задачу, которая имеет небольшой объем вычислений и, следовательно, не допускает эффективного распараллеливания, будем называть простой. Простая задача требует для своего решения одного вычислителя.

Одним из конструктивных приемов крупноблочного распараллеливания сложных задач является распараллеливание по циклам. Прием позволяет представить процесс решения задачи в виде параллельных ветвей, полученных расщеплением цикла на части, число которых в пределе равно числу повторений цикла.

Как правило, последовательные участки имеют место в начале и конце параллельной программы. На начальном участке осуществляется инициирование программы и ввод исходных данных, а на конечном - вывод результатов. При достаточно полном воплощении принципов модели коллектива вычислителей допустимы реализации в системе параллельных ввода и вывода информации. Последовательные участки в параллельной программе также могут иметь место, если используются негрупповые обмены информацией между ветвями (вычислителями).

Параллельная программа решения сложной задачи допускает представление в виде композиции: в которой есть -я ветвь программы, -допустимое число ветвей.

Пусть -алгоритм (и, следовательно, -программа) состоит из ветвей. Аксиоматически ясно, что произвольные схемы обмена информацией в -алгоритмах могут быть реализованы с помощью одного дифференцированного обмена. При этом обмене производится передача информации из одной ветви в любую другую ветвь или из одного вычислителя (передатчика) к другому вычислителю (приемнику), см. рис.1.4.(слева) Видно, что при дифференцированном обмене в работе находятся только два вычислителя, а остальные простаивают. Ясно, что такой обмен не может быть отнесен к числу эффективных, т.е таких, которые сводят к минимуму простои ресурсов ВС.

Анализ -алгоритмов и -программ показал, что многообразие встречающихся в них схем обмена информацией между ветвями сводится к пяти типам: дифференцированному (ДО), трансляционному (ТО), трансляционно-циклическому (ТЦО), конвейерно-параллельному (КПО) и коллекторному обменам (КО).

При трансляционном обмене(one-to-allbroadcast) (рис.1.4 слева) осуществляется передача одной и той же информации из одной (любой) ветви одновременно во все остальные ветви параллельного алгоритма.

Трансляционно-циклический обмен реализует трансляцию информации из каждой ветви во все остальные. Следовательно, если трансляционный обмен выполняется за 1 такт, то трансляционно-циклический - за тактов.

Конвейерно-параллельный обмен (all-to-allbroadcast) обеспечивает передачу информации между соседними ветвями; он реализуется за два такта (рис. 1.5). Так, например, при четном в первом такте осуществляется передача информации из ветвей соответственно в ветви ; во втором такте информация из последней последовательности ветвей поступает соответственно в ветви .

Коллекторный обмен - это по сути инвертированный трансляционный обмен (рис. 1.4. справа): т.е. вычислители, которые были приемниками, превращаются в передатчики и наоборот вычислитель-передатчик становится приемником. Вообще при коллекторном обмене в одну ветвь последовательно собирается информация из ветвей; такой обмен требует тактов и реализуется как последовательность из дифференцированных обменов.

1.5 Стандарт MPI

Название "интерфейс передачи сообщений", говорит само за себя. Это хорошо стандартизованный механизм для построения параллельных программ в модели обмена сообщениями. Существуют стандартные "привязки" MPI к языкам С/С++, Fortran 77/90. Существуют бесплатные и коммерческие реализации почти для всех суперкомпьютерных платформ, а также для сетей рабочих станций UNIX и Windows. В настоящее время MPI - наиболее широко используемый и динамично развивающийся интерфейс из своего класса.

Стандартизацией MPI занимается MPI Forum. Последняя версия стандарта - 2.2. В этой версии к MPI добавлены такие важные элементы функциональности, как динамическое управление процессами, односторонние коммуникации (Put/Get), параллельный ввод/вывод.

Стандарт MPI-2.2. включает следующие основные группы функций:

Дифференцированные обмены

Коллективные обмены

Контексты, группы и коммуникаторы

Топологии процессов

Динамическое порождение процессов и управление процессами

Односторонние коммуникации

Параллельный Ввод/Вывод

Обзор коммуникационных операций типа точка-точка

К операциям этого типа относятся две представленные в предыдущем разделе коммуникационные процедуры. В коммуникационных операциях типа точка-точка всегда участвуют не более двух процессов: передающий и принимающий. В MPI имеется множество функций, реализующих такой тип обменов. Многообразие объясняется возможностью организации таких обменов множеством способов [20]. Описанные в предыдущем разделе функции реализуют стандартный режим с блокировкой.

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

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

Как для блокирующих, так и неблокирующих операций MPI поддерживает четыре режима выполнения. Эти режимы касаются только функций передачи данных, поэтому для блокирующих и неблокирующих операций имеется по четыре функции посылки сообщения. В таблице 1.1 перечислены имена базовых коммуникационных функций типа точка-точка, имеющихся в библиотеке MPI.

Таблица 1.1 - Список коммуникационных функций дифференцированных обменов

Режимы выполнения	С блокировкой	Без блокировки
Стандартная посылка	MPI_Send	MPI_Isend
Синхронная посылка	MPI_Ssend	MPI_Issend
Буферизованная посылка	MPI_Bsend	MPI_Ibsend
Согласованная посылка	MPI_Rsend	MPI_Irsend
Прием информации	MPI_Recv	MPI_Irecv

Из таблицы хорошо виден принцип формирования имен функций. К именам базовых функций Send/Recv добавляются различные префиксы.

Префикс S (synchronous) - означает синхронный режим передачи данных. Операция передачи данных заканчивается только тогда, когда заканчивается прием данных. Функция нелокальная.

Префикс B (buffered) - означает буферизованный режим передачи данных. В адресном пространстве передающего процесса с помощью специальной функции создается буфер обмена, который используется в операциях обмена. Операция посылки заканчивается, когда данные помещены в этот буфер. Функция имеет локальный характер.

Префикс R (ready) - согласованный или подготовленный режим передачи данных. Операция передачи данных начинается только тогда, когда принимающий процессор выставил признак готовности приема данных, инициировав операцию приема. Функция нелокальная.

Префикс I (immediate) - относится к неблокирующим операциям.

Все функции передачи и приема сообщений могут использоваться в любой комбинации друг с другом. Функции передачи, находящиеся в одном столбце, имеют совершенно одинаковый синтаксис и отличаются только внутренней реализацией. Поэтому в дальнейшем будем рассматривать только стандартный режим, который в обязательном порядке поддерживают все реализации MPI.

1.6 Обзор коллективных операций

Набор операций типа точка-точка является достаточным для программирования любых алгоритмов, однако MPI вряд ли бы завоевал такую популярность, если бы ограничивался только этим набором коммуникационных операций. Одной из наиболее привлекательных сторон MPI является наличие широкого набора коллективных операций, которые берут на себя выполнение наиболее часто встречающихся при программировании действий. Например, часто возникает потребность разослать некоторую переменную или массив из одного процессора всем остальным. Каждый программист может написать такую процедуру с использованием операций MPI_Send/MPI_Recv, однако гораздо удобнее воспользоваться коллективной операцией MPI_Bcast. Причем гарантировано, что эта операция будет выполняться гораздо эффективнее, поскольку MPI-функция реализована с использованием внутренних возможностей коммуникационной среды [20].

Главное отличие коллективных операций от операций типа точка-точка состоит в том, что в них всегда участвуют все процессы, связанные с некоторым коммуникатором. Несоблюдение этого правила приводит либо к аварийному завершению задачи, либо к еще более неприятному зависанию задачи.

Набор коллективных операций включает:

Синхронизацию всех процессов с помощью барьеров (MPI_Barrier).

Коллективные коммуникационные операции, в число которых входят:

рассылка информации от одного процесса всем остальным членам некоторой области связи (MPI_Bcast);

сборка распределенного по процессам массива в один массив с сохранением его в адресном пространстве выделенного (root) процесса (MPI_Gather, MPI_Gatherv);

сборка распределенного массива в один массив с рассылкой его всем процессам некоторой области связи (MPI_Allgather, MPI_Allgatherv);

разбиение массива и рассылка его фрагментов всем процессам области связи (MPI_Scatter, MPI_Scatterv);

совмещенная операция MPI_Scatter/MPI_Gather, каждый процесс делит данные из своего буфера передачи и разбрасывает фрагменты всем остальным процессам, одновременно собирая фрагменты, посланные другими процессами в свой буфер приема (MPI_Alltoall, MPI_Alltoallv).

Глобальные вычислительные операции над данными, расположенными в адресных пространствах различных процессов:

с сохранением результата в адресном пространстве одного процесса (MPI_Reduce);

с рассылкой результата всем процессам (MPI_Allreduce);

совмещенная операция MPI_Reduce/MPI_Scatter (MPI_Reduce_scatter);

префиксная редукция (MPI_Scan).

Работа с группами и коммуникаторами

Часто в приложениях возникает потребность ограничить область коммуникаций некоторым набором процессов, которые составляют подмножество исходного набора. Для выполнения каких-либо коллективных операций внутри этого подмножества из них должна быть сформирована своя область связи, описываемая своим коммуникатором. Для решения таких задач MPI поддерживает два взаимосвязанных механизма. Во-первых, имеется набор функций для работы с группами процессов как упорядоченными множествами, и, во-вторых, набор функций для работы с коммуникаторами для создания новых коммуникаторов как описателей новых областей связи.

Группа представляет собой упорядоченное множество процессов. Каждый процесс идентифицируется переменной целого типа. Идентификаторы процессов образуют непрерывный ряд, начинающийся с 0. В MPI вводится специальный тип данных MPI_Group и набор функций для работы с переменными и константами этого типа. Существует две предопределенных группы:

MPI_GROUP_EMPTY - группа, не содержащая ни одного процесса;

MPI_GROUP_NULL - значение возвращаемое, когда группа не может быть создана.

Созданная группа не может быть модифицирована (расширена или усечена), может быть только создана новая группа. Интересно отметить, что при инициализации MPI не создается группы, соответствующей коммуникатору MPI_COMM_WORLD. Она должна создаваться специальной функцией явным образом.

Коммуникатор представляет собой скрытый объект с некоторым набором атрибутов, а также правилами его создания, использования и уничтожения. Коммуникатор описывает некоторую область связи. Одной и той же области связи может соответствовать несколько коммуникаторов, но даже в этом случае они не являются тождественными и не могут участвовать во взаимном обмене сообщениями. Если данные посылаются через один коммуникатор, процесс-получатель может получить их только через тот же самый коммуникатор.

В MPI существует два типа коммуникаторов:

intracommunicator - описывает область связи некоторой группы процессов;

intercommunicator - служит для связи между процессами двух различных групп.

Наиболее популярными реализациями стандарта MPI являются библиотеки MPICH и OpenMPI.

Барьерная синхронизация

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

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

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



2. ИССЛЕДОВАНИЕ АЛГОРИТМОВ БАРРЕРНОЙ СИНХРОНИЗАЦИИ

2.1 Алгоритмы барьерной синхронизации

В этом разделе будут представлены алгоритмы барьерной синхронизации: Dissemination, Recursive Doubling, Combining Tree. Каждый алгоритм можно логически разделить на 3 фазы. Алгоритм инициализируется на первой фазе (резервирование общих объектов или расчете рангов). Это должно быть сделано только 1 раз при инициализации или перенастройки коммуникатора. Фаза 2 должна быть выполнена на каждом узле каждый раз, когда будет вызываться операция MPI_Barrier. На этой фазе все ветви связываются друг с другом, пока одна или все ветви не узнают, что каждый узел достиг своего вызова MPI_Barrier. Третья фаза требуется только тогда, когда не все ветви знают, что барьер был достигнут всеми другими ветвями.

В соответствии с выше написанным, алгоритмы Dissemination и Recursive Doubling логически можно разбить на 2 фазы, а алгоритм Combining Tree можно разбить на 3 фазы.

Алгоритм Dissemination

Алгоритм Dissemination, введенный Hengsen, Finkel and Manber в 1988г. [20], допускает реализацию барьерной синхронизации для произвольного количества ветвей в параллельной программе. Пусть имеем p ветвей, пронумерованных от 0 до p - 1. Этот алгоритм логически можно разделить на этапов. На каждом этапе i-тая ветвь обменивается сообщением нулевой длины с j-той ветвью (синхронизация i-той и j-той ветви) по формуле

,	(2.1)



Где i - номер синхронизирующейся ветви, i меняется от 0 до p-1;

j - номер синхронизирующейся ветви, j меняется от 0 до p-1;

p - количество ветвей в параллельной программе;

s - номер этапа синхронизации, s меняется от 0 до .

Пример работы алгоритма Dissemination для 6 ветвей изображен на рисунке 2.1.

Ниже приведен псевдокод алгоритма Dissemantion.

procedure Dissemination(comm)

dist = 1

while dist < s do

send = (rank + dist) mod p

recv = (rank + p - dist) mod p

SendRecv(NULL, 0, send, NULL, 0, recv)

dist = dist * 2

end while

end procedure

Алгоритм Recursive Doubling

Алгоритм Recursive Doubling допускает реализацию барьерной синхронизации только для случая когда, количество ветвей в параллельной программе кратно степени двойки. Пусть имеем p ветвей, пронумерованных от 0 до p - 1. Этот алгоритм логически можно разделить на этапов. На каждом этапе i-тая ветвь обменивается сообщением нулевой длины с j-той ветвью (синхронизация i-той и j-той ветви) по формуле

,	(2.2)

Где i - номер синхронизирующейся ветви, i меняется от 0 до p-1;

j - номер синхронизирующейся ветви, j меняется от 0 до p-1;

- операция сложения по модулю 2;

s - номер этапа синхронизации, s меняется от 0 до .

Пример работы алгоритма Dissemination для 6 ветвей изображен на рисунке 2.2.

Ниже приведен псевдокод алгоритма Recursive Doubling.

procedure RecursiveDoubling(comm)

dist = 1

while dist < s do

remote = rank ^ dist /* XOR */

SendRecv(NULL, 0, remote, NULL, 0, remote)

dist = dist * 2

end while

end procedure

Алгоритм Combining Tree

Алгоритм Combining Tree, введенный Yew, Tzeng and Lawrie [20], допускает реализацию барьерной синхронизации для произвольного количества ветвей в параллельной программе. Пусть имеем p ветвей, пронумерованных от 0 до p - 1. Пусть все ветви являются главными. Этот алгоритм можно разделить на этапов. На i-том этапе группа главных ветвей разбивается на подгруппы фиксированного размера t, t меняется от 2 до p, i меняется от 0 до . В подгруппе можно выделить главную ветвь с номером 0 и подчиненные ей ветви с остальными номерами. В пределах подгруппы происходит обмен сообщениями нулевой длины между главной ветвью и подчиненных ей (синхронизация ветвей в пределах подгруппы). После синхронизации ветвей внутри подгруппы главными ветвями группы становятся главные ветви подгрупп. На этом данный этап алгоритма заканчивается, далее следует i + 1-ый этап с новыми главными ветвями. После этапа остается одна главная ветвь, которой известно, что все ветви группы достигли точки барьера. На этапе оставшаяся главная ветвь передает сообщение нулевой длины (информирует о том, что все ветви достигли точки барьера) остальным ветвям.

Пример работы алгоритма Dissemination для 6 ветвей изображен на рисунке 2.3.

Ниже приведен псевдокод алгоритма Combining Tree.

procedure CombiningTree(comm)

stage = 0

nstage = ceil((log p) / (log groupsize))

while stage < nstage do

powgroup = pow(groupsize, stage)

relnodeid = rank / powgroup

grprank = relnodeid mod groupsize

if relnodeid - (int)relnodeid == 0.0 do

if grprank == 0 do

remote = rank - grprank * powgroup

Send(NULL, 0, remote)

else

i = 1

while i < groupsize do

remote = rank + i * powgroup

Recv(NULL, 0, remote)

end while

end else

end if

end while

if rank == 0 do

remote = 1

while remote < p do

Send(NULL, 0, remote)

remote = remote + 1

end while

else

Recv(NULL, 0, 0)

end else

end procedure

2.2 Оптимизация алгоритмов барьерной синхронизации

Оптимизация алгоритма Combining Tree

Внутри подгрупп блокирующие дифференцированные (типа точка-точка) операции (MPI_Send/MPI_Recv) обмена сообщениями можно заменить на не блокирующие (MPI_Isend/MPI_Irecv). Данный способ сокращает время синхронизации внутри подгруппы.

Анализируя этап с номером , можно прийти к выводу, что это широковещательная рассылка 0 процесса. Данный этап можно заменить на первые этапов в обратном порядке, т.е. после -ого этапа пойдут -ый, -ой, …, 2-ой, 1-ый, 0-ой этапы, с тем отличием, что изначальная операция дифференцированного обмена MPI_Isend заменяется на операцию MPI_Irecv, а изначальная операция MPI_Irecv на операцию MPI_Isend. В результате получим что, на этапе 0 процесс уведомит процессы из своей группы (на этапе) о том, что все процессы дошли до точки барьера, в свою очередь, процессы этой группы уведомят процессы своих групп (на этапе, и т.д.). После -ом этапа каждый процесс будет знать, что все процессы дошли до точки барьера. В результате общее количество этапов будет равно . Данное изменение третьей фазы алгоритма приводит к уменьшению времени ее времени, следовательно, и к уменьшению времени работы всего алгоритма.

Оптимизированную версию алгоритма Combining Tree можно представить следующим псевдокодом.