Основы параллельного программирования с использованием MPI Лекция 5 Немнюгин Сергей Андреевич Санкт-Петербургский государственный университет физический факультет кафедра вычислительной физики

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

План лекции 2008 Особенности коллективных обменов. Широковещательная рассылка. Операции распределения и сбора данных. Операции приведения. Синхронизация.

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

Коллективные обмены 2008 В операцию коллективного обмена вовлечены не два, а большее число процессов.

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

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

Коллективные обмены 2008 Широковещательная рассылка

Коллективные обмены 2008 Широковещательная рассылка выполняется подпрограммой: int MPI_Bcast(void *buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm) MPI_Bcast(buffer, count, datatype, root, comm, ierr) Параметры этой процедуры одновременно являются входными и выходными: buffer - адрес буфера; count - количество элементов данных в сообщении; datatype - тип данных MPI; root - ранг главного процесса, выполняющего широковещательную рассылку; comm - коммуникатор.

Коллективные обмены 2008 Пример 1 использования широковещательной рассылки #include "mpi.h" #include int main(int argc,char *argv[]) { char data[24]; int myrank, count = 25; MPI_Status status; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0) { strcpy(data, "Hi, Parallel Programmer!"); MPI_Bcast(&data, count, MPI_BYTE, 0, MPI_COMM_WORLD); printf("send: %s\n", data); } else

Коллективные обмены 2008 MPI_Bcast(&data, count, MPI_BYTE, 0, MPI_COMM_WORLD); printf("received: %s\n", data); } MPI_Finalize(); return 0; }

Коллективные обмены 2008 Пример 2 использования широковещательной пересылки #include "mpi.h" #include int main(int argc, char *argv[]) { int myrank; int root = 0; int count = 1; float a, b; int n; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); if (myrank == 0)

Коллективные обмены 2008 printf("Enter a, b, n\n"); scanf("%f %f %i", &a, &b, &n); MPI_Bcast(&a, count, MPI_FLOAT, root, MPI_COMM_WORLD); MPI_Bcast(&b, count, MPI_FLOAT, root, MPI_COMM_WORLD); MPI_Bcast(&n, count, MPI_INT, root, MPI_COMM_WORLD); } else { MPI_Bcast(&a, count, MPI_FLOAT, root, MPI_COMM_WORLD); MPI_Bcast(&b, count, MPI_FLOAT, root, MPI_COMM_WORLD); MPI_Bcast(&n, count, MPI_INT, root, MPI_COMM_WORLD); printf("%i Process got %f %f %i\n", myrank, a, b, n); } MPI_Finalize(); return 0; }

Коллективные обмены 2008 Распределение данных int MPI_Scatter(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *rcvbuf, int rcvcount, MPI_Datatype rcvtype, int root, MPI_Comm comm) MPI_Scatter(sendbuf, sendcount, sendtype, rcvbuf, rcvcount, rcvtype, root, comm, ierr) Входные параметры: sendbuf - адрес буфера передачи; sendcount - количество элементов, пересылаемых каждому процессу (не суммарное количество пересылаемых элементов!); sendtype - тип передаваемых данных; rcvcount - количество элементов в буфере приема; rcvtype - тип принимаемых данных; root - ранг передающего процесса; comm - коммуникатор. Выходной параметр: rcvbuf - адрес буфера приема.

Коллективные обмены 2008 Процесс с рангом root распределяет содержимое буфера передачи sendbuf среди всех процессов. Содержимое буфера передачи разбивается на несколько фрагментов, каждый из которых содержит sendcount элементов. Первый фрагмент передается процессу 0, второй процессу 1 и т. д. Аргументы send имеют значение только на стороне распределяющего процесса root.

Коллективные обмены 2008 Сбор данных Сбор данных от остальных процессов в буфер главной задачи выполняется подпрограммой: int MPI_Gather(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *rcvbuf, int rcvcount, MPI_Datatype rcvtype, int root, MPI_Comm comm) MPI_Gather(sendbuf, sendcount, sendtype, rcvbuf, rcvcount, rcvtype, root, comm, ierr) Каждый процесс в коммуникаторе comm пересылает содержимое буфера передачи sendbuf процессу с рангом root. Процесс root «склеивает» полученные данные в буфере приема.

Коллективные обмены 2008 Порядок склейки определяется рангами процессов, то есть в результирующем наборе после данных от процесса 0 следуют данные от процесса 1, затем данные от процесса 2 и т. д. Аргументы rcvbuf, rcvcount и rcvtype играют роль только на стороне главного процесса. Аргумент rcvcount указывает количество элементов данных, полученных от каждого процесса (но не суммарное их количество). При вызове подпрограмм MPI_Scatter и MPI_Gather из разных процессов следует использовать общий главный процесс.

Коллективные обмены 2008 Сбор данных

