Анализ эффективности параллельных вычислений

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

(4.3)

где и ? есть параметры модели Хокни (латентность и пропускная способность сети передачи данных), а m задает объем пересылаемых данных для одного тела физической системы.

Для второго способа информационного обмена, как уже отмечалось ранее, объем пересылаемых данных на разных итерациях операции сбора данных различается. На первой итерации объем пересылаемых сообщений составляет Nm/p, на второй этот объем увеличивается вдвое и оказывается равным 2Nm/p и т.д. В общем случае, для итерации с номером i объем сообщений оценивается как 2i-1Nm/p. Как результат, длительность выполнения операции сбора данных в этом случае может быть определена при помощи следующего выражения:

(4.4)

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

Этапы разработки параллельных алгоритмов

Рассмотрим более подробно изложенную выше методику разработки параллельных алгоритмов. В значительной степени данная методика опирается на подход, впервые разработанный в [[32]], и, как отмечалось ранее, включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы (см. рис. 4.1). Для демонстрации приводимых рекомендаций далее будет использоваться учебная задача поиска максимального значения среди элементов матрицы A (такая задача возникает, например, при численном решении систем линейных уравнений для определения ведущего элемента метода Гаусса):

(4.1)

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

Контрольные вопросы

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

Краткий обзор лекции

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

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

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

Масштабирование и распределение подзадач по процессорам

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

Масштабирование набора подзадач

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

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

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

Для рассматриваемой учебной задачи поиска максимального значения агрегация вычислений может состоять в объединении отдельных строк в группы (ленточная схема разделения матрицы – см. рис. 4.3а), при декомпозиции подзадач строки исходной матрицы могут разбиваться на несколько частей (блоков).

Список контрольных вопросов, предложенный в [[32]] для оценки правильности этапа масштабирования, выглядит следующим образом:

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

Моделирование параллельных программ

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

Рис. 4.2.  Модель параллельной программы в виде графа "процессы - каналы"

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

Дадим дополнительные пояснения для используемых понятий в модели "процессы – каналы":

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

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

Следует отметить важное достоинство рассмотренной модели "процессы – каналы" – в ней проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ.

Обзор литературы

Рассмотренная в лекции методика разработки параллельных алгоритмов впервые была предложена в [[32]]. В этой работе изложение методики проводится более детально, кроме того, в ней содержится несколько примеров ее использования для разработки параллельных методов для решения ряда вычислительных задач.

Полезной при рассмотрении вопросов проектирования и разработки параллельных алгоритмов может оказаться также работа [[63]].

Гравитационная задача N тел более подробно рассматривается в [[5]].

Параллельное решение гравитационной задачи N тел

Многие задачи в области физики сводятся к операциям обработки данных для каждой пары объектов имеющейся физической системы. Такой задачей является, в частности, проблема, широко известная в литературе как гравитационная задача N тел (или просто задача N тел) – см., например, [[5]]. В самом общем виде задача может быть описана следующим образом.

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

Очевидный алгоритм решения задачи N тел состоит в рассмотрении на каждом шаге моделирования всех пар объектов физической системы и выполнении для каждой получаемой пары всех необходимых расчетов. Как результат, при таком подходе время выполнения одной итерации моделирования будет составлять1)

(4.2)

где ? есть время перевычисления параметров одной пары тел.

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

Принципы разработки параллельных методов

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

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

Рис. 4.1.  Общая схема разработки параллельных алгоритмов

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

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

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

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

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

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

Распределение подзадач между процессорами

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

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

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

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

Разделение вычислений на независимые части

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

Рис. 4.3.  Разделение данных матрицы: а) ленточная схема, б) блочная схема

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

Рис. 4.4.  Регулярные одно-, дву- и трехмерные структуры базовых подзадач после декомпозиции данных

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

Выбор способа разделения вычислений не вызывает каких-либо затруднений – очевидный подход состоит в выборе в качестве базовой подзадачи всего набора вычислений, связанных с обработкой данных какого-либо одного тела физической системы.

Очень часто функциональная декомпозиция может

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

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

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

Рис. 4.5.  Структура информационных связей учебной задачи

Для оценки корректности этапа разделения вычислений на независимые части можно воспользоваться контрольным списком вопросов, предложенных в [[32]]:

выполненная декомпозиция не увеличивает объем вычислений и необходимый объем памяти?возможна ли при выбранном способе декомпозиции равномерная загрузка всех имеющихся процессоров?достаточно ли выделенных частей процесса вычислений для эффективной загрузки имеющихся процессоров (с учетом возможности увеличения их количества)?

Выделение информационных зависимостей

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

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

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

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

Для оценки правильности этапа выделения информационных зависимостей можно воспользоваться контрольным списком вопросов, предложенным в [[32]]:

соответствует ли вычислительная сложность подзадач интенсивности их информационных взаимодействий?является ли одинаковой интенсивность информационных взаимодействий для разных подзадач?является ли схема информационного взаимодействия локальной?не препятствует ли выявленная информационная зависимость параллельному решению подзадач?

Разработайте схему параллельных вычислений, используя

1. Разработайте схему параллельных вычислений, используя рассмотренную в разделе методику проектирования и разработки параллельных методов:
для задачи поиска максимального значения среди минимальных элементов строк матрицы (такая задача имеет место для решения матричных игр)
(обратите особое внимание на ситуацию, когда число процессоров превышает размер матрицы, т.е. p>N); для задачи вычисления определенного интеграла с использованием метода прямоугольников
(описание методов интегрирования дано, например, в [[47]]).
2. Разработайте схему параллельных вычислений для задачи умножения матрицы на вектор, используя рассмотренную в разделе методику проектирования и разработки параллельных методов.

Аварийное завершение параллельной программы

Для корректного завершения параллельной программы в случае непредвиденных ситуаций необходимо использовать функцию:

int MPI_Abort(MPI_Comm comm, int errorcode),

где

comm — коммуникатор, процессы которого необходимо аварийно остановить; errorcode — код возврата из параллельной программы.

Эта функция корректно прерывает выполнение параллельной программы, оповещая об этом событии среду MPI, в отличие от функций стандартной библиотеки алгоритмического языка C, таких, как abort или terminate. Обычное ее использование заключается в следующем:

MPI_Abort(MPI_COMM_WORLD, MPI_ERR_OTHER);

Декартовы топологии (решетки)

Декартовы топологии, в которых множество процессов представляется в виде прямоугольной решетки (см. п. 1.4.1 и рис. 1.7), а для указания процессов используется декартова система координат, широко применяются во многих задачах для описания структуры имеющихся информационных зависимостей. В числе примеров таких задач – матричные алгоритмы (см. лекции 6 и 7) и сеточные методы решения дифференциальных уравнений в частных производных (см. лекцию 11).

Для создания декартовой топологии (решетки) в MPI предназначена функция:

int MPI_Cart_create(MPI_Comm oldcomm, int ndims, int *dims, int *periods, int reorder, MPI_Comm *cartcomm),

где

oldcomm — исходный коммуникатор;ndims — размерность декартовой решетки;dims — массив длины ndims, задает количество процессов в каждом измерении решетки;periods — массив длины ndims, определяет, является ли решетка периодической вдоль каждого измерения;reorder — параметр допустимости изменения нумерации процессов;cartcomm — создаваемый коммуникатор с декартовой топологией процессов.

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

Для пояснения назначения параметров функции MPI_Cart_create рассмотрим пример создания двумерной решетки 4x4, в которой строки и столбцы имеют кольцевую структуру (за последним процессом следует первый процесс):

// Создание двумерной решетки 4x4 MPI_Comm GridComm; int dims[2], periods[2], reorder = 1; dims[0] = dims[1] = 4; periods[0] = periods[1] = 1; MPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &GridComm);

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

Для определения декартовых координат процесса по его рангу можно воспользоваться функцией:

int MPI_Cart_coords(MPI_Comm comm, int rank, int ndims, int *coords),

где

comm — коммуникатор с топологией решетки;rank — ранг процесса, для которого определяются декартовы координаты;ndims — размерность решетки;coords — возвращаемые функцией декартовы координаты процесса.

Обратное действие – определение ранга процесса по его декартовым координатам – обеспечивается при помощи функции:

int MPI_Cart_rank(MPI_Comm comm, int *coords, int *rank),

где

comm — коммуникатор с топологией решетки;coords — декартовы координаты процесса;rank — возвращаемый функцией ранг процесса.

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

int MPI_Cart_sub(MPI_Comm comm, int *subdims, MPI_Comm *newcomm),

где

comm — исходный коммуникатор с топологией решетки;subdims — массив для указания, какие измерения должны остаться в создаваемой подрешетке;newcomm — создаваемый коммуникатор с подрешеткой.

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

Для пояснения функции MPI_Cart_sub дополним ранее рассмотренный пример создания двумерной решетки и определим коммуникаторы с декартовой топологией для каждой строки и столбца решетки в отдельности:

// Создание коммуникаторов для каждой строки и столбца решетки MPI_Comm RowComm, ColComm; int subdims[2]; // Создание коммуникаторов для строк subdims[0] = 0; // фиксации измерения subdims[1] = 1; // наличие данного измерения в подрешетке MPI_Cart_sub(GridComm, subdims, &RowComm); // Создание коммуникаторов для столбцов subdims[0] = 1; subdims[1] = 0; MPI_Cart_sub(GridComm, subdims, &ColComm);

В приведенном примере для решетки размером 4х4 создаются 8 коммуникаторов, по одному для каждой строки и столбца решетки. Для каждого процесса определяемые коммуникаторы RowComm и ColComm соответствуют строке и столбцу процессов, к которым данный процесс принадлежит.

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


лекцию 3). В зависимости от периодичности измерения решетки, по которому выполняется сдвиг, различаются два типа данной операции:

