Среда параллельного программирования MPI (Message Passing Interface) презентация

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

Работа с MPI
«одна программа – много процессов»
В рамках MPI для решения задачи разрабатывается одна программа, она запускается на выполнение одновременно на всех имеющихся процессорах
Такой способ организации параллельных вычислений обычно именуется как модель "одна программа - множество процессов" (single program multiple processes или SPMP)

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

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

Работа с MPI
MPI подключается как обычная библиотека. После установки и настройки реализации MPI в проект необходимо добавить ссылку на .obj или .lib файлы для линковщика и прописать путь к включаемым файлам реализации MPI (mpi.h).
Для Visual Studio это осуществляется в настройках проекта (вкладки компилятор C++ и компоновщик), следует найти и указать поставляемую версию библиотеки.
После создания С++ проекта в Visual Studio необходимо прописать путь для включаемых (include) файлов

путь для include файлов

прописать путь к .lib файлам

Добавить msmpi.lib к подключаемым библиотекам:

Запуск
Под параллельной программой в рамках MPI понимается множество одновременно выполняемых процессов: Процессы могут выполняться на разных процессорах; вместе с этим, на одном процессоре могут располагаться несколько процессов,
Каждый процесс параллельной программы порождается на основе копии одного и того же программного кода (модель SPMP).
Количество процессов и число используемых процессоров определяется в момент запуска параллельной программы средствами среды исполнения MPI программ. Все процессы программы последовательно перенумерованы. Номер процесса именуется рангом процесса.

Запуск
Вариант : mpiexec из
C:\Program Files\Microsoft HPC Pack 2008 SDK\Bin
Параметры
mpiexec –n <число процессов> <выполняемый файл программы>

Основные термины MPI
Коммуникатор – контекст взаимодействия процессов с помощью функций MPI.
За коммуникатором закрепляется некоторая группа процессов. Возможно определение виртуальных топологий для упрощения структуризации обменов в рамках коммуникатора.
Процессы в группе (и, как следствие, коммуникаторе) нумеруются от 0 до (<размер_группы> - 1)

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

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

Основные термины MPI
Все функции начинаются с префикса MPI_
int MPI_Init(int *argc, char **argv);
int MPI_Finalize(void);
int MPI_Initialized(int *flag);
Все функции имеют тип int и возвращают
либо значение MPI_SUCCESS (в случае нормального завершения),
либо код, соответствующий произошедшей ошибке.

Структура MPI-программы
Запуск (MPI_Init)
Инициализация среды выполнения MPI
Вычисления
Завершение среды выполнения MPI (MPI_Finalize(); )
Выгрузка

MPI-Init() - Инициализация среды выполнения MPI-программы
MPI_Init(argc, argv)
[INOUT] argc – количество параметров командной строки запуска программы
[INOUT] argv – параметры командной строки,
Функция MPI_Init создает группу процессов, в которой содержатся все процессы MPI-программы, и соответствующий этой группе коммуникатор MPI_COMM_WORLD.
Функция MPI_Init может быть вызвана только один раз, попытка повторной инициализации завершится ошибкой.

завершение среды выполнения
MPI-программы
MPI_Finalize()
Функция MPI_Finalize освобождает ресурсы, занятые средой выполнения MPI.

пример
#include
#include
// Подключаемый файл библиотеки MPI
int main(int argc, char* argv[]) {
int ierr;
ierr = MPI_Init(&argc, &argv);
// Инициализация среды MPI
if (ierr != MPI_SUCCESS)
return ierr;
printf("Hello world\n"); // Полезная работа
// разрешено использовать все MPI_* функции
MPI_Finalize(); // Завершение среды MPI
}

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

Общая организация MPI - Группы процессов
:MPI_COMM_WORLD - все процессы приложения
MPI_Comm_Split( … ) - разбить группу процессов на непересекающиеся подгруппы
MPI_Comm_Free(…) - уничтожить группу процессов
MPI_Group_size(MPI_Group group, int *size) - определить количество процессов в группе

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

Функции MPI
Возвращают :
MPI_SUCCESS - успешное завершение
Код ошибки
Типы:
Блокирующие (MPI_Send(…), MPI_Recv(…), MPI_WaitAll()… )
Неблокирующие (MPI_ISend(…), MPI_IRecv(…),… )

Способ выполнения функций MPI
Локальная функция - выполняется внутри вызывающего процесса. Ее завершение не требует коммуникаций.
Нелокальная функция - для ее завершения требуется выполнение MPI-процедуры другим процессом.
Глобальная функция - процедуру должны выполнять все процессы группы. Несоблюдение этого условия может приводить к зависанию задачи.

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

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

Оболочка сообщения
Оболочка сообщения содержит:
Ранг процесса-источника сообщения
Ранг процесса-получателя сообщения
Количество передаваемых в сообщении данных
Тег сообщения
Коммуникатор, в рамках которого происходит отправка

Соответствие между MPI-типами и типами языка C
Тип MPI Тип языка C++
MPI_CHAR signed char
MPI_SHORT signed short int
MPI_INT signed int
MPI_LONG signed long long int
MPI_UNSIGNED_CHAR unsigned char
MPI_UNSIGNED_SHORT unsigned short int
MPI_UNSIGNED unsigned int
MPI_UNSIGNED_LONG unsigned long long int
MPI_FLOAT float
MPI_DOUBLE double
MPI_LONG_DOUBLE long double
Структуры, вектора, массивы

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

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

Способы создания производных типов
Непрерывный способ конструирования (кол-во элементов одного типа)
MPI_Type_contiguous (2, oldtype, &newtype);
Векторный способ конструирования (кол-во блоков с промежутками)
MPI_Type_create_subarray (…);
Индексный способ конструирования (указывается смещение каждого блока)
MPI_Type_indexed (…);
Структурный способ конструирования (явное задание карты типа)
int MPI_Type_struct (…);

MPI производные типы данных: карта типа и сигнатура типа
Задание типа в MPI принято осуществлять при помощи карты типа (type map) в виде последовательности описаний входящих в тип значений, каждое отдельное значение описывается указанием типа и смещения адреса месторасположения от некоторого базового адреса:
TypeMap = {(<тип, смещение>), (< тип, смещение >), … , (< тип, смещение >)};
Часть карты типа с указанием только типов значений именуется в MPI сигнатурой типа:
TypeSignature = {<тип> , < тип>, … , < тип>};

Пример карты типа и сигнатуры типа
Функция
int MPI_Type_contiguous(int count,MPI_Data_type oldtype, MPI_Datatype *newtype);
Пусть исходный тип данных имеет карту типа
{ (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) }.

MPI производные типы данных:
структура
Структурный способ конструирования нового типа данных
Int MPI_Type_struct(count, blockLength, offset, oldTypes, newTypes);
count – количество блоков,
blockLength – количество элементов в каждом блоке,
offset – смещение каждого блока от начала типа,
oldTypes – старые типы данных элементов структуры,
newTypes – название нового типа данных;

MPI производные типы данных
перед использованием созданный тип должен быть объявлен
При завершении использования производный тип должен быть аннулирован при помощи функции MPI_Type_Free()

Базовые функции
Инициализация и завершение
int MPI_Init(int *argc, char ***argv)
процессу при инициализации передаются аргументы функции
main, полученные из командной строки
int MPI_Finalize(void)
закрывает все MPI-процессы и ликвидирует все области связи
#include “mpi.h”
in t main(int argc, char **argv) {
MPI_Init(&argc, &argv);
…
MPI_Finalize();
}

Функция определения числа процессов
int MPI_Comm_size(MPI_Comm comm, int *size);
IN comm - коммуникатор;
OUT size - число процессов в области связи коммуникатора comm, т.е. общее количество задач, работающих в области связи. Все задачи нумеруются уникальным номером от 0 до size-1.
int size;
MPI_Comm_size(MPI_COMM_WORLD, &size);

Функция определения номера процесса MPI_Comm_rank
int MPI_Comm_rank(MPI_Comm comm, int *rank)
Функция возвращает номер процесса, вызвавшего эту функцию. Номера процессов лежат в диапазоне 0..size-1 (значение size может быть определено с помощью предыдущей функции). Подпрограмма является локальной.
int runk, size;
in t main(int argc, char **argv) {
MPI_Init(&argc, &argv);
MPI_Comm_size(MPI_COMM_WORLD, &size);
MPI_Comm_rank(MPI_COMM_WORLD , &rank) ;
Printf(“%d \n”, rank);
MPI_Finalize();
}

Функции передачи сообщения с блокировкой
int MPI_Send(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm)
IN buf - адрес начала пересылаемых данных;
IN count - число пересылаемых элементов;
IN datatype - тип посылаемых элементов;
IN dest - номер процесса-получателя в группе, связанной с коммуникатором comm;
IN tag - идентификатор сообщения
IN comm - коммуникатор области связи.
Функция посылает count элементов типа datatype сообщения с идентификатором tag процессу dest в области связи коммуникатора comm. Переменная buf - массив или скалярная переменная (count = 1).

