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

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

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. Последовательная версия /* Jacobi program */ #include #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

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. Последовательная версия /****** iteration loop *************************/ for(it=1; it

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 5 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /* Jacobi-1d program */ #include #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]; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 6 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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"); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 7 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /* dynamically allocate data structures */ A = malloc ((nrow+2) * L * sizeof(double)); B = malloc ((nrow) * L * sizeof(double)); for(i=1; i

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /****** iteration loop *************************/ t1=MPI_Wtime(); for(it=1; it

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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]); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 10 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия for(i=1; i

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. DVM-версия #include #define L 1000 #define ITMAX 100 int i,j,it; #define DVM(dvmdir) #define DO(v,l,h,s) for(v=(l); v

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. DVM-версия /****** iteration loop *************************/ for(it=1; it

Параллельное программирование для высокопроизводительных вычислительных систем Тесты NAS 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 14 из 95 ТестХарактеристика тестаSEQMPIDVM MPI/ SEQ DVM/S EQ BT 3D Навье-Стокс, метод переменных направлений CG Оценка наибольшего собственного значения симметричной разреженной матрицы EP Генерация пар случайных чисел Гаусса FT Быстрое преобразование Фурье, 3D спектральный метод IS Параллельная сортировка LU 3D Навье-Стокс, метод верхней релаксации MG 3D уравнение Пуассона, метод Multigrid SP 3D Навье-Стокс, Beam-Warning approximate factorization

Параллельное программирование для высокопроизводительных вычислительных систем Тесты NAS 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 15 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Тесты NAS 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 16 из 95

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

Параллельное программирование для высокопроизводительных вычислительных систем Модель программирования DVM на программиста возлагается ответственность за соблюдение правила собственных вычислений программист определяет общие (удаленные) данные, т.е. данные, вычисляемые на одних процессорах и используемые на других процессорах программист отмечает точки в последовательной программе, где происходит обновление значений общих данных программист распределяет по процессорам виртуальной параллельной машины не только данные, но и соответствующие вычисления 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 18 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Состав DVM-системы DVM-система состоит из следующих компонент: Компилятор Fortran-DVM/OpenMP Компилятор C-DVM Библиотека поддержки LIB-DVM DVM-отладчик Предсказатель выполнения DVM-программ Анализатор производительности DVM-программ 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 19 из 95

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

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

Параллельное программирование для высокопроизводительных вычислительных систем Распределение данных. DISTRIBUTE DVM( DISTRIBUTE f1…fk ) где fi = [ BLOCK ] - распределение равными блоками (распределенное измерение) [MULT_BLOCK(m)] - распределение блоками кратными m (распределенное измерение) [GENBLOCK ( block-array-name )] - распределение блоками указанных размеров [WGTBLOCK ( block-array-name,nblock )] - распределение взвешенными блоками [ ] - распределение целым измерением (локальное измерение) k - количество измерений массива 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 22 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Распределение данных. 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, февраля Москва, 2011 DVM-технология разработки параллельных программ 23 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Распределение данных. 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) 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 24 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Распределение вычислений вне параллельных циклов Одна ОПМД-программа выполняется на всех процессорах с локальным подмножеством данных Правило собственных вычислений: OWN(A[i]) - процессор, на который распределен A[i] A[i] = expr i Оператор всегда выполняется на процессоре OWN(A[i]) Проба: свой - чужой оператор по правилу собственных вычислений 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 25 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Локализация данных. ALIGN DVM(DISTRIBUTE B[BLOCK][BLOCK]) float B[N][M+1];... for (i=0; i

Параллельное программирование для высокопроизводительных вычислительных систем Локализация данных. ALIGN DVM(ALIGN a1… an WITH B b1… bm ) гдеai - параметр i–го измерения выравниваемого массива А bj - параметр j–го измерения базового массива B n- количество измерений массива А m- количество измерений массива В ai =[ IDi ]bj =[ c*IDj+d ] =[ ] =[ ] гдеIDi, IDj- идентификаторы c, d- целочисленные константы 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 27 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Локализация данных. 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 ] на один процессор, т.е. размножить второе измерение массива А. 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 28 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Распределение витков цикла. PARALLEL Заголовки параллельного цикла не должны разделяться другими операторами (тесно-гнездовой цикл); Параметры заголовков параллельного цикла не должны изменяться в процессе выполнения цикла (прямоугольное индексное пространство); Виток цикла должен быть неделимым объектом и выполняться на одном процессоре. Поэтому левые части операторов присваивания одного витка цикла должны быть распределены на один процессор (согласование с правилом собственных вычислений). 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 29 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Распределение витков цикла. 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] = …; } 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 30 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Локализация данных. 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]; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 31 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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]; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 32 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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.; } 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 33 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Циклы с зависимостью по данным for(i = 1; i < 100; i++) a[i]= a[i-1] + a[i+1] Между витками цикла с индексами i1 и i2 ( i1 i2. Если виток i1 читает старое значение, а виток i2 записывает новое значение, то между этими витками существует обратная зависимость i1

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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]; } 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 35 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Макроконвейерный параллелизм DVM(DISTRIBUTE [BLOCK][BLOCK]) float A[N][N]; … DVM(PARALLEL [i][j] ON A[i][j]; ACROSS A[1:1][1:1]) DO(i, 1, N-2, 1) DO(j, 1, N-2, 1) A[i][j]=(A[i][j-1]+A[i][j+1]+A[i-1][j]+A[i+1][j])/4.; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 36 из 38

