Гергель В.П. Общий курс Теория и практика параллельных вычислений Лекция 9 Методы разработки параллельных программ при использования интерфейса передачи. - презентация

1 Гергель В.П. Общий курс Теория и практика параллельных вычислений Лекция 9 Методы разработки параллельных программ при использования интерфейса передачи сообщений MPI – 3 Нижегородский Государственный Университет им. Н.И. Лобачевского

2 Параллельные Гергель В.П. ННГУ, Н.Новгород, Содержание Использование виртуальных топологий Применение топологии в виде решетки Пример: Решение задачи Пуассона Вопросы для обсуждения Задания для самостоятельной работы Заключение Следующая тема

3 Параллельные Гергель В.П. ННГУ, Н.Новгород, Использование виртуальных топологий Использование топологий позволяет снизить сложность разработки параллельных программ (применение "естественных" для параллельного алгоритма структуры коммуникационных связей) В MPI имеется широко используемая в практике вычислений предопределенная топология в виде прямоугольной решетки (cartesian or grid topology) В состав MPI входит набор функций для создания новой (пользовательской) топологии в виде определенной графовой структуры

4 Параллельные Гергель В.П. ННГУ, Н.Новгород, Применение топологии в виде решетки… Создание топологии int MPI_Cart_create(MPI_Comm oldgcomm, int ndim, int sizes[], int wrap[], int reorder, MPI_Comm *newcomm); где - ndim - размерность решетки, - sizes[] – количество процессов по каждому измерению, - wrap[] - наличие связи (при wrap[i]>0) между первым и последним процессами по каждому измерению - reorder – необходимость оптимизации топологии под структуру физической сети Перевод ранга в координаты решетки int MPI Cart_coords(MPI_Com com, int rank, int ndim, int coords[]); Перевод координат решетки в ранг процесса int MPI Cart _ rank(MPI_Com com, int coords[], int *rank);

5 Параллельные Гергель В.П. ННГУ, Н.Новгород, Применение топологии в виде решетки… Определение параметров решетки int MPI_Dims_create(int nnodes, int ndim, int sizes[]); где - nnodes - количество процессов, - ndim - размерность решетки, - sizes[] – количество процессов по каждому измерению

6 Параллельные Гергель В.П. ННГУ, Н.Новгород, Применение топологии в виде решетки… Создание решетки меньшей размерности int MPI_Cart_sub(MPI_Comm comm, int freedims[], MPI_Comm *newcomm); где - freedims[] – признак фиксируемости измерений (0 –фиксировано, 1 – не фиксировано) ! Операция является коллективной Пример: Создание коммуникаторов для строк решетки freedims[0]=0; freedims[1]=1; MPI_Cart_sub(cart_comm, freedims[], &row_comm);

