'

Курс: «DVM-технология разработки параллельных программ для вычислительных кластеров»

Понравилась презентация – покажи это...





Слайд 0

Курс: «DVM-технология разработки параллельных программ для вычислительных кластеров» Бахтин Владимир Александрович К.ф.-м.н., зав. сектором Института прикладной математики им М.В.Келдыша РАН Ассистент кафедры системного программирования факультета ВМК Московского государственного университета им. М.В. Ломоносова bakhtin@keldysh.ru


Слайд 1

Содержание Прошлое MPI – модель передачи сообщений DVM – модель параллелизма по данным и управлению. Язык Си-DVM Настоящее Многоядерные и многопоточные процессоры. SMP-кластеры Гибридная модель программирования MPI/OpenMP Язык Fortran-DVM/OpenMP Будущее Гибридные вычислительные кластеры PGI Accelerator Model Язык Fortran-DVM/OpenMP/Accelerator 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 2 из 83


Слайд 2

Алгоритм Якоби. Последовательная версия /* Jacobi program */ #include <stdio.h> #define L 1000 #define ITMAX 100 int i,j,it; double A[L][L]; double B[L][L]; int main(int an, char **as) { printf("JAC STARTED\n"); for(i=0;i<=L-1;i++) for(j=0;j<=L-1;j++) { A[i][j]=0.; B[i][j]=1.+i+j; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 3 из 83


Слайд 3

Алгоритм Якоби. Последовательная версия /****** iteration loop *************************/ for(it=1; it<ITMAX;it++) { for(i=1;i<=L-2;i++) for(j=1;j<=L-2;j++) A[i][j] = B[i][j]; for(i=1;i<=L-2;i++) for(j=1;j<=L-2;j++) B[i][j] = (A[i-1][j]+A[i+1][j]+A[i][j-1]+A[i][j+1])/4.; } return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 4 из 83


Слайд 4

Алгоритм Якоби. MPI-версия 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 5 из 83


Слайд 5

Алгоритм Якоби. MPI-версия /* Jacobi-1d program */ #include <math.h> #include <stdlib.h> #include <stdio.h> #include "mpi.h" #define m_printf if (myrank==0)printf #define L 1000 #define ITMAX 100 int i,j,it,k; int ll,shift; double (* A)[L]; double (* B)[L]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 6 из 83


Слайд 6