Параллельное программирование для высокопроизводительных вычислительных систем j i t1 t2 t3 Параллелизм по гиперплоскостям dvm run 4 4 sor 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 37 из 38

Параллельное программирование для высокопроизводительных вычислительных систем p0 p1 p2 j i t1 t2 t2t2 t3 t3t3 t3t3 t4t4 t4t4 t4t4 t5t5 t5t5 t5t5 t6t6 t6t6 t6t6 t7t7 t7t7 t7t7 t8t8 t8t8 t9t9 Конвейерный параллелизм dvm run 3 1 sor 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 38 из 38

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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]; } 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 39 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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]; } 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 40 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 41 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Удаленные данные типа 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); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 42 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Копирование секций массивов 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]; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 43 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Копирование секций массивов 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); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 44 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Параллелизм задач 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 45 из 95 Макет многоблочной задачи (multiblock) Описание количества блоков (сеток) DVM(TASK) void *MB[n]; Запрос количества процессоров, на которых выполняется задача NP = NUMBER_OF_PROCESSORS ( ) Разделение процессоров на группы G = { G 1, …, G n }

Параллельное программирование для высокопроизводительных вычислительных систем Макет многоблочной задачи (multiblock) 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 46 из 95 DVM(DISTRIBUTE) float (*A1)[N1+1],(*A2)[N2+1],(*A3)[N2+1]; DVM(ALIGN) float (*B1)[N1+1], (*B2)[N2+1], (*B3)[N2+1]; DVM(PROCESSORS) void *P[NUMBER_OF_PROCESSORS()];

Параллельное программирование для высокопроизводительных вычислительных систем Макет многоблочной задачи (multiblock) 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 47 из 95 Отображение блоков NP = NUMBER_OF_PROCESSORS()/3; DVM(MAP MB[1] ONTO P(0: NP-1)); DVM(MAP MB[2] ONTO P( NP : 2*NP-1)); DVM(MAP MB[3] ONTO P(2*NP : 3*NP-1));

Параллельное программирование для высокопроизводительных вычислительных систем Макет многоблочной задачи (multiblock) 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 48 из 95 Локализация данных A1=malloc(M*(N1+1)*sizeof(float)); DVM(REDISTRIBUTE A1[][BLOCK] ONTO MB[1]); B1=malloc(M*(N1+1)*sizeof(float)); DVM(REALIGN B1[i][j] WITH A1[i][j]); A2=malloc((M1+1)*(N2+1)*sizeof(float)); DVM(REDISTRIBUTE A2[][BLOCK] ONTO MB[2]); B2=malloc((M1+1)*(N2+1)*sizeof(float)); DVM(REALIGN B2[i][j] WITH A2[i][j]); A3=malloc((M1+1)*(N2+1)*sizeof(float)); DVM(REDISTRIBUTE A3[][BLOCK] ONTO MB[3]); B3=malloc((M1+1)*(N2+1)*sizeof(float)); DVM(REALIGN B3[i][j] WITH A3[i][j]);

Параллельное программирование для высокопроизводительных вычислительных систем Макет многоблочной задачи (multiblock) 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 49 из 95 Распределение вычислений FOR(IT,MAXIT) { DVM(TASK_REGION MB) { DVM(ON MB[1]) JACOBY(A1, B1, M, N1+1);5 DVM(ON MB[2]) JACOBY(A2, B2, M1+1, N2+1); DVM(ON MB[3]) JACOBY(A3, B3, M2+1, N2+1); } /* TASK_REGION */ } /* FOR */