7 Параллельные Гергель В.П. ННГУ, Н.Новгород, Применение топологии в виде решетки Определение рангов соседних процессов int MPI_Cart_shift(MPI_Comm comm, int dim, int dir, int *rank1, int *rank2); где - dim – номер размерности, по которой определяются соседи, - dir – направление ( >0 слева направо и снизу вверх,

8 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Задача Пуассона определяется уравнениями 2 u = f(x,y) внутри области u(x,y) = g(x,y) на границе области Для простоты обсуждения в качестве области задания функции используется единичный квадрат. Для численного решения применим широко используемый для таких задач метод конечных разностей. Для этого определим равномерную квадратную сетку (n+2)*(n+2), состоящую из точек (x i,y j ) x i = ih, i=0,...,n+1, y j = jh, j=0,...,n+1, h = 1/(n+1). Обозначим оцениваемую при подобном дискретном представлении аппроксимацию функции u(x,y) в точках (x i,y j ) через u i,j.

9 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Используя пятиточечный шаблон для аппроксимации значений вторых производных, можно получить разностную форму задачи Пуассона Полученные уравнения можно переписать в виде системы для решения которой может быть применен метод Якоби с итеративной формулой

10 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона…

11 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Serial Finite Difference Algorithm */ #const N 100 void main() { int i, j, k; double u[N+2][N+2], unew[N+2][N+2]; for ( k=0; k

12 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* основная итерация для пересчета значений в узлах сетки */ #define N 100 void sweep() { int i, j; double u[N+2][N+2], unew[N+2][N+2]]; for ( j=1; j

13 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Разделение области для параллельных расчетов – горизонтальные полосы

14 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* итерация метода Якоби для одной горизонтальной полосы */ #define M N/NPROC /* NPROC – общее к-во процессов */ int i, j; double u[M][N+2], unew[M][N+2]]; for ( j=1; j

15 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона…

16 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Схема обмена граничными значениями

17 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… void exchange1d( double a[][N+2], int nx, int m, MPI_Comm comm1d,int rank1, int rank2 ) { MPI_Status status; MPI_Sendrecv(&a[m][1], nx, MPI_DOUBLE, rank2, 0, &a[0][1], nx, MPI_DOUBLE, rank1, 0,comm1d, &status); MPI_Sendrecv(&a[1][1], nx, MPI_DOUBLE, rank1, 1, &a[m+1][1], nx, MPI_DOUBLE, rank2, 1, comm1d, &status); } где - nx – количество точек по одной размерности; - m – размер полосы области для процесса; - rank1 – номер ранга предшествующего процесса; - rank2 - номер ранга следующего процесса. ! Для организации обменом используется дополнительная функция MPI int MPI_Sendrecv(void *sendbuf, int sendcount, MPI_Datatype sendtype, int dest, int sendtag, void *recvbuf, int recvcount, MPI_Datatype recvtype, int source, int recvtag, MPI_Comm comm, MPI_Status *status);

18 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Основная итерация параллельн ог о метода Якоби */ void sweep1d( double a[][N+2], double f[][N+2], int nx, int m, double b[][N+2] ) { int i, j; double h = 1.0/(nx+1); for ( j=1; j

19 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* полная реализация параллельного метода Якоби */ #define N 100 void main(int argc, char *argv[]) { double a[N+2][N+2], b[N+2][N+2], f[N+2][N+2]; int nx, ny, m, myid, numprocs; integer rank1, rank2, it; double t1, t2, dwork, diffnorm; MPI_Comm comm1d; MPI_Init(argc,argv); MPI_Comm_rank( MPI_COMM_WORLD, &myid); MPI_Comm_Size( MPI_COMM_WORLD, &mumprocs);

20 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… if (myid==0) { /* ввод размера сетки */ printf("Введите размер сетки - "); scanf("%d",&nx); } MPI_Bcast(nx,1,MPI_INT,0,MPI_COMM_WORLD); ny = nx; /* Создание новой топологии */ int sizes[1], wrap[1]; sizes[0] = numprocs; wrap[0] = 0; MPI_Cart_create(MPI_COMM_WORLD, 1, sizes, wrap, 0, &comm1d);

21 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Получение рангов текущего процесса и рангов соседей */ MPI_Comm_rank( comm1d, &myid ); MPI_Cart_shift(comm1d, 0, 1, &rank1, &rank2); /* Определение размера полосы области */ m = GetStripSize(ny, numprocs, myid); /* Подготовка данных */ InitData( a, b, f, nx, m );

22 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* Выполнение вычислений */ MPI_Barrier(MPI_COMM_WORLD); t1 = MPI_Wtime(); for ( it=0; it

23 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… } if (myid==0) printf("Точность не достигнута\n"); } t2 = MPI_Wtime(); if (myid==0) { printf("Выполнено %d итераций, Время выполнения %lf сек.\n", 2*it,t2-t1); } MPI_Finalize(); }

24 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Коммуникационные операции, используемые в методе Якоби

25 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… Общая схема блочного разбиения области dims[0] = 4; dims[1] = 3; swap[0] = 0; swap[1] = 0; reorder = 1; MPI_Cart_create(MPI_COMM_WORLD, 2, dims, swap, reorder, &comm2d); /* получение рангов соседей */ MPI_Cart_shift(comm2d, 0, 1, &hrank1, &hrank2); MPI_Cart_shift(comm2d, 1, 1, &vrank1, &vrank2);

26 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* итерация метода Якоби при блочном разбиении области */ void sweep2d(double a[][N+2], double f[][N+2], int n, int mx, int my, double b[][N+2]) { int i, j; double h = 1.0 / (n+1); for ( i=1; i

27 Параллельные Гергель В.П. ННГУ, Н.Новгород, Пример: Решение задачи Пуассона… /* обмен данными при блочном разбиении данных */ void exchange2d( double a[][N+2], int mx, int my, MPI_Comm comm2d, MPI_Datatype stridetype, int hrank1, int hrank2, int vrank1, int vrank2 ) { MPI_Status status; /* пересылка по вертикали как и в предыдущем случае */ MPI_Sendrecv(&a[m][1], mx, MPI_DOUBLE, vrank2, 0, &a[0][1], mx, MPI_DOUBLE, vrank1, 0, comm2d, &status); MPI_Sendrecv(&a[1][1], mx, MPI_DOUBLE, vrank1, 1, &a[m+1][1], mx, MPI _ DOUBLE, vrank2, 1,comm2d, &status); /* по горизонтали используется тип blocktype */ MPI_Sendrecv(&a[1][mx], 1, blocktype, hrank2, 0, &a[1][0], 1, blocktype, hrank1, 0, comm2d, &status); MPI_Sendrecv(&a[1][1], 1, blocktype, hrank1, 1, &a[1][mx+1], 1, blocktype, hrank2, 1, comm2d, &status);

28 Параллельные Гергель В.П. ННГУ, Н.Новгород, Вопросы для обсуждения Полезность использования логической топологии типа решетки Анализ эффективности параллельных вычислений для решения задачи Пуассона

29 Параллельные Гергель В.П. ННГУ, Н.Новгород, Задания для самостоятельной работы Разработки параллельной программы для решения задачи Пуассона при блочном разбиении области вычислений Методы создания новых логических топологий в MPI

30 Параллельные Гергель В.П. ННГУ, Н.Новгород, Заключение Методы создания логической топологии типа решетки Пример параллельного решения сложной вычислительной задачи

31 Параллельные Гергель В.П. ННГУ, Н.Новгород, Следующая тема Модели функционирования параллельных программ