Алгоритм Якоби. MPI-версия int main(int argc, char **argv) { MPI_Request req[4]; int myrank, ranksize; int startrow,lastrow,nrow; MPI_Status status[4]; double t1, t2, time; MPI_Init (&argc, &argv); /* initialize MPI system */ MPI_Comm_rank(MPI_COMM_WORLD, &myrank);/*my place in MPI system*/ MPI_Comm_size (MPI_COMM_WORLD, &ranksize); /* size of MPI system */ MPI_Barrier(MPI_COMM_WORLD); /* rows of matrix I have to process */ startrow = (myrank *L) / ranksize; lastrow = (((myrank + 1) * L) / ranksize)-1; nrow = lastrow - startrow + 1; m_printf("JAC1 STARTED\n"); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 7 из 83


Слайд 7

Алгоритм Якоби. MPI-версия /* dynamically allocate data structures */ A = malloc ((nrow+2) * L * sizeof(double)); B = malloc ((nrow) * L * sizeof(double)); for(i=1; i<=nrow; i++) for(j=0; j<=L-1; j++) { A[i][j]=0.; B[i-1][j]=1.+startrow+i-1+j; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 8 из 83


Слайд 8

Алгоритм Якоби. MPI-версия /****** iteration loop *************************/ t1=MPI_Wtime(); for(it=1; it<=ITMAX; it++) { for(i=1; i<=nrow; i++) { if (((i==1)&&(myrank==0))||((i==nrow)&&(myrank==ranksize-1))) continue; for(j=1; j<=L-2; j++) { A[i][j] = B[i-1][j]; } } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 9 из 83


Слайд 9

Алгоритм Якоби. MPI-версия if(myrank!=0) MPI_Irecv(&A[0][0],L,MPI_DOUBLE, myrank-1, 1235, MPI_COMM_WORLD, &req[0]); if(myrank!=ranksize-1) MPI_Isend(&A[nrow][0],L,MPI_DOUBLE, myrank+1, 1235, MPI_COMM_WORLD,&req[2]); if(myrank!=ranksize-1) MPI_Irecv(&A[nrow+1][0],L,MPI_DOUBLE, myrank+1, 1236, MPI_COMM_WORLD, &req[3]); if(myrank!=0) MPI_Isend(&A[1][0],L,MPI_DOUBLE, myrank-1, 1236, MPI_COMM_WORLD,&req[1]); ll=4; shift=0; if (myrank==0) {ll=2;shift=2;} if (myrank==ranksize-1) {ll=2;} MPI_Waitall(ll,&req[shift],&status[0]); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 10 из 83


Слайд 10

Алгоритм Якоби. MPI-версия for(i=1; i<=nrow; i++) { if (((i==1)&&(myrank==0))||((i==nrow)&&(myrank==ranksize-1))) continue; for(j=1; j<=L-2; j++) B[i-1][j] = (A[i-1][j]+A[i+1][j]+ A[i][j-1]+A[i][j+1])/4.; } }/*DO it*/ printf("%d: Time of task=%lf\n",myrank,MPI_Wtime()-t1); MPI_Finalize (); return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 11 из 83


Слайд 11

Алгоритм Якоби. DVM-версия #include <stdio.h> #define L 1000 #define ITMAX 100 int i,j,it; #define DVM(dvmdir) #define DO(v,l,h,s) for(v=(l); v<=(h); v+=(s)) DVM(DISTRIBUTE [BLOCK][BLOCK]) double A[L][L]; DVM(ALIGN [i][j] WITH A[i][j]) double B[L][L]; int main(int an, char **as) { printf("JAC STARTED\n"); DVM(PARALLEL [i][j] ON A[i][j]) DO(i,0,L-1,1) DO(j,0,L-1,1) { A[i][j]=0.; B[i][j]=1.+i+j; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 12 из 83


Слайд 12

Алгоритм Якоби. DVM-версия /****** iteration loop *************************/ for(it=1; it<ITMAX;it++) { DVM(PARALLEL [i][j] ON A[i][j]) DO(i,1,L-2,1) DO(j,1,L-2,1) A[i][j] = B[i][j]; DVM(PARALLEL [i][j] ON B[i][j]; SHADOW_RENEW A) DO(i,1,L-2,1) DO(j,1,L-2,1) B[i][j] = (A[i-1][j]+A[i+1][j]+A[i][j-1]+A[i][j+1])/4.; } return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 13 из 83


Слайд 13

Модель параллелизма по данным и управлению. DVM Эта модель (1993 г.), положенная в основу языков параллельного программирования Фортран-DVM и Си-DVM, объединяет достоинства модели параллелизма по данным и модели параллелизма по управлению Базирующаяся на этих языках система разработки параллельных программ (DVM) создана в ИПМ им. М.В. Келдыша РАН Аббревиатура DVM (Distributed Virtual Memory, Distributed Virtual Machine) отражает поддержку виртуальной общей памяти на распределенных системах 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 14 из 83


Слайд 14

Модель программирования DVM на программиста возлагается ответственность за соблюдение правила собственных вычислений программист определяет общие (удаленные) данные, т.е. данные, вычисляемые на одних процессорах и используемые на других процессорах программист отмечает точки в последовательной программе, где происходит обновление значений общих данных программист распределяет по процессорам виртуальной параллельной машины не только данные, но и соответствующие вычисления 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 15 из 83


Слайд 15

Состав DVM-системы DVM-система состоит из следующих компонент: Компилятор Fortran-DVM/OpenMP Компилятор C-DVM Библиотека поддержки LIB-DVM DVM-отладчик Предсказатель выполнения DVM-программ Анализатор производительности DVM-программ 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 16 из 83


Слайд 16

Средства программирования C-DVM = Язык Си + специальные макросы Fortran-DVM/OpenMP = Язык Фортран 95 + специальные комментарии Специальные комментарии и макросы являются высокоуровневыми спецификациями параллелизма в терминах последовательной программы Отсутствуют низкоуровневые передачи данных и синхронизации Последовательный стиль программирования Спецификации параллелизма «невидимы» для стандартных компиляторов Существует только один экземпляр программы для последовательного и параллельного счета 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 17 из 83


Слайд 17

Массив виртуальных процессоров Массивы Массивы Циклы Массив задач Физические процессоры PARALLEL PARALLEL ALIGN DISTRIBUTE DISTRIBUTE MAP Отображение последовательной программы


Слайд 18

Распределение данных. DISTRIBUTE DVM( DISTRIBUTE f1…fk ) <описание-массива-на-языке-Си> где fi = [ BLOCK ] - распределение равными блоками (распределенное измерение) [MULT_BLOCK(m)] - распределение блоками кратными m (распределенное измерение) [GENBLOCK ( block-array-name )] - распределение блоками указанных размеров [WGTBLOCK ( block-array-name,nblock )] - распределение взвешенными блоками [ ] - распределение целым измерением (локальное измерение) k - количество измерений массива 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 19 из 83


Слайд 19

Распределение данных. DISTRIBUTE DVM(DISTRIBUTE [BLOCK]) double A[12]; DVM(DISTRIBUTE [BLOCK]) double B[6]; DVM(DISTRIBUTE [MULT_BLOCK(3)]) double A[12]; node1 node2 node3 node4 A 0,1,2 3,4,5 6,7,8 9,10,11 B 0,1 2,3 4 5 double wb[6]={1.,0.5,0.5,0.5,0.5,1.}; int bs[4]={2,4,4,2}; DVM(DISTRIBUTE [GEN_BLOCK(bs)]) double A[12]; DVM(DISTRIBUTE [WGT_BLOCK(wb,6)]) double B[6]; node1 node2 node3 node4 A 0,1 2,3,4,5 6,7,8,9 10,11 B 0 1,2 3,4 5 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 20 из 83


Слайд 20

Распределение данных. DISTRIBUTE DVM(DISTRIBUTE [BLOCK] [ ] [BLOCK]) float A[N][N][N]; … dvm run M1 M2 <имя-программы> /*P(M1,M2)*/ Директива распределяет первое измерение массива А на первое измерение P блоками размера N/M1, третье измерение А - на второе измерение P блоками размера N/M2, а второе измерение А будет целиком распределено на каждый виртуальный процессор. #define DVM(dvmdir) 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 21 из 83


Слайд 21

Распределение вычислений вне параллельных циклов Одна ОПМД-программа выполняется на всех процессорах с локальным подмножеством данных Правило собственных вычислений: OWN(A[i]) - процессор, на который распределен A[i] A[i] = expri Оператор всегда выполняется на процессоре OWN(A[i]) Проба: свой - “чужой” оператор по правилу собственных вычислений 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 22 из 83


Слайд 22

Локализация данных. ALIGN DVM(DISTRIBUTE B[BLOCK][BLOCK]) float B[N][M+1]; . . . for (i=0; i<N-1;i++) for(j=0; j<M-2; j++) { B[i][j+1] = A[i][j]; } DVM(ALIGN [i][j] WITH B[i][j+1]) float A[N][M]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 23 из 83


Слайд 23

Локализация данных. ALIGN DVM(ALIGN a1… an WITH B b1… bm ) <описание-массива-A-на-языке-Си> где ai - параметр i–го измерения выравниваемого массива А bj - параметр j–го измерения базового массива B n - количество измерений массива А m - количество измерений массива В ai =[ IDi ] bj =[ c*IDj+d ] =[ ] =[ ] где IDi , IDj - идентификаторы c, d - целочисленные константы 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 24 из 83


Слайд 24

Локализация данных. ALIGN DVM(ALIGN [i] WITH B[2*i+1] ) float A[N]; Распределить элемент A[ i ] и B[2*i+1] на один процессор. DVM(ALIGN [i][j] WITH B[j][i]) float A[N][N]; Распределить элемент A[ i ] [ j ] и B[ j ] [ i ] на один процессор. DVM(ALIGN [i] WITH B[][i]) float A[N]; Распределить элемент A[ i ] на те процессоры, где размещен хотя бы один элемент i-ого столбца B. DVM(ALIGN [i] [ ] WITH B[i]) float A[N][N]; Распределить i-ую строку A и элемент B[ i ] на один процессор, т.е. размножить второе измерение массива А. 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 25 из 83


Слайд 25

Распределение витков цикла. PARALLEL Заголовки параллельного цикла не должны разделяться другими операторами (тесно-гнездовой цикл); Параметры заголовков параллельного цикла не должны изменяться в процессе выполнения цикла (прямоугольное индексное пространство); Виток цикла должен быть неделимым объектом и выполняться на одном процессоре. Поэтому левые части операторов присваивания одного витка цикла должны быть распределены на один процессор (согласование с правилом собственных вычислений). 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 26 из 83


Слайд 26

Распределение витков цикла. PARALLEL FOR(i, N) { D[2*i] = …; D[2*i+1] = …; } DVM(PARALLEL [i] ON D[2*i]) FOR(i, N) { D[2*i] = …; } DVM(PARALLEL [i] ON D[2*i+1]) FOR(i, N) { D[2*i+1] = …; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 27 из 83


Слайд 27

Локализация данных. TEMPLATE DVM(PARALLEL [i] ON A[i]) FOR(i, N) { A[i] = B[i+d1] + C[i-d2]; } DVM(DISTRIBUTE [BLOCK]; TEMPLATE [N+d1+d2]) void *TABC; DVM( ALIGN [i] WITH TABC[i] ) float B[N]; DVM( ALIGN [i] WITH TABC[i+d2] ) float A[N]; DVM( ALIGN [i] WITH TABC[i+d1+d2] ) float C[N]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 28 из 83


Слайд 28

Удаленные данные типа SHADOW DVM(DISTRIBUTE [BLOCK]) float A[N]; DVM(PARALLEL [i] ON A[i]; SHADOW_RENEW B ) FOR(i, N) { A[i] = B[i+d1] + B[i-d2]; } DVM( ALIGN [i] WITH A[i]; SHADOW [d1:d2] ) float B[N]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 29 из 83


Слайд 29

Удаленные данные типа SHADOW DVM(DISTRIBUTE [BLOCK][BLOCK]) float C[100][100]; DVM(ALIGN[I][J] WITH C[I][J]) float A[100][100], B[100][100], D[100][100]; DVM(SHADOW_GROUP) void *AB; . . . DVM(CREATE_SHADOW_GROUP AB: A B); . . . DVM(SHADOW_START AB); . . . DVM(PARALLEL[I][J] ON C[I][J]; SHADOW_WAIT AB) DO( I, 1, 98, 1) DO( J, 1, 98, 1) { C[I][J] = (A[I-1][J]+A[I+1][J]+A[I][J-1]+A[I][J+1])/4.; D[I][J] = (B[I-1][J]+B[I+1][J]+B[I][J-1]+B[I][J+1])/4.; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 30 из 83


Слайд 30

Удаленные данные типа ACROSS DVM(DISTRIBUTE [BLOCK]; SHADOW [d1:d2] ) float A[N]; DVM(PARALLEL [i] ON A[i] ]; ACROSS A[d1:d2]) FOR(i, N) { A[i] = A[i+d1] + A[i-d2]; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 31 из 83


Слайд 31

Удаленные данные типа REMOTE DVM(DISTRIBUTE [BLOCK]) float A[N]; DVM(PARALLEL [i] ON A[i]; REMOTE_ACCESS C[5] C[i+n]) FOR(i, N) { A[i] = C[5] + C[i+n]; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 32 из 83


Слайд 32

Удаленные данные типа REMOTE DVM (DISTRIBUTE [BLOCK][BLOCK]) float A1[M][N1+1], A2[M1+1][[N2+1], A3[M2+1][N2+1]; DVM (REMOTE_GROUP) void *RS; DO(ITER,1, MIT,1) { . . . DVM (PREFETCH RS); . . . DVM ( PARALLEL[i] ON A1[i][N1]; REMOTE_ACCESS RS: A2[i][1]) DO(i,0, M1-1,1) A1[i][N1] = A2[i][1]; DVM (PARALLEL[i] ON A1[i][N1]; REMOTE_ACCESS RS: A3[i-M1][1]) DO(i,M1, M-1,1) A1[i][N1] = A3[i-M1][1]; DVM (PARALLEL[i] ON A2[i][0]; REMOTE_ACCESS RS: A1[I][N1-1]) DO(i,0, M1-1,1) A2[i][0] = A1[i][N1-1]; DVM(PARALLEL[i] ON A3[i][0]; REMOTE_ACCESS RS: A1[I+M1][N1-1]) DO (i,0, M2-1,1) A3[i][0] = A1[i+M1][N1-1]; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 33 из 83


Слайд 33

Удаленные данные типа REDUCTION DVM(DISTRIBUTE [BLOCK]) float A[N]; DVM(PARALLEL [i] ON A[i] ; REDUCTION SUM(S) ) FOR(i, N) { A[i] = B[i] + C[i]; s = s + A[i]; } DVM( ALIGN [i] WITH A[i]) float B[N]; DVM( ALIGN [i] WITH A[i]) float C[N]; К редукционным операторам относятся: SUM, PRODUCT, AND, OR, MAX, MIN, MAXLOC, MINLOC 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 34 из 83


Слайд 34

Удаленные данные типа REDUCTION DVM(REDUCTION_GROUP) void *RG; S = 0; X = A[1]; Y = A[1]; MINI = 1; DVM(PARALLEL[I] ON A[I]; REDUCTION RG: SUM(S), MAX(X), MINLOC(Y,MIMI)) FOR(I, N) { S = S + A[I]; X =max(X, A[I]); if(A[I] < Y) { Y = A[I]; MINI = I; } } DVM(REDUCTION_START RG); DVM(PARALLEL[I] ON B[I]) FOR( I, N) B[I] = C[I] + A[I]; DVM(REDUCTION_WAIT RG); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 35 из 83


Слайд 35

Копирование секций массивов DVM(DISTRIBUTE [BLOCK][]) float A[N][N]; DVM(ALIGN [i][j] WITH [j][i]) float B[N][N]; . . . DVM(COPY) FOR(i,N) FOR(j,N) B[i][j]=A[i][j]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 36 из 83


Слайд 36

Копирование секций массивов DVM(DISTRIBUTE [BLOCK][]) float A[N][N]; DVM(ALIGN [i][j] WITH [j][i]) float B[N][N]; . . . DVM(COPY_FLAG) void * flag; . . . DVM(COPY_START &flag) FOR(i,N) FOR(j,N) B[i][j]=A[i][j]; . . . DVM(COPY_WAIT &flag); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 37 из 83


Слайд 37

Гибридная модель MPI/OpenMP Данные Данные Вычисления … Узел N OpenMP Вычисления MPI 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 38 из 83


Слайд 38

Многоядерные и многопоточные процессоры Процессоры Intel® Xeon® серии 5000 Процессоры Intel® Xeon® серии 7000 Процессоры AMD Opteron серии 4100 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 39 из 83


Слайд 39

Достоинства использования в узлах OpenMP вместо MPI Возможность инкрементального распараллеливания. Упрощение программирования и эффективность на нерегулярных вычислениях, проводимых над общими данными. Ликвидация или сокращение дублирования данных в памяти, свойственного MPI-программам. Дополнительный уровень параллелизма на OpenMP реализовать проще, чем на MPI. 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 40 из 83


Слайд 40

Преимущества OpenMP для многоядерных процессоров Объемы оперативной памяти и кэш памяти, приходящиеся в среднем на одно ядро, будут сокращаться – присущая OpenMP экономия памяти становится очень важна. Ядра используют общую Кэш-память, что требуется учитывать при оптимизации программы. 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 41 из 83


Слайд 41

National Institute for Computational Sciences. University of Tennessee Суперкомпьютер Kraken Cray XT5-HE Opteron Six Core 2.6 GHz 4 место в TOP 500 http://nics.tennessee.edu Пиковая производительность - 1028.85 TFlop/s Число процессоров/ядер в системе — 16 288 / 98 928 Производительность на Linpack - 831.7 TFlop/s (81% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 6-ое место в TOP500 в июне 2009 - 3-ье место в TOP500 в ноябре 2009 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 42 из 83


Слайд 42

National Institute for Computational Sciences. University of Tennessee 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 43 из 83


Слайд 43

Межведомственный Суперкомпьютерный Центр Российской Академии Наук Суперкомпьютер MVS-100K 46 место в TOP 500 http://www.jscc.ru/ Пиковая производительность - 140.16 TFlop/s Число процессоров/ядер в системе — 2 920/11 680 Производительность на Linpack - 107.45 TFlop/s (76.7% от пиковой) Updrage: замена 2-х ядерных процессоров Intel Xeon 53xx на 4-х ядерные процессоры Intel Xeon 54xx Результат: 57-ое место в TOP500 в июне 2008 - 36-ое место в TOP500 в ноябре 2008 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 44 из 83


Слайд 44

Oak Ridge National Laboratory Суперкомпьютер Jaguar Cray XT5-HE Opteron Six Core 2.6 GHz 1 место в TOP 500 http://computing.ornl.gov Пиковая производительность - 2331 TFlop/s Число ядер в системе — 224 162 Производительность на Linpack - 1759 TFlop/s (75.4% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 2-ое место в TOP500 в июне 2009 - 1-ое место в TOP500 в ноябре 2009 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 45 из 83


Слайд 45

Oak Ridge National Laboratory Jaguar Scheduling Policy 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 46 из 83


Слайд 46

Cray MPI: параметры по умолчанию 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 47 из 83


Слайд 47

Алгоритм Якоби. Последовательная версия /* Jacobi program */ #include <stdio.h> #define L 1000 #define ITMAX 100 int i,j,it; double A[L][L]; double B[L][L]; int main(int an, char **as) { printf("JAC STARTED\n"); for(i=0;i<=L-1;i++) for(j=0;j<=L-1;j++) { A[i][j]=0.; B[i][j]=1.+i+j; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 48 из 83


Слайд 48

Алгоритм Якоби. Последовательная версия /****** iteration loop *************************/ for(it=1; it<ITMAX;it++) { for(i=1;i<=L-2;i++) for(j=1;j<=L-2;j++) A[i][j] = B[i][j]; for(i=1;i<=L-2;i++) for(j=1;j<=L-2;j++) B[i][j] = (A[i-1][j]+A[i+1][j]+A[i][j-1]+A[i][j+1])/4.; } return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 49 из 83


Слайд 49

Алгоритм Якоби. MPI-версия 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 50 из 83


Слайд 50

Алгоритм Якоби. MPI-версия /* Jacobi-1d program */ #include <math.h> #include <stdlib.h> #include <stdio.h> #include "mpi.h" #define m_printf if (myrank==0)printf #define L 1000 #define ITMAX 100 int i,j,it,k; int ll,shift; double (* A)[L]; double (* B)[L]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 51 из 83


Слайд 51

Алгоритм Якоби. MPI-версия int main(int argc, char **argv) { MPI_Request req[4]; int myrank, ranksize; int startrow,lastrow,nrow; MPI_Status status[4]; double t1, t2, time; MPI_Init (&argc, &argv); /* initialize MPI system */ MPI_Comm_rank(MPI_COMM_WORLD, &myrank);/*my place in MPI system*/ MPI_Comm_size (MPI_COMM_WORLD, &ranksize); /* size of MPI system */ MPI_Barrier(MPI_COMM_WORLD); /* rows of matrix I have to process */ startrow = (myrank *L) / ranksize; lastrow = (((myrank + 1) * L) / ranksize)-1; nrow = lastrow - startrow + 1; m_printf("JAC1 STARTED\n"); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 52 из 83


Слайд 52

Алгоритм Якоби. MPI-версия /* dynamically allocate data structures */ A = malloc ((nrow+2) * L * sizeof(double)); B = malloc ((nrow) * L * sizeof(double)); for(i=1; i<=nrow; i++) for(j=0; j<=L-1; j++) { A[i][j]=0.; B[i-1][j]=1.+startrow+i-1+j; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 53 из 83


Слайд 53

Алгоритм Якоби. MPI-версия /****** iteration loop *************************/ t1=MPI_Wtime(); for(it=1; it<=ITMAX; it++) { for(i=1; i<=nrow; i++) { if (((i==1)&&(myrank==0))||((i==nrow)&&(myrank==ranksize-1))) continue; for(j=1; j<=L-2; j++) { A[i][j] = B[i-1][j]; } } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 54 из 83


Слайд 54

Алгоритм Якоби. MPI-версия if(myrank!=0) MPI_Irecv(&A[0][0],L,MPI_DOUBLE, myrank-1, 1235, MPI_COMM_WORLD, &req[0]); if(myrank!=ranksize-1) MPI_Isend(&A[nrow][0],L,MPI_DOUBLE, myrank+1, 1235, MPI_COMM_WORLD,&req[2]); if(myrank!=ranksize-1) MPI_Irecv(&A[nrow+1][0],L,MPI_DOUBLE, myrank+1, 1236, MPI_COMM_WORLD, &req[3]); if(myrank!=0) MPI_Isend(&A[1][0],L,MPI_DOUBLE, myrank-1, 1236, MPI_COMM_WORLD,&req[1]); ll=4; shift=0; if (myrank==0) {ll=2;shift=2;} if (myrank==ranksize-1) {ll=2;} MPI_Waitall(ll,&req[shift],&status[0]); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 55 из 83


Слайд 55

Алгоритм Якоби. MPI-версия for(i=1; i<=nrow; i++) { if (((i==1)&&(myrank==0))||((i==nrow)&&(myrank==ranksize-1))) continue; for(j=1; j<=L-2; j++) B[i-1][j] = (A[i-1][j]+A[i+1][j]+ A[i][j-1]+A[i][j+1])/4.; } }/*DO it*/ printf("%d: Time of task=%lf\n",myrank,MPI_Wtime()-t1); MPI_Finalize (); return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 56 из 83


Слайд 56

Алгоритм Якоби. MPI-версия 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 57 из 83


Слайд 57

Алгоритм Якоби. MPI-версия /*Jacobi-2d program */ #include <math.h> #include <stdlib.h> #include <stdio.h> #include "mpi.h" #define m_printf if (myrank==0)printf #define L 1000 #define LC 2 #define ITMAX 100 int i,j,it,k; double (* A)[L/LC+2]; double (* B)[L/LC]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 58 из 83


Слайд 58

Алгоритм Якоби. MPI-версия int main(int argc, char **argv) { MPI_Request req[8]; int myrank, ranksize; int srow,lrow,nrow,scol,lcol,ncol; MPI_Status status[8]; double t1; int isper[] = {0,0}; int dim[2]; int coords[2]; MPI_Comm newcomm; MPI_Datatype vectype; int pleft,pright, pdown,pup; MPI_Init (&argc, &argv); /* initialize MPI system */ MPI_Comm_size (MPI_COMM_WORLD, &ranksize); /* size of MPI system */ MPI_Comm_rank (MPI_COMM_WORLD, &myrank); /* my place in MPI system */ 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 59 из 83


Слайд 59

Алгоритм Якоби. MPI-версия dim[0]=ranksize/LC; dim[1]=LC; if ((L%dim[0])||(L%dim[1])) { m_printf("ERROR: array[%d*%d] is not distributed on %d*%d processors\n",L,L,dim[0],dim[1]); MPI_Finalize(); exit(1); } MPI_Cart_create(MPI_COMM_WORLD,2,dim,isper,1,&newcomm); MPI_Cart_shift(newcomm,0,1,&pup,&pdown); MPI_Cart_shift(newcomm,1,1,&pleft,&pright); MPI_Comm_rank (newcomm, &myrank); /* my place in MPI system */ MPI_Cart_coords(newcomm,myrank,2,coords); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 60 из 83


Слайд 60

Алгоритм Якоби. MPI-версия /* rows of matrix I have to process */ srow = (coords[0] * L) / dim[0]; lrow = (((coords[0] + 1) * L) / dim[0])-1; nrow = lrow - srow + 1; /* columns of matrix I have to process */ scol = (coords[1] * L) / dim[1]; lcol = (((coords[1] + 1) * L) / dim[1])-1; ncol = lcol - scol + 1; MPI_Type_vector(nrow,1,ncol+2,MPI_DOUBLE,&vectype); MPI_Type_commit(&vectype); m_printf("JAC2 STARTED on %d*%d processors with %d*%d array, it=%d\n",dim[0],dim[1],L,L,ITMAX); /* dynamically allocate data structures */ A = malloc ((nrow+2) * (ncol+2) * sizeof(double)); B = malloc (nrow * ncol * sizeof(double)); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 61 из 83


Слайд 61

Алгоритм Якоби. MPI-версия for(i=0; i<=nrow-1; i++) { for(j=0; j<=ncol-1; j++) { A[i+1][j+1]=0.; B[i][j]=1.+srow+i+scol+j; } } /****** iteration loop *************************/ MPI_Barrier(newcomm); t1=MPI_Wtime(); for(it=1; it<=ITMAX; it++) { for(i=0; i<=nrow-1; i++) { if (((i==0)&&(pup==MPI_PROC_NULL))||((i==nrow-1)&&(pdown==MPI_PROC_NULL))) continue; for(j=0; j<=ncol-1; j++) { if (((j==0)&&(pleft==MPI_PROC_NULL))||((j==ncol-1)&&(pright==MPI_PROC_NULL))) continue; A[i+1][j+1] = B[i][j]; } } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 62 из 83


Слайд 62

Алгоритм Якоби. MPI-версия MPI_Irecv(&A[0][1],ncol,MPI_DOUBLE, pup, 1235, MPI_COMM_WORLD, &req[0]); MPI_Isend(&A[nrow][1],ncol,MPI_DOUBLE, pdown, 1235, MPI_COMM_WORLD,&req[1]); MPI_Irecv(&A[nrow+1][1],ncol,MPI_DOUBLE, pdown, 1236, MPI_COMM_WORLD, &req[2]); MPI_Isend(&A[1][1],ncol,MPI_DOUBLE, pup, 1236, MPI_COMM_WORLD,&req[3]); MPI_Irecv(&A[1][0],1,vectype, pleft, 1237, MPI_COMM_WORLD, &req[4]); MPI_Isend(&A[1][ncol],1,vectype, pright, 1237, MPI_COMM_WORLD,&req[5]); MPI_Irecv(&A[1][ncol+1],1,vectype, pright, 1238, MPI_COMM_WORLD, &req[6]); MPI_Isend(&A[1][1],1,vectype, pleft, 1238, MPI_COMM_WORLD,&req[7]); MPI_Waitall(8,req,status); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 63 из 83


Слайд 63

Алгоритм Якоби. MPI-версия for(i=1; i<=nrow; i++) { if (((i==1)&&(pup==MPI_PROC_NULL))|| ((i==nrow)&&(pdown==MPI_PROC_NULL))) continue; for(j=1; j<=ncol; j++) { if (((j==1)&&(pleft==MPI_PROC_NULL))|| ((j==ncol)&&(pright==MPI_PROC_NULL))) continue; B[i-1][j-1] = (A[i-1][j]+A[i+1][j]+A[i][j-1]+A[i][j+1])/4.; } } } printf("%d: Time of task=%lf\n",myrank,MPI_Wtime()-t1); MPI_Finalize (); return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 64 из 83


Слайд 64

Алгоритм Якоби. MPI/OpenMP-версия /****** iteration loop *************************/ t1=MPI_Wtime(); #pragma omp parallel default(none) private(it,i,j) shared (A,B,myrank, nrow,ranksize,ll,shift,req,status) for(it=1; it<=ITMAX; it++) { for(i=1; i<=nrow; i++) { if (((i==1)&&(myrank==0))||((i==nrow)&&(myrank==ranksize-1))) continue; #pragma omp for nowait for(j=1; j<=L-2; j++) { A[i][j] = B[i-1][j]; } } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 65 из 83


Слайд 65

Алгоритм Якоби. MPI/OpenMP-версия #pragma omp barrier #pragma omp single { if(myrank!=0) MPI_Irecv(&A[0][0],L,MPI_DOUBLE, myrank-1, 1235, MPI_COMM_WORLD, &req[0]); if(myrank!=ranksize-1) MPI_Isend(&A[nrow][0],L,MPI_DOUBLE, myrank+1, 1235, MPI_COMM_WORLD,&req[2]); if(myrank!=ranksize-1) MPI_Irecv(&A[nrow+1][0],L,MPI_DOUBLE, myrank+1, 1236, MPI_COMM_WORLD, &req[3]); if(myrank!=0) MPI_Isend(&A[1][0],L,MPI_DOUBLE, myrank-1, 1236, MPI_COMM_WORLD,&req[1]); ll=4; shift=0; if (myrank==0) {ll=2;shift=2;} if (myrank==ranksize-1) {ll=2;} MPI_Waitall(ll,&req[shift],&status[0]); } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 66 из 83


Слайд 66

Алгоритм Якоби. MPI/OpenMP-версия for(i=1; i<=nrow; i++) { if (((i==1)&&(myrank==0))||((i==nrow)&&(myrank==ranksize-1))) continue; #pragma omp for nowait for(j=1; j<=L-2; j++) B[i-1][j] = (A[i-1][j]+A[i+1][j]+ A[i][j-1]+A[i][j+1])/4.; } }/*DO it*/ printf("%d: Time of task=%lf\n",myrank,MPI_Wtime()-t1); MPI_Finalize (); return 0; } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 67 из 83


Слайд 67

Гибридная модель DVM/OpenMP Данные Данные Вычисления … Узел N OpenMP DVM DVM 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 68 из 83


Слайд 68

Алгоритм Якоби. DVM/OpenMP-версия PROGRAM JAC_OpenMP_DVM PARAMETER (L=1000, ITMAX=100) REAL A(L,L), B(L,L) CDVM$ DISTRIBUTE ( BLOCK, BLOCK) :: A CDVM$ ALIGN B(I,J) WITH A(I,J) PRINT *, '********** TEST_JACOBI **********' C$OMP PARALLEL DEFAULT(NONE ) SHARED(A,B) PRIVATE(IT,I,J) DO IT = 1, ITMAX CDVM$ PARALLEL (J,I) ON A(I, J) DO J = 2, L-1 C$OMP DO DO I = 2, L-1 A(I, J) = B(I, J) ENDDO C$OMP ENDDO NOWAIT ENDDO 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 69 из 83


Слайд 69

Алгоритм Якоби. DVM/OpenMP-версия C$OMP BARRIER CDVM$ PARALLEL (J,I) ON B(I, J), SHADOW_RENEW (A) DO J = 2, L-1 C$OMP DO DO I = 2, L-1 B(I, J) = (A(I-1, J) + A(I, J-1) + A(I+1, J) + A(I, J+1)) / 4 ENDDO C$OMP ENDDO NOWAIT ENDDO ENDDO C$OMP END PARALLEL END 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 70 из 83


Слайд 70

Тесты NASA MultiZone BT (Block Tridiagonal Solver) 3D Навье-Стокс, метод переменных направлений LU (Lower-Upper Solver) 3D Навье-Стокс, метод верхней релаксации SP (Scalar PentadiagonalSolver) 3D Навье-Стокс, Beam-Warning approximate factorization http://www.nas.nasa.gov/News/Techreports/2003/PDF/nas-03-010.pdf 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 71 из 83


Слайд 71

Тесты NASA MultiZone 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 72 из 83


Слайд 72

Тест SP-MZ (класс A) на IBM eServer pSeries 690 Regatta DVM MPI 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 73 из 83


Слайд 73

Тест LU-MZ (класс A) на IBM eServer pSeries 690 Regatta DVM MPI 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 74 из 83


Слайд 74

Тест BT-MZ (класс A) на IBM eServer pSeries 690 Regatta зоны от 13 x 13 x 16 и до 58 x 58 x 16 DVM MPI 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 75 из 83


Слайд 75

Ликвидация или сокращение дублирования данных в памяти узла. Дополнительный уровень параллелизма на OpenMP реализовать проще, чем на MPI (например, когда в программе есть два уровня параллелизма – параллелизм между подзадачами и параллелизм внутри подзадачи). Улучшение балансировки на многоблочных задачах при меньшей трудоемкости реализации еще одного уровня параллелизма. Преимущества гибридной модели MPI/OpenMP 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 76 из 83


Слайд 76

Близость моделей OpenMP и DVM, что упрощает их совместное использование. Получение гибких программ, способных настраиваться на неоднородность узлов SMP-кластера. Возможность использования параллельной программы как последовательной, как OpenMP-программы, как DVM-программы, и как DVM/OpenMP -программы. Преимущества гибридной модели DVM/OpenMP 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 77 из 83


Слайд 77

Гибридная вычислительная система – это параллельная вычислительная система, в которой, наряду с универсальными процессорами, используются различные типы ускорителей, или сопроцессоров, обладающих нестандартной архитектурой (векторной, мультитредовой, реконфигурируемой под конкретную задачу и т. п.). В идеале должна снабжаться также нестандартной, усиленной системой межузловых коммуникаций. Гибридные вычислительные системы 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 78 из 83


Слайд 78

Вычислительный комплекс “МВС-эспресс” 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 79 из 83


Слайд 79

!$acc data region copy(a(1:n,1:m)) local(b(2:n-1,2:m-1)) copyin(w(2:n-1)) do while(resid .gt. tol) resid = 0.0 !$acc region do i = 2, n-1 do j = 2, m-1 b(i,j) = 0.25*w(i)*(a(i-1,j)+a(i,j-1)+ & a(i+1,j)+a(i,j+1)) & +(1.0-w(i))*a(i,j) enddo enddo Модель PGI Accelerator для Fortran и Си 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 80 из 83


Слайд 80

do i = 2, n-1 do j = 2, m-1 resid = resid + (b(i,j)-a(i,j))**2 a(i,j) = b(i,j) enddo enddo !$acc end region enddo !$acc end data region http://www.pgroup.com/lit/whitepapers/pgi_accel_prog_model_1.2.pdf Модель PGI Accelerator для Fortran и Си 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 81 из 83


Слайд 81

OpenMP Application Program Interface Version 3.0, May 2008. http://www.openmp.org/mp-documents/spec30.pdf MPI: A Message-Passing Interface Standard Version 2.2, September 2009. http://www.mpi-forum.org/docs/mpi-2.2/mpi22-report.pdf Параллельное программирование на языке C-DVM. Методическое пособие по практикуму для студентов 2-4 курсов. МГУ им. М.В.Ломоносова. Факультет ВMиК. Москва, 2002 г. ftp://ftp.keldysh.ru/K_student/DVM-practicum/method_CDVM_2006.doc Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.-М.: Изд-во МГУ, 2009. http://parallel.ru/info/parallel/openmp/OpenMP.pdf Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие.-М.: Изд-во МГУ, 2004. http://parallel.ru/tech/tech_dev/MPI/mpibook.pdf Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. Литература 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 82 из 83


Слайд 82

Вопросы? 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 83 из 83


×

HTML:





Ссылка: