Lect_6_24112015 (MPI)

Параллельное программирование длявысокопроизводительных системсентябрь – декабрь 2015 г.Лекция MPI_624 ноября 2015 г.Лектор доцент Н.Н.ПоповаЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.20151ТемаВиртуальные топологии MPIБлочные параллельные алгоритмыматричного умножения.Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.20152Виртуальные топологииТопология – механизм сопоставления процессамальтернативной схемы адресации. В MPI топологиивиртуальны, не связаны с физической топологиейсети.Два типа топологий:- декартова (прямоугольная решеткапроизвольной размерности)- топология графа.Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.20153Декартова топологияЛогическая топология, определяемая многомернойрешеткой.Обобщение линейной и матричной топологий напроизвольное число измерений.Для создания коммуникатора с декартовойтопологией используется функция MPI_Cart_create.С помощью этой функции можно создаватьтопологии с произвольным числом измерений,причем по каждому измерению в отдельности можнонакладывать периодические граничные условия.Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.20154Виртуальные топологииОсновные функции:MPI_CART_CREATEMPI_CART_COORDSMPI_CART_RANKMPI_CART_SUBMPI_CARTDIM_GETMPI_CART_GETMPI_CART_SHIFTЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.20155MPI_CART_CREATEСоздает структуру «прямоугольная решетка»произвольной размерности.int MPI_Cart_create(MPI_Comm old_comm, int ndims, int*dim_size, int *periods, int reorder, MPI_Comm *new_comm).Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.20156MPI_CART_CREATEПараметрыold_commMPI_CommInputИсходный коммуникаторndimsintInputЧисло измеренийdim_sizeint *InputМассив размера ndims длязадания числа элементов покаждой из размерностейperiodsint *InputМассив размера ndims длязадания «периодичности» покаждой из размерностейreorderintInputФлаг для заданияпереупорядочиванияэлементовnew_commMPI_Comm *OutputНовый коммуникаторЛекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.20157MPI_Cart_createФункция является коллективной, т.е. должна запускаться навсех процессах, входящих в группу коммуникатора comm_old.Если какие-то процессы не попадают в новую группу, то для нихвозвращается результат MPI_COMM_NULL. В случае, когдаразмеры заказываемой сетки больше имеющегося в группечисла процессов, функция завершается аварийно.Значение параметра reorder=false означает, что идентификаторывсех процессов в новой группе будут такими же, как в старойгруппе. Если reorder=true, то MPI будет пытатьсяперенумеровать их с целью оптимизации коммуникаций.Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.20158Пример виртуальной топологиирешеткаMPI_Comm vu;int dim[2], period[2], reorder;dim[0]=4; dim[1]=3;period[0]=TRUE; period[1]=FALSE;reorder=TRUE;MPI_Cart_create(MPI_COMM_WORLD,2,dim,period,reorder,&vu);Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.20159Определение оптимальнойконфигурации декартовой решеткиint MPI_Dims_create(int nnodes, int ndims, int *dims)nnodes - общее число узлов в сетке;ndims - число измерений;dims - массив целого типа размерности ndims, в который помещаетсярекомендуемое число процессов вдоль каждого измерения.В массив dims должны быть занесены целые неотрицательные числа.Если элементу массива dims[i] присвоено положительное число, тодля этой размерности вычисление не производится (число процессоввдоль этого направления считается заданным).

Вычисляются толькоте компоненты dims[i], для которых перед обращением к процедуребыли присвоены значения 0. Функция стремится создатьмаксимально равномерное распределение процессов вдольнаправлений, выстраивая их по убыванию, т.е. для 12-ти процессовона построит трехмерную сетку 4 х 3 х 1.Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201510MPI_CARTDIM_GETОпределение числа измерений врешетке.int MPI_Cartdim_get( MPI_Comm comm, int* ndims )- comm- ndimsкоммуникатор (решетка)число измеренийЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201511MPI_CARTDIM_GETПример/* create column subgrids */belongs[0] = 1;belongs[1] = 0;MPI_Cart_sub(grid_comm, belongs, &col_comm);/* queries number of dimensions of cartesan grid */MPI_Cartdim_get(col_comm, &ndims);Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201512MPI_CART_COORDSint MPI_Cart_coords( MPI_Comm comm, int rank, int maxdims,int *coords)Перевод номера процесса в его координаты в решеткеЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201513MPI_CART_COORDSПараметрыcommMPI_Comm InputКоммуникаторrankintInputРанг процессаmaxdimsintInputЧисло измеренийрешеткиcoordsint *Outpu Координаты вtрешеткеЛекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201514MPI_CART_RANKИспользуется для перевода логическихкоординат поцесса в решетке в рангпроцесса.int MPI_Cart_rank( MPI_Comm comm, int *coords, int *rank )Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201515MPI_CART_RANKПараметрыcommMPI_CommInputПараметрыcoordsint *InputМассив размера ndimsопределяющийкоординаты процессав решеткеrankintOutput Ранг процессаЛекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201516MPI_CART_SUBИспользуется для разделения коммуникатора наподгруппы .MPI_CART_SUB создает новый коммуникаторменьшей размерностиint MPI_Cart_sub( MPI_Comm old_comm, int *belongs,MPI_Comm *new_comm )Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201517MPI_CART_SUBПараметрыold_commMPI_CommInputПараметрыbelongsint *InputМассив размераndims, определяющийпринадлежностьновомукоммуникаторуnew_commnew_commMPI_CommOutput Новый коммуникаторрешеткаЛекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201518MPI_CART_SUB примерПредполагаем, что число процессов =6.Формируем 2D (3x2) решетку. Заполняем матрицуA(i,j)A(i,j) = (i+1)*10 + j + 1; i=0,1,2; j=0,1Значения элементов:A(0,0) = 11, A(2,1) = 32 и т.д..Создаем подрешетку, используя MPI_CART_SUB.Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201519MPI_CART_SUB пример#include "stdio.h"#include "mpi.h"void main(int argc, char *argv[]){int nrow, mcol, i, lastrow, p, root;int Iam, id2D, colID, ndim;int coords1D[2], coords2D[2], dims[2], aij[1], alocal[3];int belongs[2], periods[2], reorder;MPI_Comm comm2D, commcol;/* Starts MPI processes ...

