Введение в использование MPI
Введение в технологии параллельного программирования (MPI)
Цель лекции: Лекция направлена на изучение общей методики разработки параллельных алгоритмов.
Видеозапись лекции — (объем — 134 МБ).
5.1. MPI: основные понятия и определения
Рассмотрим ряд понятий и определений, являющихся основополагающими для стандарта MPI .
5.1.1. Понятие параллельной программы
Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов. Процессы могут выполняться на разных процессорах, но на одном процессоре могут располагаться и несколько процессов (в этом случае их исполнение осуществляется в режиме разделения времени). В предельном случае для выполнения параллельной программы может использоваться один процессор – как правило, такой способ применяется для начальной проверки правильности параллельной программы.
Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP). Данный программный код, представленный в виде исполняемой программы, должен быть доступен в момент запуска параллельной программы на всех используемых процессорах. Исходный программный код для исполняемой программы разрабатывается на алгоритмических языках C или Fortran с использованием той или иной реализации библиотеки MPI.
Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI-программ и в ходе вычислений меняться не может (в стандарте MPI-2 предусматривается возможность динамического изменения количества процессов). Все процессы программы последовательно перенумерованы от 0 до p-1, где p есть общее количество процессов. Номер процесса именуется рангом процесса.
5.1.2. Операции передачи данных
Основу MPI составляют операции передачи сообщений. Среди предусмотренных в составе MPI функций различаются парные (point-to-point) операции между двумя процессами и коллективные (collective) коммуникационные действия для одновременного взаимодействия нескольких процессов.
Для выполнения парных операций могут использоваться разные режимы передачи, среди которых синхронный, блокирующий и др. – полное рассмотрение возможных режимов передачи будет выполнено в подразделе 5.3.
Как уже отмечалось ранее, стандарт MPI предусматривает необходимость реализации большинства основных коллективных операций передачи данных – см. подразделы 5.2 и 5.4.
5.1.3. Понятие коммуникаторов
Процессы параллельной программы объединяются в группы. Под коммуникатором в MPI понимается специально создаваемый служебный объект, объединяющий в своем составе группу процессов и ряд дополнительных параметров (контекст), используемых при выполнении операций передачи данных.
Как правило, парные операции передачи данных выполняются для процессов, принадлежащих одному и тому же коммуникатору. Коллективные операции применяются одновременно для всех процессов коммуникатора. Как результат, указание используемого коммуникатора является обязательным для операций передачи данных в MPI.
В ходе вычислений могут создаваться новые и удаляться существующие группы процессов и коммуникаторы. Один и тот же процесс может принадлежать разным группам и коммуникаторам. Все имеющиеся в параллельной программе процессы входят в состав создаваемого по умолчанию коммуникатора с идентификатором MPI_COMM_WORLD.
При необходимости передачи данных между процессами из разных групп необходимо создавать глобальный коммуникатор (intercommunicator).
Подробное рассмотрение возможностей MPI для работы с группами и коммуникаторами будет выполнено в подразделе 5.6.
5.1.4. Типы данных
При выполнении операций передачи сообщений для указания передаваемых или получаемых данных в функциях MPI необходимо указывать тип пересылаемых данных. MPI содержит большой набор базовых типов данных, во многом совпадающих с типами данных в алгоритмических языках C и Fortran. Кроме того, в MPI имеются возможности для создания новых производных типов данных для более точного и краткого описания содержимого пересылаемых сообщений.
Подробное рассмотрение возможностей MPI для работы с производными типами данных будет выполнено в подразделе 5.5.
5.1.5. Виртуальные топологии
Как уже отмечалось ранее, парные операции передачи данных могут быть выполнены между любыми процессами одного и того же коммуникатора, а в коллективной операции принимают участие все процессы коммуникатора. В этом плане, логическая топология линий связи между процессами имеет структуру полного графа (независимо от наличия реальных физических каналов связи между процессорами).
Вместе с этим (и это уже отмечалось в разделе 3), для изложения и последующего анализа ряда параллельных алгоритмов целесообразно логическое представление имеющейся коммуникационной сети в виде тех или иных топологий.
В MPI имеется возможность представления множества процессов в виде решетки произвольной размерности (см. подраздел 5.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 предусматривается наличие более 125 функций. С другой стороны, структура MPI является тщательно продуманной – разработка параллельных программ может быть начата уже после рассмотрения всего лишь 6 функций MPI. Все дополнительные возможности MPI могут осваиваться по мере роста сложности разрабатываемых алгоритмов и программ. Именное в таком стиле – от простого к сложному – и будет далее представлен весь учебный материал по MPI.
5.2. Введение в разработку параллельных программ с использованием MPI
5.2.1. Основы MPI
Приведем минимально-необходимый набор функций MPI, достаточный для разработки достаточно простых параллельных программ.
5.2.1.1 Инициализация и завершение MPI программ
Первой вызываемой функцией MPI должна быть функция:
для инициализации среды выполнения MPI-программы. Параметрами функции являются количество аргументов в командной строке и текст самой командной строки.
Последней вызываемой функцией MPI обязательно должна являться функция:
Как результат, можно отметить, что структура параллельной программы, разработанная с использованием MPI, должна иметь следующий вид:
- Файл mpi.h содержит определения именованных констант, прототипов функций и типов данных библиотеки MPI,
- Функции MPI_Init и MPI_Finalize являются обязательными и должны быть выполнены (и только один раз) каждым процессом параллельной программы,
- Перед вызовом MPI_Init может быть использована функция MPI_Initialized для определения того, был ли ранее выполнен вызов MPI_Init.
Рассмотренные примеры функций дают представление синтаксиса именования функций в MPI. Имени функции предшествует префикс MPI, далее следует одно или несколько слов названия, первое слово в имени функции начинается с заглавного символа, слова разделяются знаком подчеркивания. Названия функций MPI, как правило, поясняют назначение выполняемых функцией действий.
5.2.1.2 Определение количества и ранга процессов
Определение количества процессов в выполняемой параллельной программе осуществляется при помощи функции:
Для определения ранга процесса используется функция:
Как правило, вызов функций MPI_Comm_size и MPI_Comm_rank выполняется сразу после MPI_Init:
Основы MPI для «чайников»
Так вышло, что мне пришлось тесно столкнуться с изучением параллельных вычислений и в частности MPI. Пожалуй, направление это на сегодняшний день является весьма перспективным, так что хотелось бы показать хабраюзерам основы этого процесса.
Основные принципы и пример
В качестве примера будет использоваться расчет экспоненты (e). Один из вариантов ее нахождения — ряд Тейлора:
e^x=∑((x^n)/n!), где суммирование происходит от n=0 до бесконечности.
Данная формула легко поддается распараллеливанию, так как искомое число является суммой отдельных слагаемых и благодаря этому каждый отдельный процессор может заняться вычислением отдельных слагаемых.
Количество слагаемых, которое будет рассчитываться в каждом отдельно взятом процессоре, зависит как и от длины интервала n, так и от имеющегося количества процессоров k, которые смогут участвовать в процессе вычисления. Так, например, если длина интервала n=4, а в вычислениях участвуют пять процессоров (k=5), то с первого по четвертый процессоры получат по одному слагаемому, а пятый будет не задействован. В случае же если n=10, а k=5, каждому процессору достанется по два слагаемых для вычисления.
Изначально, первый процессор с помощью функции широковещательной рассылки MPI_Bcast отправляет остальным значение заданной пользователями переменной n. В общем случае функция MPI_Bcast имеет следующий формат:
int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm), где buffer – это адрес буфера с элементом, сount – количество элементов, datatype – соответствующий тип данных в MPI, root – ранг главного процессора, который занимается пересылкой, а comm- имя коммуникатора.
В моем случае в роли главного процессора, как уже говорилось, будет выступать первый процессор с рангом 0.
После того число n будет успешно отправлено, каждый процессор займется вычислением своих слагаемых. Для этого в каждом шаге цикла к числу i, которое изначально равно рангу процессора, будет прибавляться число, равное количеству процессоров участвующих в вычислениях. Если число в ходе следующих действий число i превысит заданное пользователем число n, выполнение цикла для данного процессора остановится.
В ходе выполнения цикла слагаемые будут прибавляться в отдельную переменную и, после его завершения, полученная сумма отправится в главный процессор. Для этого будет использоваться функция операции приведения MPI_Reduce. В общем виде она выглядит следующим образом:
int MPI_Reduce(void *buf, void *result, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm)
Она объединяет элементы входного буфера каждого процесса в группе, используя операцию op, и возвращает объединенное значение в выходной буфер процесса с номером root. Результатом такой операции будет единственное значение, благодаря чему функция приведения и получила свое название.
После выполнения программы на всех процессорах, первый процессор получит общую сумму слагаемых, которая и будет являться нужным нам значение экспоненты.
Следует заметить, что и в параллельном и последовательном методах вычисления экспоненты, для нахождения факториала используется рекурсивная функция. В ходе принятия решения по способу распараллеливания выполняемой задачи, я рассматривал вариант нахождения факториала также на разных процессорах, но в итоге такой вариант был принят мной нерациональным.
Первостепенной задачей все же является нахождение значения экспоненты и если процессоры начнут вычислять каждый факториал каждого слагаемого раздельным образом, это может привести к прямо обратно эффекту, а именно значительной потери в производительности и скорости вычисления.
Объясняется это тем, что в данном случае начнется весьма большая нагрузка на коммуникационную среду, которая и без того зачастую является слабым звеном в системах параллельных вычислений. Если же вычисление факториала будет происходить на каждом процессоре частным образом, нагрузка на линии коммуникаций будет минимальна. Данный случай можно назвать хорошим примером того, что и задача распараллеливания тоже должна порой иметь свои границы.
Алгоритм выполнения кода
1. Из визуальной оболочки в программу передается значение числа n, которое затем с помощью функции широковещательной рассылки отправляется по всем процессорам.
2. При инициализации первого главного процессора, запускается таймер.
3. Каждый процессор выполняет цикл, где значением приращения является количество процессоров в системе. В каждой итерации цикла вычисляется слагаемое и сумма таких слагаемых сохраняется в переменную drobSum.
4. После завершения цикла каждый процессор суммирует свое значение drobSum к переменной Result, используя для этого функцию приведения MPI_Reduce.
5. После завершения расчетов на всех процессорах, первый главный процессор останавливает таймер и отправляет в поток вывода получившееся значение переменной Result.
6. В поток вывода отправляется также и отмеренное нашим таймером значение времени в милисекундах.
Листинг кода
#include «mpi.h»
#include
#include
using namespace std;
double Fact( int n)
<
if (n==0)
return 1;
else
return n*Fact(n-1);
>
int main( int argc, char *argv[])
<
SetConsoleOutputCP(1251);
int n;
int myid;
int numprocs;
int i;
int rc;
long double drob,drobSum=0,Result, sum;
double startwtime = 0.0;
double endwtime;
if (rc= MPI_Init(&argc, &argv))
<
cout «Ошибка запуска, выполнение остановлено » if (my > <
for (i = my > <
drob = 1/Fact(i);
drobSum += drob;
>
MPI_Reduce(&drobSum, &Result, 1, MPI_LONG_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
cout.precision(20);
if (my > <
cout return 0;
>
* This source code was highlighted with Source Code Highlighter .
Вывод
Таким образом мы получили простенькую программу для подсчета экспоненты с использованием сразу нескольких процессоров. Наверное, узким местом является хранением самого результата, потому что с увеличением количества разрядов вмещать значение с использованием стандартных типов банально не выйдет и это место требует проработки. Пожалуй, достаточно рациональным решением является запись результата в файл, хотя, в виду чисто учебной функции этого примера, особо на этом внимание можно не акцентировать.