Параллельное программирование для высокопроизводительных вычислительных систем Гибридная модель MPI/OpenMP Данные Core Данные Вычисления Core … Узел 0 OpenMP Core Данные Вычисления Core … Узел N OpenMP Вычисления MPI 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 50 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Многоядерные и многопоточные процессоры Процессоры Intel® Xeon® серии KX HE 6 cores 41QS HE 4 cores 2200 MHz2500 MHz Процессоры Intel® Xeon® серии 7000 Процессоры AMD Opteron серии 4100 X cores X cores 3330 MHz3460 MHz X cores X cores 2226 MHz2666 MHz 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 51 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Достоинства использования в узлах OpenMP вместо MPI Возможность инкрементального распараллеливания. Упрощение программирования и эффективность на нерегулярных вычислениях, проводимых над общими данными. Ликвидация или сокращение дублирования данных в памяти, свойственного MPI-программам. Дополнительный уровень параллелизма на OpenMP реализовать проще, чем на MPI. 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 52 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Преимущества OpenMP для многоядерных процессоров Объемы оперативной памяти и кэш памяти, приходящиеся в среднем на одно ядро, будут сокращаться – присущая OpenMP экономия памяти становится очень важна. Ядра используют общую Кэш-память, что требуется учитывать при оптимизации программы. 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 53 из 95