*/MPI_Init(&argc, &argv); /* starts MPI */MPI_Comm_rank(MPI_COMM_WORLD, &Iam);/* get current process id */MPI_Comm_size(MPI_COMM_WORLD, &p);/* get number of processes */Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201520MPI_CART_SUB примерnrow = 3; mcol = 2; ndim = 2;root = 0; periods[0] = 1; periods[1] = 0; reorder = 1;/* create cartesian topology for processes */dims[0] = ncol;/* number of columns */dims[1] = mrow;/* number of rows */MPI_Cart_create(MPI_COMM_WORLD, ndim, dims, periods, reorder,&comm2D);MPI_Comm_rank(comm2D, &id2D);MPI_Cart_coords(comm2D, id2D, ndim, coords2D);/* Create 1D column subgrids */belongs[0] = 1;/* this dimension belongs to subgrid */belongs[1] = 0;MPI_Cart_sub(comm2D, belongs, &commcol);MPI_Comm_rank(commcol, &colID);MPI_Cart_coords(commcol, colID, 1, coords1D);Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201521MPI_CART_SUB примерMPI_Barrier(MPI_COMM_WORLD);/* aij = (i+1)*10 + j + 1; 1 matrix element to each proc */aij[0] = (coords2D[0]+1)*10 + coords2D[1]+1;if(Iam == root) {printf("\n MPI_Cart_sub example:");printf("\n 3x2 cartesian grid ==> 2 (3x1) column subgrids\n");printf("\n Iam 2D2D1D1Daij");printf("\n Rank Rank coords.

Rank coords.\n");}/* Last element of each column gathers elements of its own column */for ( i=0; i<=nrow-1; i++) {alocal[i] = -1;}Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201522MPI_CART_SUB примерlastrow = nrow - 1;MPI_Gather(aij, 1, MPI_INT, alocal, 1, MPI_INT, lastrow, commcol);MPI_Barrier(MPI_COMM_WORLD);printf("%6d|%6d|%6d %6d|%6d|%8d|",Iam,id2D,coords2D[0],coords2D[1],colID,coords1D[0]);for (i=0; i<=lastrow; i++) {printf("%6d ",alocal[i]);}printf("\n");MPI_Finalize();/* let MPI finish up ... */}Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.201523MPI_CART_GETПараметрыsubgrid_commMPI_CommInputКоммуникаторndimsintInputЧисло измеренийdimsint *OutputМассив длин по каждому изизмеренийperiodsint *OutputПериодичность понаправлениямcoordsint *OutputКоординаты вызывающегопроцесса в решетке (массивразмера ndims )Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201524MPI_CART_GETИспользуется для получения информации о параметрахдекартовой топологии для заданного коммуникатораint MPI_Cart_sub( MPI_Comm comm, int maxdims,int *dims, int *periods, int *coords)Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201525MPI_CART_GET пример/* create Cartesian topology for processes */dims[0] = nrow;dims[1] = mcol;MPI_Cart_create(MPI_COMM_WORLD, ndim, dims, period,reorder, &grid_comm);MPI_Comm_rank(grid_comm, &me);MPI_Cart_coords(grid_comm, me, ndim, coords);/* create row subgrids */belongs[0] = 1;belongs[1] = 0;MPI_Cart_sub(grid_comm, belongs, &row_comm);/* Retrieve subgrid dimensions and other info */MPI_Cartdim_get(row_comm, &mdims);MPI_Cart_get(row_comm, mdims, dims, period, row_coords);Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201526MPI_CART_SHIFTПолучение номеров процессов, находящихся назаданном расстоянии displacement от текущего процессав заданном измерении direction декартовой решетки.int MPI_Cart_shift( MPI_Comm comm, intdirection, int displ, int *source, int *dest )Лекции спецкурс "Пар. прогр.

длявысокопроизводительных систем",24.11.201527MPI_CART_SHIFTПараметрыcommMPI_CommInputКоммуникаторdirectionintInputРазмерность, по которой будетпроизводиться сдвигdisplintInputВеличина и направлениесдвига (<0; >0; or 0)sourceint *OutputПроцесс- источникdestint *OutputПроцесс- получательЛекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201528MPI_CART_SHIFTДля периодических измерений осуществляетсяциклический сдвиг, для непериодических – линейныйсдвиг.Для n-мерной декартовой решетки значение directionдолжно быть в пределах от 0 до n-1.Значения source и dest можно использовать,например, для обмена функцией MPI_Sendrecv.Не является коллективной операцией!Лекции спецкурс "Пар.

прогр. длявысокопроизводительных систем",24.11.201529Пример декартовой решетки(send&recv, mesh)MPI_Request reqs[8];MPI_Status stats[8];MPI_Comm cartcomm;int dims[2],periods[2], reorder, coords[2];MPI_Init(&argc,&argv);MPI_Comm_size(MPI_COMM_WORLD, &numtasks);if (numtasks == SIZE) {// define dims, periods, reorderMPI_Cart_create(MPI_COMM_WORLD, 2, dims, periods, reorder, &cartcomm);MPI_Comm_rank(cartcomm, &rank);MPI_Cart_coords(cartcomm, rank, 2, coords);MPI_Cart_shift(cartcomm, 1, 1, &nbrs[UP], &nbrs[DOWN]);MPI_Cart_shift(cartcomm, 0, 1, &nbrs[LEFT], &nbrs[RIGHT]);outbuf = rank;Лекции спецкурс "Пар. прогр. длявысокопроизводительных систем",24.11.201530Пример декартовой решетки(send&recv, mesh)for (i=0; i<4; i++) {dest = nbrs[i];source = nbrs[i];MPI_Isend(&outbuf, 1, MPI_INT, dest, tag, MPI_COMM_WORLD, &reqs[i]);MPI_Irecv(&inbuf[i], 1, MPI_INT, source, tag, MPI_COMM_WORLD,&reqs[i+4]);}MPI_Waitall(8, reqs, stats);printf("rank= %d coords= %d %d neighbors(u,d,l,r)= %d %d %d %dinbuf(u,d,l,r)= %d %d %d %d\n",rank,coords[0],coords[1],nbrs[UP],nbrs[DOWN],nbrs[LEFT],inbuf[UP],inbuf[DOWN],inbuf[LEFT],inbuf[RIGHT]);}elseprintf("Must specify %d tasks.