Технология программирования MPI Антонов Александр Сергеевич, к.ф.-м.н., с.н.с. лаборатории Параллельных информационных технологий НИВЦ МГУ

Координаты для связи: Тел: (495) Web:

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

Параллелизм: Крупноблочное распараллеливание: if (MyProc = 0) then C операции, выполняемые 0-им процессором endif... if (MyProc = K) then C операции, выполняемые K-им процессором endif

Параллелизм: Наибольший ресурс параллелизма в программах сосредоточен в циклах! Распределение итераций циклов: do i = 1, N if (i ~ MyProc) then C операции i-й итерации для C для выполнения процессором MyProc endif enddo

Параллелизм: Примеры способов распределения итераций циклов: Блочное распределение – по N/P итераций. Блочно-циклическое распределение – размер блока меньше, распределение продолжается циклически. Циклическое распределение – циклически по одной итерации.

Параллелизм: Рассмотрим простейший цикл: do i = 1, N a(i) = a(i) + b(i) enddo

Параллелизм: Блочное распределение: C размер блока итераций k = (N-1)/P + 1 C начало блока итераций C процессора MyProc ibeg = MyProc * k + 1 C конец блока итераций C процесса MyProc iend = (MyProc + 1) * k

Параллелизм: C если не досталось итераций if (ibeg.gt. N) then iend = ibeg – 1 else C если досталось меньше итераций if (iend.gt. N) iend = N endif do i = ibeg, iend a(i) = a(i) + b(i) enddo

Параллелизм: Циклическое распределение: do i = MyProc+1, N, P a(i) = a(i) + b(i) enddo

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

MPI MPI - Message Passing Interface, интерфейс передачи сообщений. Стандарт MPI 1.1. Более 120 функций. SPMD-модель параллельного программирования.

MPI Префикс MPI_. #include ( mpif.h для языка Фортран) Процессы, посылка сообщений. Сообщение – массив однотипных данных, расположенных в последовательных ячейках памяти. Группа – упорядоченное множество процессов.

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

MPI Каждый процесс может одновременно входить в разные коммуникаторы. Два основных атрибута процесса: коммуникатор (группа) и номер процесса в коммуникаторе (группе). Если группа содержит n процессов, то номер любого процесса в данной группе лежит в пределах от 0 до n – 1.

MPI Сообщение набор данных некоторого типа. Атрибуты сообщения: номер процесса- отправителя, номер процесса-получателя, идентификатор сообщения и др. Идентификатор сообщения - целое неотрицательное число в диапазоне от 0 до Для работы с атрибутами сообщений введена структура MPI_Status.

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

MPI int MPI_Init(int *argc, char ***argv) Инициализация параллельной части программы. Все другие функции MPI могут быть вызваны только после вызова MPI_Init. Инициализация параллельной части для каждого приложения должна выполняться только один раз.

MPI int MPI_Finalize(void) Завершение параллельной части приложения. Все последующие обращения к любим MPI-функциям, в том числе к MPI_Init, запрещены. К моменту вызова MPI_Finalize каждим процессом программы все действия, требующие его участия в обмене сообщениями, должны быть завершены.

MPI Общая схема MPI-программы: #include main(int argc, char **argv) { … MPI_Init(&argc, &argv); … MPI_Finalize(); … }

MPI int MPI_Initialized(int *flag) В аргументе flag возвращает 1, если вызвана из параллельной части приложения, и 0 в противном случае. Единственная MPI-функция, которую можно вызвать до вызова MPI_Init.

MPI MPI_Comm_size(MPI_Comm comm, int *size) В аргументе size возвращает число параллельных процессов в коммуникаторе comm.

MPI MPI_Comm_rank(MPI_Comm comm, int *rank) В аргументе rank возвращает номер процесса в коммуникаторе comm в диапазоне от 0 до size-1.