циклический сдвиг на k элементов вдоль измерения решетки – в этой операции данные от процесса i пересылаются процессу , где dim есть размер измерения, вдоль которого производится сдвиг;линейный сдвиг на k позиций вдоль измерения решетки – в этом варианте операции данные от процесса i пересылаются процессу i+k (если таковой существует).

Функция MPI_Cart_shift обеспечивает получение рангов процессов, с которыми текущий процесс (процесс, вызвавший функцию MPI_Cart_shift) должен выполнить обмен данными:

int MPI_Card_shift(MPI_Comm comm, int dir, int disp, int *source, int *dst),

где

comm — коммуникатор с топологией решетки;dir — номер измерения, по которому выполняется сдвиг;disp — величина сдвига (при отрицательных значениях сдвиг производится к началу измерения);source — ранг процесса, от которого должны быть получены данные;dst — ранг процесса, которому должны быть отправлены данные.

Следует отметить, что функция MPI_Cart_shift только определяет ранги процессов, между которыми должен быть выполнен обмен данными в ходе операции сдвига. Непосредственная передача данных может быть выполнена, например, при помощи функции MPI_Sendrecv.

Дополнительные операции редукции данных

Рассмотренная в п. 5.2.3.2 функция MPI_Reduce обеспечивает получение результатов редукции данных только на одном процессе. Для получения результатов редукции данных на каждом из процессов коммуникатора необходимо использовать функцию редукции и рассылки:

int MPI_Allreduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype type, MPI_Op op, MPI_Comm comm),

где

sendbuf — буфер памяти с отправляемым сообщением;recvbuf — буфер памяти для результирующего сообщения;count — количество элементов в сообщениях;type — тип элементов сообщений;op — операция, которая должна быть выполнена над данными;comm — коммуникатор, в рамках которого выполняется операция.

Функция MPI_Allreduce выполняет рассылку между процессами всех результатов операции редукции. Возможность управления распределением этих данных между процессами предоставляется функций MPI_Reduce_scatter.

И еще один вариант операции сбора и обработки данных, при котором обеспечивается получение всех частичных результатов редуцирования, может быть реализован при помощи функции:

int MPI_Scan(void *sendbuf, void *recvbuf, int count, MPI_Datatype type, MPI_Op op, MPI_Comm comm),

где

sendbuf — буфер памяти с отправляемым сообщением;recvbuf — буфер памяти для результирующего сообщения;count — количество элементов в сообщениях;type — тип элементов сообщений;op — операция, которая должна быть выполнена над данными;comm — коммуникатор, в рамках которого выполняется операция.

Общая схема выполнения функции MPI_Scan показана на рис. 5.7. Элементы получаемых сообщений представляют собой результаты обработки соответствующих элементов передаваемых процессами сообщений, при этом для получения результатов на процессе с рангом i, 0i<n, используются данные от процессов, ранг которых меньше или равен i, т.е.

где есть операция, задаваемая при вызове функции MPI_Scan.

Рис. 5.7.  Общая схема операции редукции с получением частичных результатов обработки данных

в 1997 г. Несмотря на

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

Для знакомства со стандартом MPI-2 может быть рекомендован информационный ресурс http://www.mpiforum.org, а также работа [[42]]. Здесь же дадим краткую характеристику дополнительных возможностей стандарта MPI-2:

динамическое порождение процессов, при котором процессы параллельной программы могут создаваться и уничтожаться в ходе выполнения;одностороннее взаимодействие процессов, что позволяет быть инициатором операции передачи и приема данных только одному процессу;параллельный ввод/вывод, обеспечивающий специальный интерфейс для работы процессов с файловой системой;расширение возможностей коллективных операций, в числе которых, например, взаимодействие через глобальные коммуникаторы (intercommunicator);интерфейс для алгоритмических языков C++ и Fortran 90.

Формирование сообщений при помощи упаковки и распаковки данных

Наряду с рассмотренными в п. 5.5.2 методами конструирования производных типов в MPI предусмотрен и явный способ сборки и разборки сообщений, содержащих значения разных типов и располагаемых в разных областях памяти.

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

int MPI_Pack(void *data, int count, MPI_Datatype type, void *buf, int bufsize, int *bufpos, MPI_Comm comm),

где

data — буфер памяти с элементами для упаковки;count — количество элементов в буфере;type — тип данных для упаковываемых элементов;buf — буфер памяти для упаковки;bufsize — размер буфера в байтах;bufpos — позиция для начала записи в буфер (в байтах от начала буфера);comm — коммуникатор для упакованного сообщения.

Функция MPI_Pack упаковывает count элементов из буфера data в буфер упаковки buf, начиная с позиции bufpos. Общая схема процедуры упаковки показана на рис. 5.8а.

Рис. 5.8.  Общая схема упаковки и распаковки данных

Начальное значение переменной bufpos должно быть сформировано до начала упаковки и далее устанавливается функцией MPI_Pack. Вызов функции MPI_Pack осуществляется последовательно для упаковки всех необходимых данных. Так, в ранее рассмотренном примере набора переменных a, b и n для их упаковки необходимо выполнить:

bufpos = 0; MPI_Pack(&a, 1, MPI_DOUBLE, buf, buflen, &bufpos, comm); MPI_Pack(&b, 1, MPI_DOUBLE, buf, buflen, &bufpos, comm); MPI_Pack(&n, 1, MPI_INT, buf, buflen, &bufpos, comm);

Для определения необходимого размера буфера для упаковки может быть применена функция:

int MPI_Pack_size(int count, MPI_Datatype type, MPI_Comm comm, int *size),

где

count — количество элементов в буфере;type — тип данных для упаковываемых элементов;comm — коммуникатор для упакованного сообщения;size — рассчитаный размер буфера.

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

После получения сообщения с типом MPI_PACKED данные могут быть распакованы при помощи функции:

int MPI_Unpack(void *buf, int bufsize, int *bufpos, void *data, int count, MPI_Datatype type, MPI_Comm comm),

где

buf — буфер памяти с упакованными данными;bufsize — размер буфера в байтах;bufpos — позиция начала данных в буфере (в байтах от начала буфера);data — буфер памяти для распаковываемых данных;count — количество элементов в буфере;type — тип распаковываемых данных;comm — коммуникатор для упакованного сообщения.

Функция MPI_Unpack распаковывает, начиная с позиции bufpos, очередную порцию данных из буфера buf и помещает распакованные данные в буфер data. Общая схема процедуры распаковки показана на рис. 5.8б.

Начальное значение переменной bufpos должно быть сформировано до начала распаковки и далее устанавливается функцией MPI_Unpack. Вызов функции MPI_Unpack осуществляется последовательно для распаковки всех упакованных данных, при этом порядок распаковки должен соответствовать порядку упаковки. Так, в ранее рассмотренном примере упаковки для распаковки упакованных данных необходимо выполнить:

bufpos = 0; MPI_Unpack(buf, buflen, &bufpos, &a, 1, MPI_DOUBLE, comm); MPI_Unpack(buf, buflen, &bufpos, &b, 1, MPI_DOUBLE, comm); MPI_Unpack(buf, buflen, &bufpos, &n, 1, MPI_INT, comm);

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

Индексный способ конструирования

При индексном способе конструирования производного типа данных в MPI используются функции:

int MPI_Type_indexed(int count, int blocklens[], int indices[], MPI_Data_type oldtype, MPI_Datatype *newtype) и int MPI_Type_hindexed(int count, int blocklens[], MPI_Aint indices[], MPI_Data_type oldtype, MPI_Datatype *newtype),

где

count — количество блоков;blocklens — количество элементов в каждом блоке;indices — смещение каждого блока от начала типа;oldtype — исходный тип данных;newtype — новый определяемый тип данных.

Как следует из описания, при индексном способе новый производный тип создается как набор блоков разного размера из элементов исходного типа, при этом между блоками могут иметься разные промежутки по памяти. Для пояснения данного способа можно привести пример конструирования типа для описания верхней треугольной матрицы размером n?n:

// Конструирование типа для описания верхней треугольной матрицы for ( i = 0, i < n; i++ ) { blocklens[i] = n - i; indices [i] = i * n + i; } MPI_Type_indexed(n, blocklens, indices, &UTMatrixType, &ElemType).

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

Следует отметить, что существует еще одна дополнительная функция MPI_Type_create_indexed_block индексного способа конструирования для определения типов с блоками одинакового размера (данная функция предусматривается стандартом MPI-2).

Инициализация и завершение MPI-программ

Первой вызываемой функцией MPI должна быть функция:

int MPI_Init(int *argc, char ***argv),

где

argc — указатель на количество параметров командной строки,argv — параметры командной строки,

применяемая для инициализации среды выполнения MPI-программы. Параметрами функции являются количество аргументов в командной строке и адрес указателя на массив символов текста самой командной строки.

Последней вызываемой функцией MPI обязательно должна являться функция:

int MPI_Finalize(void).

Как результат, можно отметить, что структура параллельной программы, разработанная с использованием MPI, должна иметь следующий вид:

#include "mpi.h" int main(int argc, char *argv[]) { <программный код без использования функций MPI> MPI_Init(&agrc, &argv); <программный код с использованием функций MPI> MPI_Finalize(); <программный код без использования функций MPI> return 0; }

Следует отметить:

файл mpi.h содержит определения именованных констант, прототипов функций и типов данных библиотеки MPI;функции MPI_Init и MPI_Finalize являются обязательными и должны быть выполнены (и только один раз) каждым процессом параллельной программы;перед вызовом MPI_Init может быть использована функция MPI_Initialized для определения того, был ли ранее выполнен вызов MPI_Init, а после вызова MPI_Finalize – MPI_Finalized1) аналогичного предназначения.