Параллельное программирование для высокопроизводительных вычислительных систем National Institute for Computational Sciences. University of Tennessee Суперкомпьютер Kraken Cray XT5-HE Opteron Six Core 2.6 GHz 4 место в TOP Пиковая производительность TFlop/s Число процессоров/ядер в системе / Производительность на Linpack TFlop/s (81% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 6-ое место в TOP500 в июне ье место в TOP500 в ноябре февраля Москва, 2011 DVM-технология разработки параллельных программ 54 из 95

Параллельное программирование для высокопроизводительных вычислительных систем National Institute for Computational Sciences. University of Tennessee 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 55 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Межведомственный Суперкомпьютерный Центр Российской Академии Наук Суперкомпьютер MVS-100K 46 место в TOP Пиковая производительность TFlop/s Число процессоров/ядер в системе 2 920/ Производительность на Linpack TFlop/s (76.7% от пиковой) Updrage: замена 2-х ядерных процессоров Intel Xeon 53xx на 4-х ядерные процессоры Intel Xeon 54xx Результат: 57-ое место в TOP500 в июне ое место в TOP500 в ноябре февраля Москва, 2011 DVM-технология разработки параллельных программ 56 из февраля Москва, 2011 DVM-технология разработки параллельных программ 56 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Oak Ridge National Laboratory Суперкомпьютер Jaguar Cray XT5-HE Opteron Six Core 2.6 GHz 1 место в TOP Пиковая производительность TFlop/s Число ядер в системе Производительность на Linpack TFlop/s (75.4% от пиковой) Updrage: замена 4-х ядерных процессоров AMD Opteron на 6-ти ядерные процессоры AMD Opteron Результат: 2-ое место в TOP500 в июне ое место в TOP500 в ноябре февраля Москва, 2011 DVM-технология разработки параллельных программ 57 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Oak Ridge National Laboratory Jaguar Scheduling Policy MIN Cores MAX Cores MAXIMUM WALL-TIME (HOURS) февраля Москва, 2011 DVM-технология разработки параллельных программ 58 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Cray MPI: параметры по умолчанию MPI Environment Variable Name1,000 PEs10,000 PEs50,000 PEs100,000 Pes MPI Environment Variable Name128,000 Bytes 20, MPICH_UNEX_BUFFER_SIZE (The buffer allocated to hold the unexpected Eager data) 60 MB 150 MB260 MB MPICH_PTL_UNEX_EVENTS (Portals generates two events for each unexpected message received) 20,480 events 22,000110,000220,000 MPICH_PTL_UNEX_EVENTS (Portals generates two events for each unexpected message received) 2048 events ,50025, февраля Москва, 2011 DVM-технология разработки параллельных программ 59 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. Последовательная версия /* Jacobi program */ #include #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

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. Последовательная версия /****** iteration loop *************************/ for(it=1; it

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 62 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /* Jacobi-1d program */ #include #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]; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 63 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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"); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 64 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /* dynamically allocate data structures */ A = malloc ((nrow+2) * L * sizeof(double)); B = malloc ((nrow) * L * sizeof(double)); for(i=1; i

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /****** iteration loop *************************/ t1=MPI_Wtime(); for(it=1; it

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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]); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 67 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия for(i=1; i

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 69 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия /*Jacobi-2d program */ #include #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]; 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 70 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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 */ 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 71 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 72 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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)); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 73 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия for(i=0; i

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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); 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 75 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI-версия for(i=1; i

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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]); } 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 78 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. MPI/OpenMP-версия for(i=1; i

Параллельное программирование для высокопроизводительных вычислительных систем Гибридная модель DVM/OpenMP Данные Core Данные Вычисления Core … Узел 0 OpenMP Core Данные Вычисления Core … Узел N OpenMP DVM 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 80 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 81 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Алгоритм Якоби. 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 C$OMP END PARALLEL END 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 82 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Тесты NASA MultiZone BT (Block Tridiagonal Solver)3D Навье-Стокс, метод переменных направлений LU (Lower-Upper Solver) 3D Навье-Стокс, метод верхней релаксации SP(Scalar PentadiagonalSolver)3D Навье-Стокс, Beam- Warning approximate factorization 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 83 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Тесты NASA MultiZone 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 84 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Тест SP-MZ (класс A) на IBM eServer pSeries 690 Regatta DVMMPI 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 85 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Тест LU-MZ (класс A) на IBM eServer pSeries 690 Regatta DVMMPI 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 86 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Тест BT-MZ (класс A) на IBM eServer pSeries 690 Regatta зоны от 13 x 13 x 16 и до 58 x 58 x 16 DVMMPI 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 87 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Ликвидация или сокращение дублирования данных в памяти узла. Дополнительный уровень параллелизма на OpenMP реализовать проще, чем на MPI (например, когда в программе есть два уровня параллелизма – параллелизм между подзадачами и параллелизм внутри подзадачи). Улучшение балансировки на многоблочных задачах при меньшей трудоемкости реализации еще одного уровня параллелизма. Преимущества гибридной модели MPI/OpenMP 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 88 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Близость моделей OpenMP и DVM, что упрощает их совместное использование. Получение гибких программ, способных настраиваться на неоднородность узлов SMP-кластера. Возможность использования параллельной программы как последовательной, как OpenMP-программы, как DVM- программы, и как DVM/OpenMP -программы. Преимущества гибридной модели DVM/OpenMP 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 89 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Гибридная вычислительная система – это параллельная вычислительная система, в которой, наряду с универсальными процессорами, используются различные типы ускорителей, или сопроцессоров, обладающих нестандартной архитектурой ( векторной, мультитредовой, реконфигурируемой под конкретную задачу и т. п.). В идеале должна снабжаться также нестандартной, усиленной системой межузловых коммуникаций. Гибридные вычислительные системы 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 90 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Вычислительный комплекс МВС-эспресс 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 91 из 95

Параллельное программирование для высокопроизводительных вычислительных систем !$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 Модель PGI Accelerator для Fortran и Си 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 92 из 95

Параллельное программирование для высокопроизводительных вычислительных систем 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 !$acc end region enddo !$acc end data region Модель PGI Accelerator для Fortran и Си 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 93 из 95

Параллельное программирование для высокопроизводительных вычислительных систем OpenMP Application Program Interface Version 3.0, May MPI: A Message-Passing Interface Standard Version 2.2, September Параллельное программирование на языке C-DVM. Методическое пособие по практикуму для студентов 2-4 курсов. МГУ им. М.В.Ломоносова. Факультет ВMиК. Москва, 2002 г. ftp://ftp.keldysh.ru/K_student/DVM-practicum/method_CDVM_2006.doc ftp://ftp.keldysh.ru/K_student/DVM-practicum/method_CDVM_2006.doc Антонов А.С. Параллельное программирование с использованием технологии OpenMP: Учебное пособие.-М.: Изд-во МГУ, Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие.-М.: Изд-во МГУ, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, Литература 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 94 из 95

Параллельное программирование для высокопроизводительных вычислительных систем Вопросы? 28 февраля Москва, 2011 DVM-технология разработки параллельных программ 95 из 95