Функции приема сообщения с блокировкой
int MPI_Recv(void* buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Status * status)
IN buf - адрес начала пересылаемых данных;
IN count - число получаемых элементов (max емкость буфера);
IN datatype - тип посылаемых элементов;
IN dest - номер процесса-отправителя в группе, связанной с коммуникатором comm;
IN tag - идентификатор сообщения
IN comm - коммуникатор области связи.
OUT status – информация о принятом сообщении (структура : идентификатор сообщения, номер отправителя, фактическое кол-во данных, код завершения)

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

Пример (1) – вычисление числа π
#include "mpi.h"
#include
double f(double a) { // подынтегральная функция
return (4.0 / (1.0 + a*a));
}
int main(int argc, char *argv) {
int ProcRank, ProcNum, done = 0, n = 0, i;
double PI25DT = 3.141592653589793238462643;
double mypi, pi, h, sum, x, t1, t2;
MPI_Init(&argc,&argv);
MPI_Comm_size(MPI_COMM_WORLD,&ProcNum);
MPI_Comm_rank(MPI_COMM_WORLD,&ProcRank);

Пример (2) – вычисление числа π
# while (!done ) { // основной цикл вычислений
if ( ProcRank == 0) {
printf("Enter the number of intervals: ");
scanf("%d",&n);
t1 = MPI_Wtime();
}
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

Пример (3) – вычисление числа π
if (n > 0) { // вычисление локальных сумм
h = 1.0 / (double) n;
sum = 0.0;
for (i = ProcRank + 1; i <= n; i += ProcNum) {
x = h * ((double)i ­ 0.5);
sum += f(x);
}
mypi = h * sum;
// сложение локальных сумм (редукция)
MPI_Reduce(&mypi,&pi,1,MPI_DOUBLE,MPI_SUM,0,MPI_COMM_WORLD);

Пример (4) – вычисление числа π
if ( ProcRank == 0 ) { // вывод результатов
t2 = MPI_Wtime();
printf("pi is approximately %.16f, Error is
%.16f\n",pi, fabs(pi ­ PI25DT));
printf("wall clock time = %f\n",t2-t1);
}
} else done = 1;
}
MPI_Finalize();
}

Функции MPI - продолжение

Функция MPI_Probe(…)
MPI_Status status;
int dataSize;
// узнали статус сообщения:
MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COM_WORLD, & status) ;
// по статусу получим размер сообщения:
MPI_GetCount(&status, MPI_INT, &dataSize);
// теперь получим данные, которые гарантированно
// поместятся в буфер
int * buf = new int(dataSize);
MPI_Recv(buf, dataSize, MPI_INT, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COM_WORLD, & status) ;

Функция MPI_Probe(…) для получения данных разных типов
MPI_Status status;
int dataSize;
// узнали статус сообщения:
MPI_Probe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COM_WORLD, & status) ;
MPI_GetCount(&status, MPI_INT, &dataSize);
// по статусу получим тип данных в сообщении:
switch( status.MPI_TAG){
case tagIntData:
….. MPI_Recv(buf, dataSize, MPI_INT, …);
case tagFloatData:
…. MPI_Recv(buf, dataSize, MPI_FLOAT, …);
}

Джокеры
MPI_ANY_SOURCE – любой номер задачи
MPI_ANY_TAG -- любой идентификатор сообщения
MPI_COMM_WORLD -- любая область связи
MPI_DATATYPE_NULL - неопределенный тип данных
MPI_UNDEFINED - неопределенное значение

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

Объединенная конструкция приема-передачи - проблемы
Процесс 1: (БЛОКИРОВКА!!!)
Recv( …2 …); Send(…2…);
Процесс 2:
Recv( …1 …); Send(…1…);
Процесс 1: (НЕТ БЛОКИРОВКИ НА ЛЮБОЙ ПЛАТФОРМЕ)
Send(…2…); Recv( …2 …);
Процесс 2:
Recv( …1 …); Send(…1…);
Процесс 1: (MPI не блокирует, т.к. использует временный буфер)
Send(…2…); Recv( …2 …);
Процесс 2:
Send(…1…); Recv( …1 …);

Объединенная конструкция приема-передачи MPI_Sendrecv()
MPI_Sendrecv( … );
12 параметров = 5 (send) + 7 (recv)
Свойства:
Порядок приема-передачи выбирается автоматически.
Функция совместима с раздельными send и recv
Прием и передача использует один и тот же коммуникатор

Объединенная конструкция приема-передачи MPI_Sendrecv_replace()
MPI_Sendrecv_replace( … );
12 параметров = 5 (send) + 7 (recv) -1 (буфер)
Свойства:
Порядок приема-передачи выбирается автоматически.
Отправляемые данные затираются принимаемыми
Прием и передача использует один и тот же коммуникатор
Принимаемые и отправляемые данные имеют один и тот же тип
Принимаемые данные должны быть не длиннее отправляемых

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

Функция отсчета времени
double MPI_Wtime(void)
Функция возвращает астрономическое время в секундах, прошедшее с некоторого момента в прошлом (точки отсчета). Гарантируется, что эта точка отсчета не будет изменена в течение жизни процесса. Для хронометража участка программы вызов функции делается в начале и конце участка и определяется разница между показаниями таймера.
{
double starttime, endtime;
starttime = MPI_Wtime();
... хронометрируемый участок ...
endtime = MPI_Wtime();
printf("Выполнение заняло %f секунд\n", endtime-starttime);
}

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

Схема простейшего алгоритма

Пример шаблона кода
int res = MPI_Init(int *argc, char ***argv) ;
MPI_Comm_rank( …&myNum…. ); MPI_Comm_size( … &size…);
//Информацию получает 0-й процессор :
if (myNum == 0 ) {
<генерация дaнных для обработки >
// Рассылка информации всем процессорам:
for (int i=1; i
for (int i=1; i
}
else{MPI_Recv( …. );
< ВЫЧИСЛЕНИЯ на одном процессоре для своих данных>
MPI_Send( …. );
} MPI_Finalize();

Коллективные функции - рассылка
Функция MPI_Scatter разбивает сообщение из буфера посылки процесса root на равные части размером sendcount и посылает i-ю часть в буфер приема процесса с номером i. Процесс root использует оба буфера (посылки и приема), поэтому в вызываемой им подпрограмме все параметры являются существенными. Остальные процессы группы с коммуникатором comm являются только получателями, поэтому для них параметры, специфицирующие буфер посылки, не существенны.
int MPI_Scatter(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype,
int root, MPI_Comm comm)

Коллективные функции - рассылка
Пример использования функции MPI_Scatter
MPI_Comm comm;
int rbuf[100], gsize;
int root, *array;
. . . . . .
MPI_Comm_size(comm, &gsize);
array = (int *) malloc(gsize * 100 * sizeof(int));
. . . . . .
MPI_Scatter(array, 100, MPI_INT, rbuf, 100, MPI_INT, root, comm);

Коллективные функции - прием
Функция MPI_Gather производит сборку блоков данных, посылаемых всеми процессами группы, в один массив процесса с номером root. Длина блоков предполагается одинаковой.
Объединение происходит в порядке увеличения номеров процессов-отправителей. То есть данные, посланные процессом i из своего буфера sendbuf, помещаются в i-ю порцию буфера recvbuf процесса root. Длина массива, в который собираются данные, должна быть достаточной для их размещения.
int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype,
int root, MPI_Comm comm);

Коллективные функции - прием
Пример программы с использованием функции MPI_Gather:
MPI_Comm comm;
int array[100];
int root, *rbuf;
. . .
MPI_Comm_size(comm, &gsize);
rbuf = (int *) malloc( gsize * 100 * sizeof(int));
MPI_Gather(array, 100, MPI_INT, rbuf, 100, MPI_INT, root, comm);

Коллективные функции - векторный вариант
int MPI_Scatterv(void* sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void* recvbuf, int recvcount,
MPI_Datatype recvtype, int root, MPI_Comm comm) ;
Начало расположения элементов блока, посылаемого i-му процессу, задается в массиве смещений displs, а число посылаемых элементов - в массиве sendcounts.
int MPI_Gatherv(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* rbuf, int *recvcounts, int *displs, MPI_Datatype recvtype,
int root, MPI_Comm comm)

Пример шаблона кода с коллективными функциями
int res = MPI_Init(int *argc, char ***argv) ;
int myNum = MPI_Comm_rank( …. );
//Информацию получает 0-й процессор :
if (myNum == 0 ) {
< ввод дaнных>
// Рассылка информации всем процессорам:
MPI_Scatter( …. );
< ВЫЧИСЛЕНИЯ на одном процессоре для своих данных>
MPI_Gather( . .. );
}
else{
< ВЫЧИСЛЕНИЯ на одном процессоре для своих данных>
} MPI_Finalize();

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