Рассмотренные примеры функций дают представление синтаксиса именования функций в MPI. Имени функции предшествует префикс MPI, далее следует одно или несколько слов названия, первое слово в имени функции начинается с заглавного символа, слова разделяются знаком подчеркивания. Названия функций MPI, как правило, поясняют назначение выполняемых функцией действий.

Коллективные операции передачи данных

Как уже отмечалось ранее, под коллективными операциями в MPI понимаются операции над данными, в которых принимают участие все процессы используемого коммуникатора. Выделение основных видов коллективных операций было выполнено в лекции 3. Часть коллективных операций уже была рассмотрена в п.5.2.3 – это операции передачи от одного процесса всем процессам коммуникатора (широковещательная рассылка) и операции обработки данных, полученных на одном процессе от всех процессов (редукция данных).

Рассмотрим далее оставшиеся базовые коллективные операции передачи данных.

Контрольные вопросы

Какой минимальный набор средств является достаточным для организации параллельных вычислений в системах с распределенной памятью?В чем состоит важность стандартизации средств передачи сообщений?Что следует понимать под параллельной программой?В чем различие понятий процесса и процессора?Какой минимальный набор функций MPI позволяет начать разработку параллельных программ?Как описываются передаваемые сообщения?Как можно организовать прием сообщений от конкретных процессов?Как определить время выполнения MPI-программы?В чем различие парных и коллективных операций передачи данных?Какая функция MPI обеспечивает передачу данных от одного процесса всем процессам?Что понимается под операцией редукции?В каких ситуациях следует применять барьерную синхронизацию?Какие режимы передачи данных поддерживаются в MPI?Как организуется неблокирующий обмен данными в MPI?В чем состоит понятие тупика? Когда функция одновременного выполнения передачи и приема гарантирует отсутствие тупиковых ситуаций?Какие коллективные операции передачи данных предусмотрены в MPI?Что понимается под производным типом данных в MPI?Какие способы конструирования типов имеются в MPI?В каких ситуациях может быть полезна упаковка и распаковка данных?Что понимается в MPI под коммуникатором?Для чего может потребоваться создание новых коммуникаторов?Что понимается в MPI под виртуальной топологией?Какие виды топологий предусмотрены в MPI?Для чего может оказаться полезным использование виртуальных топологий?В чем состоят особенности разработки параллельных программ с использованием MPI на алгоритмическом языке Fortran?Какие основные дополнительные возможности предусмотрены в стандарте MPI-2?

Краткий обзор лекции

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

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

В подразделе 5.1 рассматривается ряд понятий и определений, являющихся основополагающими для стандарта MPI. Так, дается представление о параллельной программе> как множестве одновременно выполняемых процессов. При этом процессы могут выполняться на разных процессорах, но на одном процессоре могут располагаться и несколько процессов (в этом случае их исполнение осуществляется в режиме разделения времени). Далее приводится краткая характеристика понятий для операций передачи сообщений, типов данных, коммуникаторов и виртуальных топологий.

В подразделе 5.2 проводится быстрое и простое введение в разработку параллельных программ с использованием MPI. Излагаемого в подразделе материала достаточно для начала разработки параллельных программ разного уровня сложности.

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

В подразделе 5.4 рассматриваются коллективные операции передачи данных.
Изложение материала соответствует последовательности изучения коммуникационных операций, использованной в лекции 3. Основной вывод данного подраздела состоит в том, что MPI обеспечивает поддержку практически всех основных операций информационных обменов между процессами.

В подразделе 5.5 излагается материал, связанный с использованием в MPI производных типов данных. В подразделе представлены все основные способы конструирования производных типов – непрерывный, векторный, индексный и структурный. Обсуждается также возможность явного формирования сложных сообщений при помощи упаковки и распаковки данных.

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

В подразделе 5.7 рассматриваются возможности MPI по использованию виртуальных топологий. В подразделе представлены топологии, поддерживаемые MPI, – прямоугольная решетка произвольной размерности (декартова топология) и топология графа любого необходимого вида.

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

MPI: основные понятия и определения

Рассмотрим ряд понятий и определений, являющихся основополагающими для стандарта MPI.

Начальное знакомство с коллективными операциями передачи данных

Функции MPI_Send и MPI_Recv, рассмотренные в п. 5.2.1, обеспечивают возможность выполнения парных операций передачи данных между двумя процессами параллельной программы. Для выполнения коммуникационных коллективных операций, в которых принимают участие все процессы коммуникатора, в MPI предусмотрен специальный набор функций. В данном подразделе будут рассмотрены три такие функции, широко применяемые даже при разработке сравнительно простых параллельных программ; полное же представление коллективных операций будет дано в подразделе 5.4.

Для демонстрации применения рассматриваемых функций MPI будет использоваться учебная задача суммирования элементов вектора x (см. подраздел 2.5):

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

Непрерывный способ конструирования

При непрерывном способе конструирования производного типа данных в MPI используется функция:

int MPI_Type_contiguous(int count, MPI_Data_type oldtype, MPI_Datatype *newtype),

где

count — количество элементов исходного типа;oldtype — исходный тип данных;newtype — новый определяемый тип данных.

Как следует из описания, новый тип newtype создается как count элементов исходного типа oldtype. Например, если исходный тип данных имеет карту типа

{(MPI_INT, 0), (MPI_DOUBLE, 8)},

то вызов функции MPI_Type_contiguous с параметрами

MPI_Type_contiguous(2, oldtype, &newtype);

приведет к созданию типа данных с картой типа

{(MPI_INT, 0), (MPI_DOUBLE, 8), (MPI_INT, 16), (MPI_DOUBLE, 24)}.

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

Объявление производных типов и их удаление

Рассмотренные в предыдущем пункте функции конструирования позволяют определить производный тип данных. Дополнительно перед использованием созданный тип должен быть объявлен при помощи функции:

int MPI_Type_commit(MPI_Datatype *type),

где

type – объявляемый тип данных.

При завершении использования производный тип должен быть аннулирован при помощи функции:

int MPI_Type_free(MPI_Datatype *type),

где

type – аннулируемый тип данных.

Обобщенная передача данных от одного процесса всем процессам

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

int MPI_Scatter(void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int root, MPI_Comm comm),

где

sbuf, scount, stype — параметры передаваемого сообщения (scount определяет количество элементов, передаваемых на каждый процесс);rbuf, rcount, rtype — параметры сообщения, принимаемого в процессах;root — ранг процесса, выполняющего рассылку данных;comm — коммуникатор, в рамках которого выполняется передача данных.

Рис. 5.4.  Общая схема операции обобщенной передачи данных от одного процесса всем процессам

При вызове этой функции процесс с рангом root произведет передачу данных всем другим процессам в коммуникаторе. Каждому процессу будет отправлено scount элементов. Процесс с рангом 0 получит блок данных из sbuf элементов с индексами от 0 до scount-1, процессу с рангом 1 будет отправлен блок из sbuf элементов с индексами от scount до 2*scount-1 и т.д. Тем самым, общий размер отправляемого сообщения должен быть равен scount * p элементов, где p есть количество процессов в коммуникаторе comm.

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

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

Пример использования функции MPI_Scatter рассматривается в лекции 6 при разработке параллельных программ умножения матрицы на вектор.

Обобщенная передача данных от всех процессов одному процессу

Операция обобщенной передачи данных от всех процессов одному процессу (сбор данных) является двойственной к процедуре распределения данных (см. рис. 5.5). Для выполнения этой операции в MPI предназначена функция:

int MPI_Gather(void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, int root, MPI_Comm comm),

где

sbuf, scount, stype — параметры передаваемого сообщения;rbuf, rcount, rtype — параметры принимаемого сообщения;root — ранг процесса, выполняющего сбор данных;comm — коммуникатор, в рамках которого выполняется передача данных.

Рис. 5.5.  Общая схема операции обобщенной передачи данных от всех процессов одному процессу

При выполнении функции MPI_Gather каждый процесс в коммуникаторе передает данные из буфера sbuf на процесс с рангом root. Процесс с рангом root собирает все получаемые данные в буфере rbuf (размещение данных в буфере осуществляется в соответствии с рангами процессов – отправителей сообщений). Для того чтобы разместить все поступающие данные, размер буфера rbuf должен быть равен scount * p элементов, где p есть количество процессов в коммуникаторе comm.

Функция MPI_Gather также определяет коллективную операцию, и ее вызов при выполнении сбора данных должен быть обеспечен в каждом процессе коммуникатора.

Следует отметить, что при использовании функции MPI_Gather сборка данных осуществляется только на одном процессе. Для получения всех собираемых данных на каждом из процессов коммуникатора необходимо применять функцию сбора и рассылки:

int MPI_Allgather(void *sbuf, int scount, MPI_Datatype stype, void *rbuf, int rcount, MPI_Datatype rtype, MPI_Comm comm),

где

sbuf, scount, stype — параметры передаваемого сообщения;rbuf, rcount, rtype — параметры принимаемого сообщения;comm — коммуникатор, в рамках которого выполняется передача данных.

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

Пример использования функции MPI_Gather рассматривается в лекции 6 при разработке параллельных программ умножения матрицы на вектор.

Общая характеристика среды выполнения MPI-программ

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

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

Запуск MPI-программы также зависит от среды выполнения, но в большинстве случаев данное действие выполняется при помощи команды mpirun2). В числе возможных параметров этой команды:

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

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

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

Дополнительная информация по средам выполнения параллельных программ на кластерных системах может быть получена, например, в [[70], [71]].

Общая передача данных от всех процессов всем процессам

Передача данных от всех процессов всем процессам является наиболее общей операцией передачи данных (см. рис. 5.6). Выполнение данной операции может быть обеспечено при помощи функции:

int MPI_Alltoall(void *sbuf,int scount,MPI_Datatype stype, void *rbuf,int rcount,MPI_Datatype rtype,MPI_Comm comm),

