МОЛОДЕЖНАЯ ШКОЛА « Суперкомпьютерные технологии в науке, промышленности и образовании» ННГУ им. Н.И. Лобачевского, Нижний Новгород, октября 2010 г. КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Курс: «DVM-технология разработки параллельных программ для вычислительных кластеров» Бахтин Владимир Александрович К.ф.-м.н., зав. сектором Института прикладной математики им М.В.Келдыша РАН Ассистент кафедры системного программирования факультета ВМК Московского государственного университета им. М.В. Ломоносова

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. Последовательная версия /* 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-версия 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 5 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 6 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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]); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 10 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

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

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

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

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

Массив виртуальных процессоров Массивы Циклы Массив задач Физические процессоры 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 - количество измерений массива 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 19 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Распределение данных. 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, октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 20 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Распределение данных. 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

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Локализация данных. 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- целочисленные константы 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 24 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Локализация данных. 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

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Распределение витков цикла. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Локализация данных. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Удаленные данные типа 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Копирование секций массивов 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Копирование секций массивов 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

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Многоядерные и многопоточные процессоры Процессоры 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 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 39 из 83

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

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» 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 в ноябре октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 42 из 83

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Межведомственный Суперкомпьютерный Центр Российской Академии Наук Суперкомпьютер 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 в ноябре октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 44 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» 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 в ноябре октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 45 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Oak Ridge National Laboratory Jaguar Scheduling Policy MIN Cores MAX Cores MAXIMUM WALL-TIME (HOURS) октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 46 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» 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, октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 47 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. Последовательная версия /* 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-версия 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 50 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 51 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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]); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 55 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. MPI-версия for(i=1; i

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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]; 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 58 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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); 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 63 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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]); } 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 66 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. MPI/OpenMP-версия for(i=1; i

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Алгоритм Якоби. 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 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 70 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» Тесты NASA MultiZone BT (Block Tridiagonal Solver)3D Навье-Стокс, метод переменных направлений LU (Lower-Upper Solver) 3D Навье-Стокс, метод верхней релаксации SP(Scalar PentadiagonalSolver)3D Навье-Стокс, Beam- Warning approximate factorization 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 71 из 83

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

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

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

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

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

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

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

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

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» !$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 и Си 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 80 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» 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 и Си 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 81 из 83

Всероссийская школа «Суперкомпьютерные технологии в образовании, науке и промышленности» 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: Учебное пособие.-М.: Изд-во МГУ, Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.: БХВ-Петербург, Литература 25 октября Н. Новгород, 2010 DVM-технология разработки параллельных программ 82 из 83

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