MPI Общая схема распараллеливания: if (rank == 0) {/* операции, выполняемые 0-им процессом */} if (rank == K) {/* операции, выполняемые K-им процессом */} for (i = 0; i < N; i++) { if (i ~ rank) { /* операции i-й итерации для выполнения процессом rank */ }

MPI double MPI_Wtime(void) Функция возвращает для каждого вызвавшего процесса астрономическое время в секундах (вещественное число), прошедшее с некоторого момента в прошлом. Момент времени, используемый в качестве точки отсчета, не будет изменен за время существования процесса.

MPI double MPI_Wtick(void) Функция возвращает разрешение таймера в секундах.

MPI MPI_Get_processor_name(char *name, int *len) Функция возвращает в строке name имя узла, на котором запущен вызвавший процесс. В переменной len возвращается количество символов в имени, не превышающее константы MPI_MAX_PROCESSOR_NAME.

MPI #include main(int argc, char **argv) { int rank, size; … MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &rank); MPI_Comm_size(MPI_COMM_WORLD, &size); printf("Process %d of %d \n", rank, size); … MPI_Finalize(); }

MPI int MPI_Send(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm) Блокирующая посылка массива buf с идентификатором msgtag, состоящего из count элементов типа datatype, процессу с номером dest в коммуникаторе comm.

MPI Типы данных: MPI_INT – int MPI_SHORT – short MPI_LONG - long MPI_FLOAT – float MPI_DOUBLE – double MPI_CHAR – char MPI_BYTE – 8 бит MPI_PACKED – тип для упакованных данных. Все типы данных перечислены в файле mpi.h.

MPI Модификации функции MPI_Send : MPI_Bsend передача сообщения с буферизацией. MPI_Ssend передача сообщения с синхронизацией. MPI_Rsend передача сообщения по готовности.

MPI int MPI_Buffer_attach(void* buf, int size) Назначение массива buf размера size для использования при посылке сообщений с буферизацией. В каждом процессе может быть только один такой буфер.

MPI int MPI_Buffer_detach(buf, size) Освобождение массива buf для других целей. Процесс блокируется до того момента, когда все сообщения уйдут из данного буфера.

MPI int MPI_Recv(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Status status) Блокирующий прием сообщения длины не более count от процесса с номером source с заполнением массива status.

MPI Вместо аргументов source и msgtag можно использовать константы: MPI_ANY_SOURCE признак того, что подходит сообщение от любого процесса MPI_ANY_TAG признак того, что подходит сообщение с любим идентификатором.

MPI Параметры принятого сообщения всегда можно определить по соответствующим элементам структуры status : status.MPI_SOURCE номер процесса-отправителя. status.MPI_TAG идентификатор сообщения. status.MPI_ERROR код ошибки.

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

MPI int MPI_Get_count(MPI_Status *status, MPI_Datatype datatype, int *count) По значению параметра status функция определяет число count уже принятых (после обращения к MPI_Recv) или принимаемых (после обращения к MPI_Probe или MPI_Iprobe ) элементов сообщения типа datatype.

MPI int MPI_Probe(int source, int msgtag, MPI_Comm comm, MPI_Status *status) Получение в параметре status информации о структуре ожидаемого сообщения с блокировкой. Возврата не произойдет, пока сообщение с подходящим идентификатором и номером процесса-отправителя не будет доступно для получения.

MPI Тупиковые ситуации (deadlock): процесс 0: Recv(1) Send(1) процесс 1: Recv(0) Send(0) процесс 0: Send(1) Recv(1) процесс 1: Send(0) Recv(0)

MPI Разрешение тупиковых ситуаций: 1. процесс 0: Send(1) Recv(1) процесс 1: Recv(0) Send(0) 2. Использование неблокирующих операций 3. Использование функции MPI_Sendrecv

MPI MPI_Comm_rank (MPI_COMM_WORLD, &me); MPI_Comm_size (MPI_COMM_WORLD, &size); if ((me % 2) == 0) { if ((me+1) < size) /* посылают все процессы, кроме последнего */ MPI_Send (…, me+1, SOME_TAG, MPI_COMM_WORLD); } else MPI_Recv (…, me-1, SOME_TAG, MPI_COMM_WORLD, &status);

MPI int MPI_Isend(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request) Неблокирующая посылка сообщения. Возврат из функции происходит сразу после инициализации передачи. Переменная request идентифицирует пересылку.

MPI Модификации функции MPI_Isend : MPI_Ibsend передача сообщения с буферизацией. MPI_Issend передача сообщения с синхронизацией. MPI_Irsend передача сообщения по готовности.

MPI int MPI_Irecv(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request) Неблокирующий прием сообщения. Возврат из функции происходит сразу после инициализации передачи. Переменная request идентифицирует пересылку.

MPI Сообщение, отправленное любой из функций MPI_Send, MPI_Isend и любой из трех их модификаций, может быть принято любой из процедур MPI_Recv и MPI_Irecv. До завершения неблокирующей операции не следует записывать в используемый массив данных!

MPI int MPI_Iprobe(int source, int msgtag, MPI_Comm comm, int *flag, MPI_Status *status) Получение информации о структуре ожидаемого сообщения без блокировки. В аргументе flag возвращается значение 1, если сообщение с подходящими атрибутами уже может быть принято.

MPI int MPI_Wait(MPI_Request *request, MPI_Status *status) Ожидание завершения асинхронной операции, ассоциированной с идентификатором request. Для неблокирующего приема определяется параметр status. request устанавливается в значение MPI_REQUEST_NULL.

MPI int MPI_Waitall(int count, MPI_Request *requests, MPI_Status *statuses) Ожидание завершения count асинхронных операций, ассоциированных с идентификаторами requests. Для неблокирующих приемов определяются параметры в массиве statuses.

MPI prev = rank – 1; next = rank + 1; if (rank == 0) prev = numtasks – 1; if (rank == (numtasks – 1)) next = 0; MPI_Irecv(&buf[0], 1, MPI_INT, prev, tag1, MPI_COMM_WORLD, &reqs[0]); MPI_Irecv(&buf[1], 1, MPI_INT, next, tag2, MPI_COMM_WORLD, &reqs[1]);

MPI MPI_Isend(&rank, 1, MPI_INT, prev, tag2, MPI_COMM_WORLD, &reqs[2]); MPI_Isend(&rank, 1, MPI_INT, next, tag1, MPI_COMM_WORLD, &reqs[3]); MPI_Waitall(4, reqs, stats);

MPI int MPI_Waitany(int count, MPI_Request *requests, int *index, MPI_Status *status) Ожидание завершения одной из count асинхронных операций, ассоциированных с идентификаторами requests. Для неблокирующего приема определяется параметр status.

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

MPI int MPI_Waitsome(int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses) Ожидание завершения хотя бы одной из incount асинхронных операций, ассоциированных с идентификаторами requests.

MPI Параметр outcount содержит число завершенных операций, а первые outcount элементов массива indexes содержат номера элементов массива requests с их идентификаторами. Первые outcount элементов массива statuses содержат параметры завершенных операций (для неблокирующих приемов).

MPI int MPI_Test(MPI_Request *request, int *flag, MPI_Status *status) Проверка завершенности асинхронной операции, ассоциированной с идентификатором request. В параметре flag возвращается значение 1, если операция завершена.

MPI int MPI_Testall(int count, MPI_Request *requests, int *flag, MPI_Status *statuses) Проверка завершенности count асинхронных операций, ассоциированных с идентификаторами requests.

MPI int MPI_Testany(int count, MPI_Request *requests, int *index, int *flag, MPI_Status *status) В параметре flag возвращается значение 1, если хотя бы одна из операций асинхронного обмена завершена.

MPI int MPI_Testsome(int incount, MPI_Request *requests, int *outcount, int *indexes, MPI_Status *statuses) Аналог MPI_Waitsome, но возврат происходит немедленно. Если ни одна из операций не завершилась, то значение outcount будет равно нулю.

MPI int MPI_Send_init(void *buf, int count, MPI_Datatype datatype, int dest, int msgtag, MPI_Comm comm, MPI_Request *request) Формирование отложенного запроса на посылку сообщения. Сама операция пересылки не начинается!

MPI Модификации функции MPI_Send_init : MPI_Bsend_init формирование запроса на передачу сообщения с буферизацией. MPI_Ssend_init формирование запроса на передачу сообщения с синхронизацией. MPI_Rsend_init формирование запроса на передачу сообщения по готовности.

MPI int MPI_Recv_init(void *buf, int count, MPI_Datatype datatype, int source, int msgtag, MPI_Comm comm, MPI_Request *request) Формирование отложенного запроса на приём сообщения. Сама операция приема не начинается!

MPI int MPI_Start(MPI_Request *request) Инициализация отложенного запроса на выполнение операции обмена, соответствующей значению параметра request. Операция запускается как неблокирующая.

MPI int MPI_Startall(int count, MPI_Request *requests) Инициализация count отложенных запросов на выполнение операций обмена, соответствующих значениям первых count элементов массива requests. Операции запускаются как неблокирующие.

MPI Сообщение, отправленное при помощи отложенного запроса, может быть принято любой из процедур MPI_Recv и MPI_Irecv, и наоборот. По завершении отложенного запроса значение параметра request (requests) сохраняется и может использоваться в дальнейшем!

MPI int MPI_Request_free(MPI_Request *request) Удаляет структуры данных, связанные с параметром request. request устанавливается в значение MPI_REQUEST_NULL. Если операция, связанная с этим запросом, уже выполняется, то она завершится.

MPI prev = rank – 1; next = rank + 1; if (rank == 0) prev = numtasks – 1; if (rank == (numtasks – 1)) next = 0; MPI_Recv_init(&rbuf[0], 1, MPI_FLOAT, prev, tag1, MPI_COMM_WORLD, &reqs[0]); MPI_Recv_init(&rbuf[1], 1, MPI_FLOAT, next, tag2, MPI_COMM_WORLD, &reqs[1]); MPI_Send_init(&sbuf[0], 1, MPI_FLOAT, prev, tag2, MPI_COMM_WORLD, &reqs[2]); MPI_Send_init(&sbuf[1], 1, MPI_FLOAT, next, tag1, MPI_COMM_WORLD, &reqs[3]);

MPI for(…){ sbuf[0]=…; sbuf[1]=…; MPI_Startall(4, reqs);... MPI_Waitall(4, reqs, stats);... } MPI_Request_free(&reqs[0]); MPI_Request_free(&reqs[1]); MPI_Request_free(&reqs[2]); MPI_Request_free(&reqs[3]);

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)

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

MPI int MPI_Sendrecv_replace(void *buf, int count, MPI_Datatype datatype, int dest, int stag, int source, int rtag, MPI_comm comm, MPI_Status *status) Совмещенные прием и передача сообщений с блокировкой через общий буфер buf.

MPI prev = rank – 1; next = rank + 1; if (rank == 0) prev = numtasks – 1; if (rank == (numtasks – 1)) next = 0; MPI_Sendrecv(&sbuf[0], 1, MPI_FLOAT, prev, tag2, &rbuf[0], 1, MPI_FLOAT, next, tag2, MPI_COMM_WORLD, &status1); MPI_Sendrecv(&sbuf[1], 1, MPI_FLOAT, next, tag1, &rbuf[1], 1, MPI_FLOAT, prev, tag1, MPI_COMM_WORLD, &status2);

MPI Специальное значение MPI_PROC_NULL для несуществующего процесса. Операции с таким процессом завершаются немедленно с кодом завершения MPI_SUCCESS. next = rank + 1; if(rank == (numtasks - 1)) next=MPI_PROC_NULL; MPI_Send (&buf, 1, MPI_FLOAT, next, tag, MPI_COMM_WORLD);

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