где

sbuf, scount, stype — параметры передаваемых сообщений;rbuf, rcount, rtype — параметры принимаемых сообщений;comm — коммуникатор, в рамках которого выполняется передача данных.

Рис. 5.6.  Общая схема операции передачи данных от всех процессов всем процессам

При выполнении функции MPI_Alltoall каждый процесс в коммуникаторе передает данные из scount элементов каждому процессу (общий размер отправляемых сообщений в процессах должен быть равен scount * p элементов, где p есть количество процессов в коммуникаторе comm) и принимает сообщения от каждого процесса.

Вызов функции MPI_Alltoall при выполнении операции общего обмена данными должен быть выполнен в каждом процессе коммуникатора.

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

Пример использования функции MPI_Alltoall рассматривается в лекции 6 при разработке параллельных программ умножения матрицы на вектор как задание для самостоятельного выполнения.

Обзор литературы

Имеется ряд источников, в которых может быть получена информация о MPI. Прежде всего, это информационный ресурс Интернет с описанием стандарта MPI: http://www.mpiforum.org. Одна из наиболее распространенных реализаций MPI – библиотека MPICH – представлена на http://www-unix.mcs.anl.gov/mpi/mpich (библиотека MPICH2 с реализацией стандарта MPI-2 содержится на http://www-unix.mcs.anl.gov/mpi/mpich2). Русскоязычные материалы о MPI имеются на сайте http://www.parallel.ru.

Среди опубликованных изданий могут быть рекомендованы работы [[4], [40] – [42], [57]]. Описание стандарта MPI-2 может быть получено в [[42]]. Среди русскоязычных изданий могут быть рекомендованы работы [[2], [4], [12]].

Следует отметить также работу [[63]], в которой изучение MPI проводится на примере ряда типовых задач параллельного программирования – матричных вычислений, сортировки, обработки графов и др.

Одновременное выполнение передачи и приема

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

Достижение эффективного и гарантированного одновременного выполнения операций передачи и приема данных может быть обеспечено при помощи функции MPI:

int MPI_Sendrecv(void *sbuf,int scount,MPI_Datatype stype, int dest, int stag, void *rbuf,int rcount,MPI_Datatype rtype, int source,int rtag, MPI_Comm comm, MPI_Status *status),

где

sbuf, scount, stype, dest, stag — параметры передаваемого сообщения;rbuf, rcount, rtype, source, rtag — параметры принимаемого сообщения;comm — коммуникатор, в рамках которого выполняется передача данных;status — структура данных с информацией о результате выполнения операции.

Как следует из описания, функция MPI_Sendrecv передает сообщение, описываемое параметрами (sbuf, scount, stype, dest, stag), процессу с рангом dest и принимает сообщение в буфер, определяемый параметрами (rbuf, rcount, rtype, source, rtag), от процесса с рангом source.

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

int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype type, int dest, int stag, int source, int rtag, MPI_Comm comm, MPI_Status* status),

где

buf, count, type — параметры передаваемого сообщения;dest — ранг процесса, которому отправляется сообщение;stag — тег для идентификации отправляемого сообщения;source — ранг процесса, от которого выполняется прием сообщения;rtag — тег для идентификации принимаемого сообщения;comm — коммуникатор, в рамках которого выполняется передача данных;status — структура данных с информацией о результате выполнения операции.

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

Операции передачи данных

Основу MPI составляют операции передачи сообщений. Среди предусмотренных в составе MPI функций различаются парные (point-to-point) операции между двумя процессами и коллективные (collective) коммуникационные действия для одновременного взаимодействия нескольких процессов.

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

Как уже отмечалось ранее, в стандарт MPI включено большинство основных коллективных операций передачи данных – см. подразделы 5.2 и 5.4.

Операции передачи данных между двумя процессами

Продолжим начатое в п. 5.2.1 изучение функций MPI для выполнения операций передачи данных между процессами параллельной программы.

Определение количества и ранга процессов

Определение количества процессов в выполняемой параллельной программе осуществляется при помощи функции:

int MPI_Comm_size(MPI_Comm comm, int *size),

где

comm — коммуникатор, размер которого определяется,size — определяемое количество процессов в коммуникаторе.

Для определения ранга процесса используется функция:

int MPI_Comm_rank(MPI_Comm comm, int *rank),

где

comm — коммуникатор, в котором определяется ранг процесса,rank — ранг процесса в коммуникаторе.

Как правило, вызов функций MPI_Comm_size и MPI_Comm_rank выполняется сразу после MPI_Init для получения общего количества процессов и ранга текущего процесса:

#include "mpi.h" int main(int argc, char *argv[]) { int ProcNum, ProcRank; <программный код без использования функций MPI> MPI_Init(&agrc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); <программный код с использованием функций MPI> MPI_Finalize(); <программный код без использования функций MPI> return 0; }

Следует отметить:

коммуникатор MPI_COMM_WORLD, как отмечалось ранее, создается по умолчанию и представляет все процессы выполняемой параллельной программы;ранг, получаемый при помощи функции MPI_Comm_rank, является рангом процесса, выполнившего вызов этой функции, т. е. переменная ProcRank примет различные значения у разных процессов.

Определение времени выполнение MPI-программы

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

Получение текущего момента времени обеспечивается при помощи функции:

double MPI_Wtime(void),

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

double t1, t2, dt; t1 = MPI_Wtime(); ѕ t2 = MPI_Wtime(); dt = t2 – t1;

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

double MPI_Wtick(void),

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

Организация неблокирующих обменов данными между процессами

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

MPI обеспечивает возможность неблокированного выполнения операций передачи данных между двумя процессами. Наименование неблокирующих аналогов образуется из названий соответствующих функций путем добавления префикса I (Immediate). Список параметров неблокирующих функций содержит обычный набор параметров исходных функций и один дополнительный параметр request с типом MPI_Request (в функции MPI_Irecv отсутствует также параметр status):

int MPI_Isend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request), int MPI_Issend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request), int MPI_Ibsend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request), int MPI_Irsend(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm, MPI_Request *request), int MPI_Irecv(void *buf, int count, MPI_Datatype type, int source, int tag, MPI_Comm comm, MPI_Request *request).

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

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

int MPI_Test(MPI_Request *request, int *flag, MPI_status *status),

где

request — дескриптор операции, определенный при вызове неблокирующей функции;flag — результат проверки (true, если операция завершена);status — результат выполнения операции обмена (только для завершенной операции).

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

MPI_Isend(buf, count, type, dest, tag, comm, &request); ѕ do { ѕ MPI_Test(&request, &flag, &status); } while (!flag);

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

int MPI_Wait(MPI_Request *request, MPI_status *status),

где

request — дескриптор операции, определенный при вызове неблокирующей функции;status — результат выполнения операции обмена (только для завершенной операции).

Кроме рассмотренных, MPI содержит ряд дополнительных функций проверки и ожидания неблокирующих операций обмена:

MPI_Testall — проверка завершения всех перечисленных операций обмена;MPI_Waitall — ожидание завершения всех операций обмена;MPI_Testany — проверка завершения хотя бы одной из перечисленных операций обмена;MPI_Waitany — ожидание завершения любой из перечисленных операций обмена;MPI_Testsome — проверка завершения каждой из перечисленных операций обмена;MPI_Waitsome — ожидание завершения хотя бы одной из перечисленных операций обмена и оценка состояния по всем операциям.

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

Основы MPI

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

Параллельное программирование на основе MPI

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

Решение всех перечисленных вопросов и обеспечивает интерфейс передачи данных (message passing interface – MPI).

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

Подобный способ организации параллельных вычислений получил наименование модели "одна программа множество процессов" (single program multiple processes or SPMP1)).

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

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

Следует отметить, что попытки создания программных средств передачи данных между процессорами начали предприниматься практически сразу с появлением локальных компьютерных сетей – ряд таких средств, представлен, например, в работах [[2], [5], [24]] и многих других. Однако подобные средства часто были неполными и, самое главное, являлись несовместимыми. Таким образом, одна из самых серьезных проблем в программировании – переносимость программ при переводе программного обеспечения на другие компьютерные системы – проявлялась при разработке параллельных программ в максимальной степени. Как результат, уже с 90-х годов стали предприниматься усилия по стандартизации средств организации передачи сообщений в многопроцессорных вычислительных системах. Началом работ, непосредственно приведших к появлению MPI, послужило проведение рабочего совещания по стандартам для передачи сообщений в среде распределенной памяти (the Workshop on Standards for Message Passing in a Distributed Memory Environment, Williamsburg, Virginia, USA, April 1992). По итогам совещания была образована рабочая группа, позднее преобразованная в международное сообщество MPI Forum, результатом деятельности которых явилось создание и принятие в 1994 г. стандарта интерфейса передачи сообщений (message passing interface – MPI) версии 1.0. В последующие годы стандарт MPI последовательно развивался. В 1997 г. был принят стандарт MPI версии 2.0.

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


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

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

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

Передача данных от одного процесса всем процессам программы

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

MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); for (int i = 1; i < ProcNum; i++) MPI_Send(&x, n, MPI_DOUBLE, i, 0, MPI_COMM_WORLD);

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

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

int MPI_Bcast(void *buf, int count, MPI_Datatype type, int root, MPI_Comm comm),

где

buf, count, type — буфер памяти с отправляемым сообщением (для процесса с рангом 0) и для приема сообщений (для всех остальных процессов);root — ранг процесса, выполняющего рассылку данных;comm — коммуникатор, в рамках которого выполняется передача данных.

Функция MPI_Bcast осуществляет рассылку данных из буфера buf, содержащего count элементов типа type, с процесса, имеющего номер root, всем процессам, входящим в коммуникатор comm (см. рис. 5.1).

Следует отметить:

функция MPI_Bcast определяет коллективную операцию, и, тем самым, при выполнении необходимых рассылок данных вызов функции MPI_Bcast должен быть осуществлен всеми процессами указываемого коммуникатора (см. далее пример программы);указываемый в функции MPI_Bcast буфер памяти имеет различное назначение у разных процессов: для процесса с рангом root, которым осуществляется рассылка данных, в этом буфере должно находиться рассылаемое сообщение, а для всех остальных процессов указываемый буфер предназначен для приема передаваемых данных;все коллективные операции "несовместимы" с парными операциями — так, например, принять широковещательное сообщение, отосланное с помощью MPI_Bcast, функцией MPI_Recv нельзя, для этого можно задействовать только MPI_Bcast.

Рис. 5.1.  Общая схема операции передачи данных от одного процесса всем процессам

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

Программа 5.2. Параллельная программа суммирования числовых значений

Пример 5.2.

(html, txt)

В приведенной программе функция DataInitialization осуществляет подготовку начальных данных. Необходимые данные могут быть введены с клавиатуры, прочитаны из файла или сгенерированы при помощи датчика случайных чисел – подготовка этой функции предоставляется как задание для самостоятельной разработки.

Передача данных от всех процессов одному процессу Операция редукции

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

int MPI_Reduce(void *sendbuf, void *recvbuf, int count, MPI_Datatype type, MPI_Op op, int root, MPI_Comm comm),

где

sendbuf — буфер памяти с отправляемым сообщением;recvbuf — буфер памяти для результирующего сообщения (только для процесса с рангом root);count — количество элементов в сообщениях;type — тип элементов сообщений;op — операция, которая должна быть выполнена над данными;root — ранг процесса, на котором должен быть получен результат;comm — коммуникатор, в рамках которого выполняется операция.

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

Помимо данного стандартного набора операций могут быть определены и новые дополнительные операции непосредственно самим пользователем библиотеки MPI – см., например, [[4], [40] – [42], [57]].

Общая схема выполнения операции сбора и обработки данных на одном процессе показана на табл. 5.2. Элементы получаемого сообщения на процессе root представляют собой результаты обработки соответствующих элементов передаваемых процессами сообщений, т.е.:

где есть операция, задаваемая при вызове функции MPI_Reduce (для пояснения на рис. 5.3 показан пример выполнения функции редукции данных).

Следует отметить:

функция MPI_Reduce определяет коллективную операцию, и, тем самым, вызов функции должен быть выполнен всеми процессами указываемого коммуникатора.
При этом все вызовы функции должны содержать одинаковые значения параметров count, type, op, root, comm;передача сообщений должна быть выполнена всеми процессами, результат операции будет получен только процессом с рангом root;выполнение операции редукции осуществляется над отдельными элементами передаваемых сообщений. Так, например, если сообщения содержат по два элемента данных и выполняется операция суммирования MPI_SUM, то результат также будет состоять из двух значений, первое из которых будет содержать сумму первых элементов всех отправленных сообщений, а второе значение будет равно сумме вторых элементов сообщений соответственно;не все сочетания типа данных type и операции op возможны, разрешенные сочетания перечислены в табл. 5.3.

Таблица 5.2. Базовые (предопределенные) типы операций MPI для функций редукции данныхОперацииОписание

MPI_MAX	Определение максимального значения
MPI_MIN	Определение минимального значения
MPI_SUM	Определение суммы значений
MPI_PROD	Определение произведения значений
MPI_LAND	Выполнение логической операции "И" над значениями сообщений
MPI_BAND	Выполнение битовой операции "И" над значениями сообщений
MPI_LOR	Выполнение логической операции "ИЛИ" над значениями сообщений
MPI_BOR	Выполнение битовой операции "ИЛИ" над значениями сообщений
MPI_LXOR	Выполнение логической операции исключающего "ИЛИ" над значениями сообщений
MPI_BXOR	Выполнение битовой операции исключающего "ИЛИ" над значениями сообщений
MPI_MAXLOC	Определение максимальных значений и их индексов
MPI_MINLOC	Определение минимальных значений и их индексов

Рис. 5.2.  Общая схема операции сбора и обработки на одном процессе данных от всех процессов



Таблица 5.3. Разрешенные сочетания операции типа операнда в операции редукцииОперацииДопустимый тип операндов для алгоритмического языка C

MPI_MAX, MPI_MIN, MPI_SUM, MPI_PROD	Целый, вещественный
MPI_LAND, MPI_LOR, MPI_LXOR	Целый
MPI_BAND, MPI_BOR, MPI_BXOR	Целый, байтовый
MPI_MINLOC, MPI_MAXLOC	Целый, вещественный

Рис. 5.3.  Пример выполнения операции редукции при суммировании пересылаемых данных для трех процессов (в каждом сообщении 4 элемента, сообщения собираются на процессе с рангом 2)

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

// Сборка частичных сумм на процессе с рангом 0 MPI_Reduce(&ProcSum, &TotalSum, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);

Передача сообщений

Для передачи сообщения процесс- отправитель должен выполнить функцию:

int MPI_Send(void *buf, int count, MPI_Datatype type, int dest, int tag, MPI_Comm comm),

где

buf — адрес буфера памяти, в котором располагаются данные отправляемого сообщения;count — количество элементов данных в сообщении;type — тип элементов данных пересылаемого сообщения;dest — ранг процесса, которому отправляется сообщение;tag — значение-тег, используемое для идентификации сообщения;comm — коммуникатор, в рамках которого выполняется передача данных.

Для указания типа пересылаемых данных в MPI имеется ряд базовых типов, полный список которых приведен в табл. 5.1.

Таблица 5.1. Базовые (пpедопpеделенные) типы данных MPI для алгоритмического языка C

Тип данных MPIТип данных C

MPI_BYTE
MPI_CHAR	signed char
MPI_DOUBLE	double
MPI_FLOAT	float
MPI_INT	int
MPI_LONG	long
MPI_LONG_DOUBLE	long double
MPI_PACKED
MPI_SHORT	short
MPI_UNSIGNED_CHAR	unsigned char
MPI_UNSIGNED	unsigned int
MPI_UNSIGNED_LONG	unsigned long
MPI_UNSIGNED_SHORT	unsigned short

Следует отметить:

отправляемое сообщение определяется через указание блока памяти (буфера), в котором это сообщение располагается. Используемая для указания буфера триада (buf, count, type) входит в состав параметров практически всех функций передачи данных;процессы, между которыми выполняется передача данных, в обязательном порядке должны принадлежать коммуникатору, указываемому в функции MPI_Send;параметр tag используется только при необходимости различения передаваемых сообщений, в противном случае в качестве значения параметра может быть использовано произвольное положительное целое число2) (см. также описание функции MPI_Recv).

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

Пример использования функции будет представлен после описания функции MPI_Recv.

Первая параллельная программа с использованием MPI

Рассмотренный набор функций оказывается достаточным для разработки параллельных программ1). Приводимая ниже программа является стандартным начальным примером для алгоритмического языка C.

Программа 5.1. Первая параллельная программа с использованием MPI

#include <stdio.h> #include "mpi.h" int main(int argc, char* argv[]){ int ProcNum, ProcRank, RecvRank; MPI_Status Status; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &ProcNum); MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); if ( ProcRank == 0 ){ // Действия, выполняемые только процессом с рангом 0 printf("\n Hello from process %3d", ProcRank); for (int i = 1; i < ProcNum; i++ ) { MPI_Recv(&RecvRank, 1, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &Status); printf("\n Hello from process %3d", RecvRank); } } else // Сообщение, отправляемое всеми процессами, // кроме процесса с рангом 0 MPI_Send(&ProcRank,1,MPI_INT,0,0,MPI_COMM_WORLD); MPI_Finalize(); return 0; }

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

Hello from process 0 Hello from process 2 Hello from process 1 Hello from process 3

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

MPI_Recv(&RecvRank, 1, MPI_INT, i, MPI_ANY_TAG, MPI_COMM_WORLD, &Status).

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

Следует отметить еще один важный момент: разрабатываемая с применением MPI программа, как в данном частном варианте, так и в самом общем случае, используется для порождения всех процессов параллельной программы а значит, должна определять вычисления, выполняемые всеми этими процессами. Можно сказать, что MPI- программа является некоторой "макропрограммой", различные части которой используются разными процессами. Так, например, в приведенном примере программы выделенные рамкой участки программного кода не выполняются одновременно ни одним из процессов. Первый выделенный участок с функцией приема MPI_Recv исполняется только процессом с рангом 0, второй участок с функцией передачи MPI_Send задействуется всеми процессами, за исключением нулевого процесса.

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


Общая схема MPI-программы в этом случае будет иметь вид:

MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); if ( ProcRank == 0 ) DoProcess0(); else if ( ProcRank == 1 ) DoProcess1(); else if ( ProcRank == 2 ) DoProcess2();

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

MPI_Comm_rank(MPI_COMM_WORLD, &ProcRank); if ( ProcRank == 0 ) DoManagerProcess(); else DoWorkerProcesses();

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

MPI_ERR_BUFFER — неправильный указатель на буфер;MPI_ERR_TRUNCATE — сообщение превышает размер приемного буфера;MPI_ERR_COMM — неправильный коммуникатор;MPI_ERR_RANK — неправильный ранг процесса и др.

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

Понятие коммуникаторов

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

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

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

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

Подробное рассмотрение возможностей MPI для работы с группами и коммуникаторами будет выполнено в подразделе 5.6.

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

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

Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP). Данный программный код, представленный в виде исполняемой программы, должен быть доступен в момент запуска параллельной программы на всех используемых процессорах. Исходный программный код для исполняемой программы разрабатывается на алгоритмических языках C или Fortran с применением той или иной реализации библиотеки MPI.

Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI-программ и в ходе вычислений не может меняться без применения специальных, но редко задействуемых средств динамического порождения процессов и управления ими, появившихся в стандарте MPI версии 2.0. Все процессы программы последовательно перенумерованы от 0 до p-1, где p есть общее количество процессов. Номер процесса именуется рангом процесса.