Коллективные обмены 2008 Сбор данных от всех процессов и распределение их всем процессам: int MPI_Allgather(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *rcvbuf, int rcvcount, MPI_Datatype rcvtype, MPI_Comm comm) MPI_Allgather(sendbuf, sendcount, sendtype, rcvbuf, rcvcount, rcvtype, comm, ierr) Входные параметры: sendbuf - начальный адрес буфера передачи; sendcount - количество элементов в буфере передачи; sendtype - тип передаваемых данных; rcvcount - количество элементов, полученных от каждого процесса; rcvtype - тип данных в буфере приема; comm - коммуникатор. Выходной параметр: rcvbuf - адрес буфера приема.

Коллективные обмены 2008 Блок данных, переданный от j-го процесса, принимается каждым процессом и размещается в j-м блоке буфера приема recvbuf.

Коллективные обмены 2008 Операция приведения Операция приведения, результат которой передается одному процессу int MPI_Reduce(void *buf, void *result, int count, MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) MPI_Reduce(buf, result, count, datatype, op, root, comm, ierr) Входные параметры: buf - адрес буфера передачи; count - количество элементов в буфере передачи; datatype - тип данных в буфере передачи; op - операция приведения; root - ранг главного процесса; comm - коммуникатор.

Коллективные обмены 2008 MPI_Reduce применяет операцию приведения к операндам из buf, а результат каждой операции помещается в буфер результата result. MPI_Reduce должна вызываться всеми процессами в коммуникаторе comm, а аргументы count, datatype и op в этих вызовах должны совпадать.

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

Коллективные обмены 2008 #include "mpi.h" #include int main(int argc,char *argv[]) { int myrank, i; int count = 5, root = 1; MPI_Group MPI_GROUP_WORLD, subgroup; int ranks[4] = {1, 3, 5, 7}; MPI_Comm subcomm; int sendbuf[5] = {1, 2, 3, 4, 5}; int recvbuf[5]; MPI_Init(&argc, &argv); MPI_Comm_group(MPI_COMM_WORLD, &MPI_GROUP_WORLD); MPI_Group_incl(MPI_GROUP_WORLD, 4, ranks, &subgroup); MPI_Group_rank(subgroup, &myrank); MPI_Comm_create(MPI_COMM_WORLD, subgroup, &subcomm);

Коллективные обмены 2008 if(myrank != MPI_UNDEFINED) { MPI_Reduce(&sendbuf, &recvbuf, count, MPI_INT, MPI_SUM, root, subcomm); if(myrank == root) { printf("Reduced values"); for(i = 0; i < count; i++){ printf(" %i ", recvbuf[i]);} } printf("\n"); MPI_Comm_free(&subcomm); MPI_Group_free(&MPI_GROUP_WORLD); MPI_Group_free(&subgroup); } MPI_Finalize(); return 0; }

Коллективные обмены 2008 Предопределенные операции приведения

Коллективные обмены 2008 Допускается определение собственных операций приведения. Для этого используется подпрограмма: int MPI_Op_create(MPI_User_function *function, int commute, MPI_Op *op) MPI_Op_create(function, commute, op, ierr) Входные параметры: function - пользовательская функция; commute - флаг, которому присваивается значение «истина», если операция коммутативна (результат не зависит от порядка операндов).

Коллективные обмены 2008 Описание типа пользовательской функции выглядит следующим образом: typedef void (MPI_User_function)(void *a, void *b, int *len, MPI_Datatype *dtype) Здесь операция определяется так: b[I] = a[I] op b[I] для I = 0, …, len – 1.

Коллективные обмены 2008 После завершения операций приведения пользовательская функция должна быть удалена. Удаление пользовательской функции выполняется подпрограммой: int MPI_Op_free(MPI_Op *op) MPI_Op_free(op, ierr) После завершения вызова op присваивается значение MPI_OP_NULL.

Коллективные обмены 2008 Пример использования операции приведения: вычисление числа π методом Монте-Карло. Два файла pi_compute.c и mc_trials.c. #include #include "mpi.h" float mc_trials(int trials); main(int argc, char **argv) { float homepi, pisum, pi, avepi; int mytid, nproc, rcode, i; int trials = 10000, rounds = 20, master = 0; MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &mytid); MPI_Comm_size(MPI_COMM_WORLD, &nproc); printf ("MPI task ID = %d\n", mytid);

Коллективные обмены 2008 srandom (mytid); avepi = 0; for (i = 0; i < rounds; i++) { homepi = dboard(trials); rcode = MPI_Reduce(&homepi, &pisum, 1, MPI_FLOAT, MPI_SUM, master, MPI_COMM_WORLD); if (rcode != 0) printf("%d: failure on MPI_Reduce\n", mytid); if (mytid == master) { pi = pisum/nproc; avepi = ((avepi * i) + pi)/(i + 1); printf(" After %3d throws, average value of pi = %10.8f\n", (trials * (i + 1)),avepi); } MPI_Finalize(); }

Коллективные обмены 2008 #include #define sqr(x)((x)*(x)) float mc_trials(int trials) { double x_coord, y_coord, pi, r; int score, n; unsigned long cconst = ; score = 0; for (n = 1; n

Коллективные обмены 2008 pi = 4.0 * (double)score/(double)trials; return(pi); }

Коллективные обмены 2008 Операция сканирования Операции сканирования (частичной редукции) выполняются следующей подпрограммой: int MPI_Scan(void *sendbuf, void *rcvbuf, int count, MPI_Datatype datatype, MPI_Op op, MPI_Comm comm) MPI_Scan(sendbuf, rcvbuf, count, datatype, op, comm, ierr) Входные параметры: sendbuf - начальный адрес буфера передачи; count - количество элементов во входном буфере; datatype - тип данных во входном буфере; op - операция; comm - коммуникатор. Выходной параметр: rcvbuf - стартовый адрес буфера приема.

Коллективные обмены 2008 При выполнении операции сканирования в буфере приёма процесса с рангом i будут содержаться результаты приведения значений в буферах передачи процессов с рангами 0, …, i. В остальном эта операция аналогична операции MPI_Reduce.

Коллективные обмены 2008 Векторная операция распределения данных Векторная подпрограмма распределения данных: int MPI_Scatterv(void *sendbuf, int *sendcounts, int *displs, MPI_Datatype sendtype, void *rcvbuf, int rcvcount, MPI_Datatype rcvtype, int root, MPI_Comm comm) MPI_Scatterv(sendbuf, sendcounts, displs, sendtype, rcvbuf, rcvcount, rcvtype, root, comm, ierr) Входные параметры: sendbuf - адрес буфера передачи; sendcounts - целочисленный одномерный массив, содержащий количество элементов, передаваемых каждому процессу (индекс равен рангу адресата). Его длина равна количеству процессов в коммуникаторе;

Коллективные обмены 2008 Входные параметры: displs - целочисленный массив, длина которого равна количеству процессов в коммуникаторе. Элемент с индексом i задает смещение относительно начала буфера передачи. Ранг адресата равен значению индекса i; sendtype - тип данных в буфере передачи; rcvcount - количество элементов в буфере приема; rcvtype - тип данных в буфере приема; root - ранг передающего процесса; comm - коммуникатор. Выходной параметр: rcvbuf - адрес буфера приема.

Коллективные обмены 2008 Векторная операция сбора данных Сбор данных от всех процессов в заданном коммуникаторе и запись их в буфер приема с указанным смещением выполняется подпрограммой векторного сбора данных: int MPI_Gatherv(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *recvbuf, int *recvcounts, int *displs, MPI_Datatype recvtype, int root, MPI_Comm comm) MPI_Gatherv(sendbuf, sendcount, sendtype, recvbuf, recvcounts, displs, recvtype, root, comm, ierr) Список параметров у этой подпрограммы похож на список параметров подпрограммы MPI_Scatterv. В обменах, выполняемых подпрограммами MPI_Allgather и MPI_Alltoall, нет главного процесса. Детали отправки и приема важны для всех процессов, участвующих в обмене.

Коллективные обмены 2008 Пересылка данных по схеме «каждый - всем» int MPI_Alltoall(void *sendbuf, int sendcount, MPI_Datatype sendtype, void *rcvbuf, int rcvcount, MPI_Datatype rcvtype, MPI_Comm comm) MPI_Alltoall(sendbuf, sendcount, sendtype, rcvbuf, rcvcount, rcvtype, comm, ierr) Входные параметры: sendbuf - начальный адрес буфера передачи; sendcount - количество элементов данных, пересылаемых каждому процессу; sendtype - тип данных в буфере передачи; rcvcount - количество элементов данных, принимаемых от каждого процесса; rcvtype - тип принимаемых данных; comm - коммуникатор. Выходной параметр: rcvbuf - адрес буфера приема.

Коллективные обмены 2008 Векторными версиями MPI_Allgather и MPI_Alltoall являются подпрограммы MPI_Allgatherv и MPI_Alltoallv. Векторные операции позволяют детализировать процесс коллективного обмена.

Коллективные обмены 2008 Синхронизация Синхронизация с помощью «барьера» выполняется с помощью подпрограммы: int MPI_Barrier(MPI_Comm comm) MPI_Barrier(comm, ierr) Синхронизация с помощью «барьера» - простейшая форма синхронизации коллективных обменов. Она не требует пересылки данных. Обращение к подпрограмме MPI_Barrier блокирует выполнение каждого процесса из коммуникатора comm до тех пор, пока все процессы не вызовут эту подпрограмму, таким образом, «толщина барьера» здесь максимальная – она равна числу процессов в указанном коммуникаторе. Барьерная синхронизация относится к числу коллективных операций потому, что выполнить соответствующий вызов должны все процессы.

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

2008 Задания для самостоятельной работы Решения следует высылать по электронной почте:

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

2008 Задания для самостоятельной работы Напишите параллельную программу вычисления произведения матрицы на матрицу. Используйте ленточную декомпозицию и операции коллективного обмена.

Тема следующей лекции 2008 Группы процессов и коммуникаторы