Программирование для многопроцессорных систем в стандарте MPI - Шпаковский Г.И., Серикова Н.В.. Программирование для многопроцессорных систем в стандарте MPI -. Организация вычислений в многопроцессорных системах
 Скачать 1.61 Mb.
|
|
Глава 4. КОЛЛЕКТИВНЫЕ ВЗАИМОДЕЙСТВИЯ ПРОЦЕССОВ 4.1. ВВЕДЕНИЕ К операциям коллективного обмена относятся (рис. 4.1): • Барьерная синхронизация всех процессов группы (параграф 4.2.1). • Широковещательная передача (broadcast) от одного процесса всем остальным процессам группы (параграф 4.2.2). • Сбор данных из всех процессов группы в один процесс (параграф 4.2.3). • Рассылка данных одним процессом группы всем процессам груп- пы (параграф 4.2.4). • Сбор данных, когда все процессы группы получают результат (па- раграф 4.2.5). Этот вариант представлен на рис. 4.1 как “allgather”. • Раздача/сбор данных из всех процессов группы всем процессам группы (параграф 4.2.6). Этот вариант называется также полным обменом или all-to-all. • Глобальные операции редукции, такие как сложение, нахождение максимума, минимума или определенные пользователем функции, где результат возвращается всем процессам группы или в один процесс (параграф 4.3). • Составная операция редукции и раздачи (параграф 4.3.5). • Префиксная операция редукции, при которой в процессе i появля- ется результат редукции 0, 1, …, i, i ≤ n, где n – число процессов в группе (параграф 4.3.6). 108 Рис. 4.1. Операции коллективного обмена. В каждом случае строка прямоугольника представляет данные одного процесса, поэтому, напри- мер, в операции broadcast сначала один процесс содержит A0, но после операции все процессы содержат это значение. Коллективная операция исполняется путем вызова всеми процес- сами в группе коммуникационных функций с соответствующими ар- гументами. В коллективных операциях используются основные типы данных, и они должны совпадать у процесса-отправителя и процесса- получателя. Один из ключевых аргументов – это коммуникатор, кото- рый определяет группу участвующих в обмене процессов и обеспечи- вает контекст для этой операции. Различные коллективные операции (широковещание, сбор дан- ных) имеют единственный процесс-отправитель или процесс- получатель. Такие процессы называются корневыми (root). Некоторые аргументы в коллективных функциях определены как “существенные только для корневого процесса” и игнорируются для всех других уча- стников операции. Условия соответствия типов для коллективных операций более строгие, чем аналогичные условия для парного обмена. А именно для коллективных операций количество посланных данных должно точно соответствовать количеству данных, описанных в процессе-получа- A0 A0 A0 A0 A0 A0 A1 A2 A3 A0 A1 A2 A3 A B C D A B C D A B C D A B C D A B C D A0 A1 A2 A3 B0 B1 B2 B3 C0 C1 C2 C3 D0 D1 D2 D3 A0 B0 C0 D0 A1 B1 C1 D1 A2 B2 C2 D2 A3 B3 C3 D3 broadcast scatter gather allgather alltoall 109 теле. Вызов коллективной функции может возвращать управление сразу, как только его участие в коллективной операции завершено. Завершение вызова показывает, что процесс-отправитель может обра- щаться к буферу обмена. Это не означает, что другие процессы в группе завершили операцию. Таким образом, вызов операции коллек- тивного обмена может иметь эффект синхронизации всех процессов в группе. Это утверждение не относится к барьерной функции. Вызовы коллективных операций могут использовать те же комму- никаторы, что и парный обмен, при этом MPI гарантирует, что сооб- щения, созданные коллективными операциями, не будут смешаны с сообщениями, созданными парным обменом. Ключевым понятием в коллективных функциях является группа участвующих процессов, но в качестве явного аргумента выступает коммуникатор. Коммуникатор понимается как идентификатор груп- пы, связанный с контекстом. Не разрешается использовать в качестве аргумента коллективной функции интер-коммуникатор (коммуника- тор, соединяющий две группы). 4.2. КОЛЛЕКТИВНЫЕ ОПЕРАЦИИ 4.2.1. Барьерная синхронизация MPI_BARRIER (comm) IN comm коммуникатор (дескриптор) int MPI_Barrier (MPI_Comm comm) MPI_BARRIER (COMM, IERROR) INTEGER COMM, IERROR void MPI::Intracomm::Barrier() const Функция барьерной синхронизации MPI_BARRIER блокирует вызывающий процесс, пока все процессы группы не вызовут ее. В ка- ждом процессе управление возвращается только тогда, когда все про- цессы в группе вызовут процедуру. 4.2.2. Широковещательный обмен Функция широковещательной передачи MPI_BCAST посылает сообщение из корневого процесса всем процессам группы, включая себя. Она вызывается всеми процессами группы с одинаковыми аргу- ментами для comm, root . В момент возврата управления содержимое корневого буфера обмена будет уже скопировано во все процессы. 110 MPI_BCAST(buffer, count, datatype, root, comm ) INOUT buffer адрес начала буфера (альтернатива) IN count количество записей в буфере (целое) IN datatype тип данных в буфере (дескриптор) IN root номер корневого процесса (целое) IN comm коммуникатор (дескриптор) int MPI_Bcast(void* buffer, int count, MPI_Datatype datatype, int root, MPI_Comm comm ) MPI_BCAST(BUFFER, COUNT, DATATYPE, ROOT, COMM, IERROR) INTEGER COUNT, DATATYPE, ROOT, COMM, IERROR void MPI::Intracomm::Bcast(void* buffer, int count, const Datatype& datatype,int root) const В аргументе datatype можно задавать производные типы данных. Сигнатура типа данных count, datatype любого процесса обязана сов- падать с соответствующей сигнатурой в корневом процессе. Это тре- бует, чтобы количество посланных и полученных данных совпадало попарно для корневого и каждого другого процессов. Такое ограниче- ние имеют и все другие коллективные операции, выполняющие пере- мещение данных. Пример 4.1. Широковещательная передача 100 целых чисел от про- цесса 0 каждому процессу в группе. MPI_Comm comm; int array[100]; int root = 0; MPI_Bcast( array, 100, MPI_INT, root, comm ); 4.2.3. Сбор данных При выполнении операции сборки данных MPI_GATHER каждый процесс, включая корневой, посылает содержимое своего буфера в корневой процесс. Корневой процесс получает сообщения, располагая их в порядке возрастания номеров процессов. Результат будет такой же, как если бы каждый из n процессов группы (включая корневой процесс) вы- полнил вызов MPI_Send (sendbuf, sendcount, sendtype, root, …), и корневой процесс выполнил n вызовов 111 MPI_Recv(recvbuf + i * recvcount * extent(recvtype), recvcount, recvtype, i, …), где extent(recvtype) – размер типа данных, получаемый с помощью MPI_Type_extent(). MPI_GATHER( sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, root, comm) IN sendbuf начальный адрес буфера процесса-отправителя (альтернатива) IN sendcount количество элементов в отсылаемом сообщении (целое) IN sendtype тип элементов в отсылаемом сообщении (дескриптор) OUT recvbuf начальный адрес буфера процесса сборки данных (аль- тернатива, существенен только для корневого процесса) IN recvcount количество элементов в принимаемом сообщении (целое, имеет значение только для корневого процесса) IN recvtype тип данных элементов в буфере процесса-получателя (дескриптор) IN root номер процесса-получателя (целое) IN comm коммуникатор (дескриптор) int MPI_Gather(void* sendbuf, int sendcount, MPI_Datatype sendtype, void* recvbuf, int recvcount, MPI_Datatype recvtype, int root, MPI_Comm comm) MPI_GATHER(SENDBUF, SENDCOUNT, SENDTYPE, RECVBUF, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR) INTEGER SENDCOUNT, SENDTYPE, RECVCOUNT, RECVTYPE, ROOT, COMM, IERROR void MPI::Intracomm::Gather(const void* sendbuf, int sendcount, const Datatype& sendtype, void* recvbuf, int recvcount, const Datatype& recvtype, int root) const В общем случае как для sendtype, так и для recvtype разрешены производные типы данных. Сигнатура типа данных sendcount, sendtype у процесса i должна быть такой же, как сигнатура recvcount, recvtype корневого процесса. Это требует, чтобы количество послан- ных и полученных данных совпадало попарно для корневого и каж- дого другого процессов. Разрешается различие в картах типов между отправителями и получателями. В корневом процессе используются все аргументы функции, в то время как у остальных процессов используются только аргументы sendbuf, sendcount, sendtype, root, comm. Аргументы comm и root должны иметь одинаковые значения во всех процессах. 112 Описанные в функции MPI_GATHER количества и типы данных не должны являться причиной того, чтобы любая ячейка корневого процесса записывалась бы более одного раза. Такой вызов является неверным. Аргумент recvcount в главном процессе показывает количество элементов, которые он получил от каждого процесса, а не общее ко- личество полученных элементов. MPI_GATHERV ( sendbuf, sendcount, sendtype, recvbuf, recvcounts, displs, recvtype, root, comm) IN sendbuf начальный адрес буфера процесса-отправителя (альтернатива) IN sendcount количество элементов в отсылаемом сообщении (целое) IN sendtype тип элементов в отсылаемом сообщении (дескриптор) OUT recvbuf начальный адрес буфера процесса сборки данных (альтер- натива, существенно для корневого процесса) IN recvcounts массив целых чисел (по размеру группы), содержащий ко- личество элементов, которые получены от каждого из про- цессов (используется корневым процессом) IN displs массив целых чисел (по размеру группы). Элемент i опре- деляет смещение относительно recvbuf, в котором размещаются данные из процесса i (используется корневым процессом) IN recvtype тип данных элементов в буфере процесса-получателя (дескриптор) IN root номер процесса-получателя (целое) IN comm коммуникатор (дескриптор) 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, IERROR) INTEGER SENDCOUNT, SENDTYPE, RECVCOUNTS(*), DISPLS(*), RECVTYPE, ROOT, COMM, IERROR void MPI::Intracomm::Gatherv(const void* sendbuf, int sendcount, const Datatype& sendtype, void* recvbuf, const int recvcounts[], const int displs[], const Datatype& recvtype, int root) const По сравнению с MPI_GATHER при использовании функции MPI_GATHERV разрешается принимать от каждого процесса пере- менное число элементов данных, поэтому в функции MPI_GATHERV аргумент recvcount является массивом. Она также 113 обеспечивает большую гибкость в размещении данных в корневом процессе. Для этой цели используется новый аргумент displs Выполнение MPI_GATHERV будет давать такой же результат, как если бы каждый процесс, включая корневой, посылал корневому процессу сообщение: MPI_Send(sendbuf, sendcount, sendtype, root, …), и корневой процесс выполнял n операций приема: MPI_Recv(recvbuf+displs[i]*extern(recvtype), recvcounts[i], recvtype, i, …). Сообщения помещаются в принимающий буфер корневого про- цесса в порядке возрастания их номеров, то есть данные, посланные процессом j , помещаются в j -ю часть принимающего буфера recvbuf на корневом процессе. j -я часть recvbuf начинается со смещения displs[j]. Номер принимающего буфера игнорируется во всех некор- невых процессах. Сигнатура типа, используемая sendcount , sendtype в процессе i должна быть такой же, как и сигнатура, используемая recvcounts[i] , recvtype в корневом процессе. Это требует, чтобы коли- чество посланных и полученных данных совпадало попарно для кор- невого и каждого другого процессов. Разрешается различие в картах типов между отправителями и получателями. В корневом процессе используются все аргументы функции MPI_GATHERV , а на всех других процессах используются только аргументы sendbuf, sendcount, sendtype, root, comm Переменные comm и root должны иметь одинаковые значения во всех процессах. Описанные в функции MPI_GATHERV количества, типы данных и смещения не должны приводить к тому, чтобы любая область корне- вого процесса записывалась бы более одного раза. Пример 4.2. Сбор 100 целых чисел с каждого процесса группы в кор- невой процесс (рис. 4.2). MPI_Comm comm; int gsize,sendarray[100]; int root, *rbuf; MPI_Comm_size( comm, &gsize); rbuf = (int *)malloc(gsize*100*sizeof(int)); MPI_Gather(sendarray,100, MPI_INT, rbuf,100,MPI_INT,root, comm); Пример 4.3 Предыдущий пример модифицирован – только корневой процесс назначает память для буфера приема. 114 MPI_Comm comm; int gsize,sendarray[100]; int root, myrank, *rbuf; MPI_Comm_rank( comm, myrank); if ( myrank == root) { MPI_Comm_size( comm, &gsize); rbuf = (int *)malloc(gsize*100*sizeof(int)); } MPI_Gather(sendarray,100,MPI_INT, rbuf,100, MPI_INT, root,comm); Рис. 4.2. Корневой процесс собирает по 100 целых чисел из каждого процесса в группе Пример 4.4. Программа делает то же, что и в предыдущем примере, но использует производные типы данных. MPI_Comm comm; int gsize,sendarray[100]; int root, *rbuf; MPI_Datatype rtype; MPI_Comm_size( comm, &gsize); MPI_Type_contiguous( 100, MPI_INT, &rtype ); MPI_Type_commit( &rtype ); rbuf = (int *)malloc(gsize*100*sizeof(int)); MPI_Gather( sendarray, 100, MPI_INT, rbuf, 1, rtype, root, comm); Пример 4.5. Каждый процесс посылает 100 чисел int корневому про- цессу, но каждое множество (100 элементов) размещается с некото- рым шагом ( stride) относительно конца размещения предыдущего множества. Для этого нужно использовать MPI_GATHERV и аргу- мент displs . Полагаем, что stride ≥ 100 (рис. 4.3). 100 100 100 100 100 100 rbuf Все процессы Корневой процесс 115 MPI_Comm comm; int gsize,sendarray[100], root, *rbuf, stride, *displs,i,*rcounts; MPI_Comm_size( comm, &gsize); rbuf = (int *)malloc(gsize*stride*sizeof(int)); displs = (int *)malloc(gsize*sizeof(int)); rcounts = (int *)malloc(gsize*sizeof(int)); for (i=0; i MPI_Gatherv( sendarray, 100, MPI_INT, rbuf, rcounts, displs, MPI_INT, root, comm); Рис. 4.3. Корневой процесс собирает множество из 100 целых чисел из каждого процесса в группе, и каждое множество размещается с не- которым страйдом относительно предыдущего размещения Программа неверна, если stride < 100 Пример 4.6. Со стороны процесса-получателя пример такой же, как и 4.5, но посылается 100 чисел типа int из 0-го столбца массива 100×150 чисел типа int (рис. 4.4). MPI_Comm comm; int gsize,sendarray[100][150], root, *rbuf, stride, *displs,i,*rcounts; MPI_Datatype stype; MPI_Comm_size( comm, &gsize); rbuf = (int *)malloc(gsize*stride*sizeof(int)); displs = (int *)malloc(gsize*sizeof(int)); rcounts = (int *)malloc(gsize*sizeof(int)); for (i=0; i rbuf Страйд Все процессы Корневой процесс 116 /* Create datatype for 1 column of array */ MPI_Type_vector( 100, 1, 150, MPI_INT, &stype); MPI_Type_commit( &stype ); MPI_Gatherv( sendarray, 1, stype, rbuf, rcounts, displs, MPI_INT, root, comm); Рис. 4.4. Корневой процесс собирает столбец 0 массива 100×150, и каждое множество размещается с некоторым страйдом по отношению к предыдущему Пример 4.7. Процесс i посылает 100 чисел типа int из i -го столбца массива 100×150 чисел типа int (рис. 4.5) MPI_Comm comm; int gsize,sendarray[100][150],*sptr, root, *rbuf, stride, myrank, *displs,i,*rcounts; MPI_Datatype stype; MPI_Comm_size( comm, &gsize); MPI_Comm_rank( comm, &myrank ); rbuf = (int *)malloc(gsize*stride*sizeof(int)); displs = (int *)malloc(gsize*sizeof(int)); rcounts = (int *)malloc(gsize*sizeof(int)); for (i=0; i } /* отличие от предыдущего примера */ /* создается тип данных для посылаемого столбца */ MPI_Type_vector( 100-myrank, 1, 150, MPI_INT, &stype); MPI_Type_commit( &stype ); /* sptr есть адрес начала столбца "myrank" */ sptr = &sendarray[0][myrank]; MPI_Gatherv(sptr,1,stype,rbuf,rcounts,displs,MPI_INT,root,comm); Из каждого процесса получено различное количество данных. 150 150 150 100 100 100 100 100 100 100 Все процессы Корневой процесс rbuf Страйд 100 100 100 100 117 Рис. 4.5. Корневой процесс собирает множество из100-i целых чисел столбца i массива 100 ×150, и каждое множество размещается с отдельным страйдом Пример 4.8. Пример такой же, как и 4.7, но содержит отличие на пе- редающей стороне. Создается тип данных со страйдом на передающей стороне для чтения столбца массива. MPI_Comm comm; int gsize,sendarray[100][150],*sptr,root, *rbuf, stride, myrank, disp[2], blocklen[2]; MPI_Datatype stype,type[2]; int *displs,i,*rcounts; MPI_Comm_size( comm, &gsize); MPI_Comm_rank( comm, &myrank ); rbuf = (int *)malloc(gsize*stride*sizeof(int)); displs = (int *)malloc(gsize*sizeof(int)); rcounts = (int *)malloc(gsize*sizeof(int)); for (i=0; i } /* создается тип для числа int с расширением на полную строку */ disp[0] = 0; disp[1] = 150*sizeof(int); type[0] = MPI_INT; type[1] = MPI_UB; blocklen[0] = 1; blocklen[1] = 1; MPI_Type_struct( 2, blocklen, disp, type, &stype ); MPI_Type_commit( &stype ); sptr = &sendarray[0][myrank]; MPI_Gatherv( sptr, 100-myrank, stype, rbuf, rcounts, displs, MPI_INT, root, comm); 150 150 150 100 100 100 100 100 100 99 98 100 Все процессы Корневой процесс rbuf Страйд |