Понятие производного типа данных

В самом общем виде под производным типом данных в MPI можно понимать описание набора значений предусмотренного в MPI типа, причем в общем случае описываемые значения не обязательно непрерывно располагаются в памяти. Задание типа в MPI принято осуществлять при помощи карты типа (type map) в виде последовательности описаний входящих в тип значений; каждое отдельное значение описывается указанием типа и смещения адреса месторасположения от некоторого базового адреса, т.е.

TypeMap = {(type0, disp0),...,(typen-1, dispn-1)}.

Часть карты типа с указанием только типов значений именуется в MPI сигнатурой типа:

TypeSignature = {type0,...,typen-1}.

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

Поясним рассмотренные понятия на следующем примере. Пусть в сообщение должны входить значения переменных:

double a; /* адрес 24 */ double b; /* адрес 40 */ int n; /* адрес 48 */

Тогда производный тип для описания таких данных должен иметь карту типа следующего вида:

{(MPI_DOUBLE, 0), (MPI_DOUBLE, 16), (MPI_INT, 24)}

Дополнительно для производных типов данных в MPI используется следующий ряд новых понятий:

нижняя граница типа ;верхняя граница типа ;протяженность типа .

Согласно определению, нижняя граница есть смещение для первого байта значений рассматриваемого типа данных. Соответственно, верхняя граница представляет собой смещение для байта, располагающегося вслед за последним элементом рассматриваемого типа данных. При этом величина смещения для верхней границы может быть округлена вверх с учетом требований выравнивания адресов. Так, одно из требований, которые налагают некоторые реализации языков C и Fortran, состоит в том, чтобы адрес элемента был кратен длине этого элемента в байтах. Например, если тип int занимает четыре байта, то адрес элемента типа int должен нацело делиться на четыре.
Именно это требование и отражается в определении верхней границы типа данных MPI. Поясним данный момент на ранее рассмотренном примере набора переменных a, b и n, для которого нижняя граница равна 0, а верхняя принимает значение 32 (величина округления 6 или 4 в зависимости от размера типа int). Здесь следует отметить, что требуемое выравнивание определяется по типу первого элемента данных в карте типа.

Следует также указать на различие понятий "протяженность" и "размер типа". Протяженность – это размер памяти в байтах, который нужно отводить для одного элемента производного типа. Размер типа данных – это число байтов, которые занимают данные (разность между адресами последнего и первого байтов данных). Различие в значениях протяженности и размера опять же в величине округления для выравнивания адресов. Так, в рассматриваемом примере размер типа равен 28, а протяженность – 32 (предполагается, что тип int занимает четыре байта).

Для получения значения протяженности типа в MPI предусмотрена функция:

int MPI_Type_extent(MPI_Datatype type, MPI_Aint *extent),

где

type — тип данных, протяженность которого отыскивается;extent — протяженность типа.

Размер типа можно найти, используя функцию:

int MPI_Type_size(MPI_Datatype type, MPI_Aint *size),

где

type — тип данных, размер которого отыскивается;size — размер типа.

Определение нижней и верхней границ типа может быть выполнено при помощи функций:

int MPI_Type_lb(MPI_Datatype type, MPI_Aint *disp) и int MPI_Type_ub(MPI_Datatype type, MPI_Aint *disp),

где

type — тип данных, нижняя граница которого отыскивается;disp — нижняя/верхняя граница типа.

Важной и необходимой при конструировании производных типов является функция получения адреса переменной:

int MPI_Address(void *location, MPI_Aint *address),

где

location — адрес памяти;address — адрес памяти в переносимом MPI-формате

(следует отметить, что данная функция является переносимым вариантом средств получения адресов в алгоритмических языках C и Fortran).

Прием сообщений

Для приема сообщения процесс-получатель должен выполнить функцию:

int MPI_Recv(void *buf, int count, MPI_Datatype type, int source, int tag, MPI_Comm comm, MPI_Status *status),

где

buf, count, type — буфер памяти для приема сообщения, назначение каждого отдельного параметра соответствует описанию в MPI_Send;source — ранг процесса, от которого должен быть выполнен прием сообщения;tag — тег сообщения, которое должно быть принято для процесса;comm — коммуникатор, в рамках которого выполняется передача данных;status – указатель на структуру данных с информацией о результате выполнения операции приема данных.

Следует отметить:

буфер памяти должен быть достаточным для приема сообщения. При нехватке памяти часть сообщения будет потеряна и в коде завершения функции будет зафиксирована ошибка переполнения; с другой стороны, принимаемое сообщение может быть и короче, чем размер приемного буфера, в таком случае изменятся только участки буфера, затронутые принятым сообщением;типы элементов передаваемого и принимаемого сообщения должны совпадать;при необходимости приема сообщения от любого процесса- отправителя для параметра source может быть указано значение MPI_ANY_SOURCE (в отличие от функции передачи MPI_Send, которая отсылает сообщение строго определенному адресату);при необходимости приема сообщения с любым тегом для параметра tag может быть указано значение MPI_ANY_TAG (опять-таки, при использовании функции MPI_Send должно быть указано конкретное значение тега);в отличие от параметров "процесс-получатель" и "тег", параметр "коммуникатор" не имеет значения, означающего "любой коммуникатор";параметр status позволяет определить ряд характеристик принятого сообщения:status.MPI_SOURCE — ранг процесса – отправителя принятого сообщения;status.MPI_TAG — тег принятого сообщения.

Приведенные значения MPI_ANY_SOURCE и MPI_ANY_TAG иногда называют джокерами.

Значение переменной status позволяет определить количество элементов данных в принятом сообщении при помощи функции:

int MPI_Get_count(MPI_Status *status, MPI_Datatype type, int *count),

где

status — статус операции MPI_Recv;type — тип принятых данных;count — количество элементов данных в сообщении.

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

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

Рассылка данных на все процессы

#include <math.h> #include <stdio.h> #include <stdlib.h> #include "mpi.h" int main(int argc, char* argv[]){ double x[100], TotalSum, ProcSum = 0.0; int ProcRank, ProcNum, N=100, k, i1, i2; MPI_Status Status; // Инициализация MPI_Init(&argc,&argv); MPI_Comm_size(MPI_COMM_WORLD,&ProcNum); MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank); // Подготовка данных if ( ProcRank == 0 ) DataInitialization(x,N); // Рассылка данных на все процессы MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD); // Вычисление частичной суммы на каждом из процессов // на каждом процессе суммируются элементы вектора x от i1 до i2 k = N / ProcNum; i1 = k * ProcRank; i2 = k * ( ProcRank + 1 ); if ( ProcRank == ProcNum-1 ) i2 = N; for ( int i = i1; i < i2; i++ ) ProcSum = ProcSum + x[i]; // Сборка частичных сумм на процессе с рангом 0 if ( ProcRank == 0 ) { TotalSum = ProcSum; for ( int i=1; i < ProcNum; i++ ) { MPI_Recv(&ProcSum,1,MPI_DOUBLE,MPI_ANY_SOURCE,0, MPI_COMM_WORLD, &Status); TotalSum = TotalSum + ProcSum; } } else // Все процессы отсылают свои частичные суммы MPI_Send(&ProcSum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD); // Вывод результата if ( ProcRank == 0 ) printf("\nTotal Sum = %10.2f",TotalSum); MPI_Finalize(); return 0; }

Пример 5.2.

Закрыть окно

#include
#include
#include
#include "mpi.h"
int main(int argc, char* argv[]){
double x[100], TotalSum, ProcSum = 0.0;
int ProcRank, ProcNum, N=100, k, i1, i2;
MPI_Status Status;
// Инициализация
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);
MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);
// Подготовка данных
if ( ProcRank == 0 ) DataInitialization(x,N);
// Рассылка данных на все процессы
MPI_Bcast(x, N, MPI_DOUBLE, 0, MPI_COMM_WORLD);
// Вычисление частичной суммы на каждом из процессов
// на каждом процессе суммируются элементы вектора x от i1 до i2
k = N / ProcNum;
i1 = k * ProcRank;
i2 = k * ( ProcRank + 1 );
if ( ProcRank == ProcNum-1 ) i2 = N;
for ( int i = i1; i < i2; i++ )
ProcSum = ProcSum + x[i];
// Сборка частичных сумм на процессе с рангом 0
if ( ProcRank == 0 ) {
TotalSum = ProcSum;
for ( int i=1; i < ProcNum; i++ ) {
MPI_Recv(&ProcSum,1,MPI_DOUBLE,MPI_ANY_SOURCE,0, MPI_COMM_WORLD, &Status);
TotalSum = TotalSum + ProcSum;
}
}
else // Все процессы отсылают свои частичные суммы
MPI_Send(&ProcSum, 1, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD);
// Вывод результата
if ( ProcRank == 0 )
printf("\nTotal Sum = %10.2f",TotalSum);
MPI_Finalize();
return 0;
}

Производные типы данных в MPI

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

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

Вид коллективной операцииОбщее описание и оценка сложностиФункции MPIПримеры использования

Передача от одного процесса всем процессам (широковещательная рассылка)	п. 3.2.2	MPI_Bcast п. 5.2.3.1	п. 5.2.3.1
Сбор и обработка данных на одном процессе от всех процессов (редукция данных)	пп. 3.2.2, 3.2.3	MPI_Reduce п. 5.2.3.2	п. 5.2.3.2
- то же с рассылкой результатов всем процессам	пп. 3.2.2, 3.2.3	MPI_Allreduce MPI_Reduce_scatter п. 5.4.4
- то же с получением частичных результатов обработки	пп. 3.2.2, 3.2.3	MPI_Scan п. 5.4.4
Обобщенная передача от одного процесса всем процессам (распределение данных)	п. 3.2.4	MPI_Scatter MPI_Scatterv п. 5.4.1	Лекция 6
Обобщенная передача от всех процессов одному процессу (сбор данных)	п. 3.2.4	MPI_Gather MPI_Gatherv п. 5.4.2	Лекция 6
- то же с рассылкой результатов всем процессам	п. 3.2.4	MPI_Allgather MPI_Allgatherv п. 5.4.2
Обобщенная передача данных от всех процессов всем процессам	п. 3.2.5	MPI_Alltoall MPI_Alltoallv п. 5.4.3	Лекция 6

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

Разработка параллельных программ с использованием MPI на алгоритмическом языке Fortran

При разработке параллельных программ с использованием MPI на алгоритмическом языке Fortran существует не так много особенностей по сравнению с применением алгоритмического языка C:

все константы, переменные и функции объявляются в подключаемом файле mpif.h;подпрограммы библиотеки MPI являются процедурами и, тем самым, вызываются при помощи оператора вызова процедур CALL;коды завершения передаются через дополнительный параметр целого типа, располагаемый на последнем месте в списке параметров процедур (кроме MPI_Wtime и MPI_Wtick);все структуры (такие, например, как переменная status) являются массивами целого типа, размеры и номера ячеек которых описаны символическими константами (такими, как MPI_STATUS_SIZE для статуса операций);типы MPI_Comm и MPI_Datatype представлены целых типом INTEGER.

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

В качестве примера приведем варианты программы из п. 5.2.1.5 на алгоритмических языках Fortran 77 и Fortran 90.

Программа 5.3. Параллельная программа на языке Fortran 77

! Пример программы, использующей MPI на Fortran 77 program main include 'mpif.h' integer ProcNum, ProcRank, RecvRank, ierr integer i integer st(MPI_STATUS_SIZE) call MPI_INIT(ierr) call MPI_COMM_SIZE(MPI_COMM_WORLD, ProcNum, ierr) call MPI_COMM_RANK(MPI_COMM_WORLD, ProcRank, ierr)

if (ProcRank .gt. 0) goto 20 c Действия, выполняемые только процессом с рангом 0 print *, "Hello from process ", ProcRank do 10 i = 1, ProcNum - 1 call MPI_RECV(RecvRank, 1, MPI_INTEGER, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, st, ierr) print *, "Hello from process ", RecvRank 10 continue goto 30 c Сообщение, отправляемое всеми процессами, кроме процесса с рангом 0 20 call MPI_SEND(ProcRank, 1, MPI_INTEGER, 0, 0, MPI_COMM_WORLD, ierr) 30 call MPI_FINALIZE(ierr) stop end

Программа 5.4. Параллельная программа на языке Fortran 90

! Пример программы, использующей MPI на Fortran 90 program main use mpi

integer ProcNum, ProcRank, RecvRank, ierr integer status(MPI_STATUS_SIZE) integer i call MPI_INIT(ierr) call MPI_COMM_SIZE(MPI_COMM_WORLD, ProcNum, ierr) call MPI_COMM_RANK(MPI_COMM_WORLD, ProcRank, ierr) if (ProcRank .EQ. 0) then ! Действия, выполняемые только процессом с рангом 0 print *, "Hello from process ", ProcRank do i = 1, procnum - 1 call MPI_RECV(RecvRank, 1, MPI_INTEGER, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, ierr) print *, "Hello from process ", RecvRank enddo else c Сообщение, отправляемое всеми процессами, кроме процесса c с рангом 0 call MPI_SEND(ProcRank, 1, MPI_INTEGER, 0, 0, MPI_COMM_WORLD, ierr) endif call MPI_FINALIZE(ierr) stop end

Режимы передачи данных

Рассмотренная ранее функция MPI_Send обеспечивает так называемый стандартный (standard) режим отправки сообщений, при котором (см. также п. 5.2.1.3):

на время выполнения функции процесс – отправитель сообщения блокируется;после завершения функции буфер может быть использован повторно;состояние отправленного сообщения может быть различным – сообщение может располагаться на процессе-отправителе, может находиться в состоянии передачи, может храниться на процессе-получателе или же может быть принято процессом-получателем при помощи функции MPI_Recv.

Кроме стандартного режима в MPI предусматриваются следующие дополнительные режимы передачи сообщений:

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

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

MPI_Ssend – функция отправки сообщения в синхронном режиме;MPI_Bsend – функция отправки сообщения в буферизованном режиме;MPI_Rsend – функция отправки сообщения в режиме по готовности.

Список параметров всех перечисленных функций совпадает с составом параметров функции MPI_Send.

Для применения буферизованного режима передачи может быть создан и передан MPI буфер памяти, используемая для этого функция имеет вид:

int MPI_Buffer_attach(void *buf, int size),

где

buf — адрес буфера памяти;size — размер буфера.

После завершения работы с буфером он должен быть отключен от MPI при помощи функции:

int MPI_Buffer_detach(void *buf, int *size),

где

buf — адрес буфера памяти;size — возвращаемый размер буфера.

По практическому использованию режимов можно привести следующие рекомендации:

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

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

Синхронизация вычислений

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

Синхронизация процессов, т.е. одновременное достижение процессами тех или иных точек процесса вычислений, обеспечивается при помощи функции MPI:

int MPI_Barrier(MPI_Comm comm),

где

comm — коммуникатор, в рамках которого выполняется операция.

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

Способы конструирования производных типов данных

Для снижения сложности в MPI предусмотрено несколько различных способов конструирования производных типов:

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

Далее перечисленные способы конструирования производных типов данных будут рассмотрены более подробно.

Структурный способ конструирования

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

int MPI_Type_struct(int count, int blocklens[], MPI_Aint indices[], MPI_Data_type oldtypes[], MPI_Datatype *newtype),

где

count — количество блоков;blocklens — количество элементов в каждом блоке;indices — смещение каждого блока от начала типа (в байтах);oldtypes — исходные типы данных в каждом блоке в отдельности;newtype — новый определяемый тип данных.

Как следует из описания, структурный способ дополнительно к индексному методу позволяет указывать типы элементов для каждого блока в отдельности.

Сводный перечень коллективных операций данных

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

Типы данных

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

Подробное рассмотрение возможностей MPI для работы с производными типами данных будет выполнено в подразделе 5.5.

Топологии графа

Сведения по функциям MPI для работы с виртуальными топологиями типа граф будут рассмотрены более кратко – дополнительная информация может быть получена, например, в [[4], [40]

– [42], [57]].

Для создания коммуникатора с топологией типа граф в MPI предназначена функция:

int MPI_Graph_create(MPI_Comm oldcom, int nnodes, int *index, int *edges, int reorder, MPI_Comm *graphcom),

где

oldcom — исходный коммуникатор;nnodes — количество вершин графа;index — количество исходящих дуг для каждой вершины;edges — последовательный список дуг графа;reorder — параметр допустимости изменения нумерации процессов;graphcom – создаваемый коммуникатор с топологией типа граф.

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

Рис. 5.9.  Пример графа для топологии типа звезда

Для примера создадим топологию графа со структурой, представленной на рис. 5.9. В этом случае количество процессов равно 5, порядки вершин (количества исходящих дуг) принимают значения (4, 1, 1, 1, 1), а матрица инцидентности (номера вершин, для которых дуги являются входящими) имеет вид:

ПроцессыЛинии связи

0	1, 2, 3, 4
1	0
2	0
3	0
4	0

Для создания топологии с графом данного вида необходимо выполнить следующий программный код:

/* Создание топологии типа звезда */ int index[] = { 4,1,1,1,1 }; int edges[] = { 1,2,3,4,0,0,0,0 }; MPI_Comm StarComm; MPI_Graph_create(MPI_COMM_WORLD, 5, index, edges, 1, &StarComm);

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

int MPI_Graph_neighbors_count(MPI_Comm comm, int rank, int *nneighbors),

где

comm — коммуникатор с топологией типа граф;rank — ранг процесса в коммуникаторе;nneighbors — количество соседних процессов.

Получение рангов соседних вершин обеспечивается функцией:

int MPI_Graph_neighbors(MPI_Comm comm, int rank, int mneighbors, int *neighbors),

где

comm — коммуникатор с топологией типа граф;rank — ранг процесса в коммуникаторе;mneighbors — размер массива neighbors;neighbors — ранги соседних в графе процессов.

Управление группами

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

Для получения группы, связанной с существующим коммуникатором, применяется функция:

int MPI_Comm_group(MPI_Comm comm, MPI_Group *group),

где

comm — коммуникатор;group — группа, связанная с коммуникатором.

Далее, на основе существующих групп, могут быть созданы новые группы:

создание новой группы newgroup из существующей группы oldgroup, которая будет включать в себя n процессов — их ранги перечисляются в массиве ranks:

int MPI_Group_incl(MPI_Group oldgroup, int n, int *ranks, MPI_Group *newgroup),

где

oldgroup — существующая группа;n — число элементов в массиве ranks;ranks — массив рангов процессов, которые будут включены в новую группу;newgroup — созданная группа;создание новой группы newgroup из группы oldgroup, которая будет включать в себя n процессов, чьи ранги не совпадают с рангами, перечисленными в массиве ranks:

int MPI_Group_excl(MPI_Group oldgroup, int n, int *ranks, MPI_Group *newgroup),

где

oldgroup — существующая группа;n — число элементов в массиве ranks; ranks — массив рангов процессов, которые будут исключены из новой группы; newgroup — созданная группа.

Для получения новых групп над имеющимися группами процессов могут быть выполнены операции объединения, пересечения и разности:

создание новой группы newgroup как объединения групп group1 и group2:

int MPI_Group_union(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup),

где

group1 — первая группа;group2 — вторая группа;newgroup — объединение групп;создание новой группы newgroup как пересечения групп group1 и group2:

int MPI_Group_intersection(MPI_Group group1, MPI_Group group2, MPI_Group *newgroup),

где

group1 — первая группа;group2 — вторая группа;newgroup — пересечение групп;создание новой группы newgroup как разности групп group1 и group2:

int MPI_Group_difference( MPI_Group group1, MPI_Group group2, MPI_Group *newgroup),

где

group1 — первая группа;group2 — вторая группа;newgroup — разность групп;

При конструировании групп может оказаться полезной специальная пустая группа MPI_COMM_EMPTY.

Ряд функций MPI обеспечивает получение информации о группе процессов:

получение количества процессов в группе:

int MPI_Group_size(MPI_Group group, int *size),

где

group — группа;size — число процессов в группе;получение ранга текущего процесса в группе:

int MPI_Group_rank(MPI_Group group, int *rank),

где

group — группа;size — ранг процесса в группе.

После завершения использования группа должна быть удалена:

int MPI_Group_free(MPI_Group *group),

где

group — группа, подлежащая удалению

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

Управление группами процессов и коммуникаторами

Рассмотрим теперь возможности MPI по управлению группами процессов и коммуникаторами.

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

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

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

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

При необходимости передачи данных между процессами из разных групп необходимо создавать определенные в стандарте MPI-2 глобальные коммуникаторы (intercommunicator). Взаимодействие между процессами разных групп оказывается необходимым в достаточно редких ситуациях, в данном учебном материале не рассматривается и может служить темой для самостоятельного изучения – см., например, [[4], [40] – [42], [57]].

Управление коммуникаторами

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

Для создания новых коммуникаторов существуют два основных способа:

дублирование уже существующего коммуникатора:

int MPI_Comm_dup(MPI_Comm oldcom, MPI_comm *newcom),

где

oldcom — существующий коммуникатор, копия которого создается;newcom — новый коммуникатор;создание нового коммуникатора из подмножества процессов существующего коммуникатора:

int MPI_comm_create(MPI_Comm oldcom, MPI_Group group, MPI_Comm *newcom),

где

oldcom — существующий коммуникатор;group — подмножество процессов коммуникатора oldcom;newcom — новый коммуникатор.

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

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

Для пояснения рассмотренных функций можно привести пример создания коммуникатора, в котором содержатся все процессы, кроме процесса, имеющего ранг 0 в коммуникаторе MPI_COMM_WORLD (такой коммуникатор может быть полезен для поддержки схемы организации параллельных вычислений "менеджер – исполнители" – см. лекцию 4):

MPI_Group WorldGroup, WorkerGroup; MPI_Comm Workers; int ranks[1]; ranks[0] = 0; // Получение группы процессов в MPI_COMM_WORLD MPI_Comm_group(MPI_COMM_WORLD, &WorldGroup); // Создание группы без процесса с рангом 0 MPI_Group_excl(WorldGroup, 1, ranks, &WorkerGroup); // Создание коммуникатора по группе MPI_Comm_create(MPI_COMM_WORLD, WorkerGroup, &Workers); ... MPI_Group_free(&WorkerGroup); MPI_Comm_free(&Workers);

Быстрый и полезный способ одновременного создания нескольких коммуникаторов обеспечивает функция:

int MPI_Comm_split( MPI_Comm oldcomm, int split, int key, MPI_Comm *newcomm),

где

oldcomm — исходный коммуникатор;split — номер коммуникатора, которому должен принадлежать процесс;key — порядок ранга процесса в создаваемом коммуникаторе;newcomm — создаваемый коммуникатор.

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

В качестве примера можно рассмотреть задачу представления набора процессов в виде двумерной решетки. Пусть p=q*q есть общее количество процессов; следующий далее фрагмент программы обеспечивает получение коммуникаторов для каждой строки создаваемой топологии:

MPI_Comm comm; int rank, row; MPI_Comm_rank(MPI_COMM_WORLD, &rank); row = rank / q; MPI_Comm_split(MPI_COMM_WORLD, row, rank, &comm);

При выполнении данного примера, например, при p=9, процессы с рангами (0, 1, 2) образуют первый коммуникатор, процессы с рангами (3, 4, 5) – второй и т. д.

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

int MPI_Comm_free(MPI_Comm *comm),

где

comm — коммуникатор, подлежащий удалению.

Векторный способ конструирования

При векторном способе конструирования производного типа данных в MPI применяются функции

int MPI_Type_vector(int count, int blocklen, int stride, MPI_Data_type oldtype, MPI_Datatype *newtype) и int MPI_Type_hvector(int count, int blocklen, MPI_Aint stride, MPI_Data_type oldtype, MPI_Datatype *newtype),

где

count — количество блоков;blocklen — размер каждого блока;stride — количество элементов, расположенных между двумя соседними блоками;oldtype — исходный тип данных;newtype — новый определяемый тип данных.

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

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

конструирование типа для выделения половины (только четных или только нечетных) строк матрицы размером n?n:

MPI_Type_vector(n / 2, n, 2 * n, &StripRowType, &ElemType), конструирование типа для выделения столбца матрицы размером n?n:

MPI_Type_vector(n, 1, n, &ColumnType, &ElemType), конструирование типа для выделения главной диагонали матрицы размером n?n:

MPI_Type_vector(n, 1, n + 1, &DiagonalType, &ElemType).

С учетом характера приводимых примеров можно упомянуть имеющуюся в MPI возможность создания производных типов для описания подмассивов многомерных массивов при помощи функции (данная функция предусматривается стандартом MPI-2):

int MPI_Type_create_subarray(int ndims, int *sizes, int *subsizes, int *starts, int order, MPI_Data_type oldtype, MPI_Datatype *newtype),

где

ndims — размерность массива;sizes — количество элементов в каждой размерности исходного массива;subsizes — количество элементов в каждой размерности определяемого подмассива;starts — индексы начальных элементов в каждой размерности определяемого подмассива;order — параметр для указания необходимости переупорядочения;oldtype — тип данных элементов исходного массива;newtype — новый тип данных для описания подмассива.

Виртуальные топологии

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

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

В MPI имеется возможность представления множества процессов в виде решетки произвольной размерности (см. рис. 1.7). При этом граничные процессы решеток могут быть объявлены соседними, и, тем самым, на основе решеток могут быть определены структуры типа тор.

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

И, наконец, последний ряд замечаний перед началом рассмотрения MPI:

описание функций и все приводимые примеры программ будут представлены на алгоритмическом языке C; особенности использования MPI для алгоритмического языка Fortran будут даны в п. 5.8.1;краткая характеристика имеющихся реализаций библиотек MPI и общее описание среды выполнения MPI-программ будут рассмотрены в п. 5.8.2;основное изложение возможностей MPI будет ориентировано на стандарт версии 1.2 (так называемый MPI-1), нововведения стандарта версии 2.0 будут представлены в п. 5.8.3.

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

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

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

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

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

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

Разработайте программу для нахождения минимального

Подраздел 5.2.
1. Разработайте программу для нахождения минимального (максимального) значения среди элементов вектора.
2. Разработайте программу для вычисления скалярного произведения двух векторов.
3. Разработайте программу, в которой два процесса многократно обмениваются сообщениями длиной n байт. Выполните эксперименты и оцените зависимость времени выполнения операции передачи данных от длины сообщения. Сравните с теоретическими оценками, построенными по модели Хокни.
Подраздел 5.3.
4. Подготовьте варианты ранее разработанных программ с разными режимами выполнения операций передачи данных. Сравните время выполнения операций передачи данных при разных режимах работы.
5. Подготовьте варианты ранее разработанных программ с использованием неблокирующего способа выполнения операций передачи данных. Оцените количество вычислительных операций, необходимое для того, чтобы полностью совместить передачу данных и вычисления. Разработайте программу, в которой бы полностью отсутствовали задержки вычислений из-за ожидания передаваемых данных.
6. Выполните задание 3 с использованием операции одновременного выполнения передачи и приема данных. Сравните результаты вычислительных экспериментов.
Подраздел 5.4.
7. Разработайте программу-пример для каждой имеющейся в MPI коллективной операции.
8. Разработайте реализации коллективных операций при помощи парных обменов между процессами. Выполните вычислительные эксперименты и сравните время выполнения разработанных программ и функций MPI для коллективных операций.
9. Разработайте программу, выполните эксперименты и сравните результаты для разных алгоритмов реализации операции сбора, обработки и рассылки данных всех процессам (функция MPI_Allreduce).
Подраздел 5.5.
10. Разработайте программу-пример для каждого имеющегося в MPI способа конструирования производных типов данных.
11. Разработайте программу-пример с использованием функций упаковки и распаковки данных. Выполните эксперименты и сравните с результатами при использовании производных типов данных.
12. Разработайте производные типы данных для строк, столбцов, диагоналей матриц.
13. Разработайте программу-пример для каждой из рассмотренных функций для управления процессами и коммуникаторами.
14. Разработайте программу для представления множества процессов в виде прямоугольной решетки. Создайте коммуникаторы для каждой строки и столбца процессов. Выполните коллективную операцию для всех процессов и для одного из созданных коммуникаторов. Сравните время выполнения операции.
15. Изучите самостоятельно и разработайте программы-примеры для передачи данных между процессами разных коммуникаторов.
Подраздел 5.7.
16. Разработайте программу-пример для декартовой топологии.
17. Разработайте программу-пример для топологии графа.
18. Разработайте подпрограммы для создания некоторого набора дополнительных виртуальных топологий (звезда, дерево и др.).

---

---