Модель параллелизма по данным и управлению. DVM Эта модель (1993 г.), положенная в основу языков параллельного программирования Фортран-DVM и Си- DVM, - презентация

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

2 Принципы построения DVM-системы Система должна базироваться на высокоуровневой модели выполнения параллельной программы, удобной и понятной для программиста Языки параллельного программирования должны представлять собой стандартные языки последовательного программирования, расширенные спецификациями параллелизма. Эти языки должны предлагать программисту модель программирования, достаточно близкую к модели выполнения Спецификации параллелизма должны быть прозрачными для обычных компиляторов (упрощает внедрение языка и отладку программ)

3 Принципы построения DVM-системы Основная работа по реализации модели выполнения параллельной программы (например, распределение данных и вычислений) должна осуществляться динамически специальной системой - системой поддержки выполнения DVM-программ. Это позволяет обеспечить динамическую настройку DVM-программ при запуске (без перекомпиляции) на параметры приложения (количество и размер массивов данных) и конфигурацию параллельного компьютера (количество процессоров и их производительность)

4 Модель программирования DVM на программиста возлагается ответственность за соблюдение правила собственных вычислений программист определяет общие данные, т.е. данные, вычисляемые на одних процессорах и используемые на других процессорах программист отмечает точки в последовательной программе, где происходит обновление значений общих данных программист распределяет по процессорам виртуальной параллельной машины не только данные, но и соответствующие вычисления

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

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

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

8 Распределение данных. 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

9 Распределение данных. 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)

10 Локализация данных. 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- целочисленные константы

11 Локализация данных. 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 ] на один процессор, т.е. размножить второе измерение массива А.

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

13 Распределение витков цикла. PARALLEL DVM(DISTRIBUTE B[BLOCK][BLOCK]) float B[N][M+1]; DVM(ALIGN [i][j] WITH B[i][j+1]) float A[N][M], C[N][M], D[N][M];... DVM(PARALLEL [i][j] ON B[i][j+1]) DO(i, 0, N-1, 1) DO(j, 0, M-2, 1) { A[i][j] = D[i][j] + C[i][j]; B[i][j+1] = D[i][j] – C[i][j]; } #define DVM(dvmdir) #define DO(v,l,h,s) for(v=l; v

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

15 Распределение витков цикла. 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] = …; }

16 Локализация данных. 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];

17 Удаленные данные типа 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];

18 Удаленные данные типа 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.; }

19 Удаленные данные типа SHADOW

20 Удаленные данные типа 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]; }

21 Удаленные данные типа 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]; }

22 Удаленные данные типа 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]; }

23 Удаленные данные типа 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

24 Удаленные данные типа 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 Копирование секций массивов 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];

26 Копирование секций массивов 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);

27 Макроконвейерный параллелизм 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 Параллелизм по гиперплоскостям ( dvm run 4 4 sor ) j i t1 t2 t3

29 Конвейерный параллелизм ( dvm run 3 1 sor ) 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

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

31 Макет многоблочной задачи (multiblock) 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()];

32 Макет многоблочной задачи (multiblock) Отображение блоков 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));

33 Макет многоблочной задачи (multiblock) Распределение данных 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]);

34 Макет многоблочной задачи (multiblock) Распределение вычислений FOR(IT,MAXIT) { DVM(TASK_REGION MB) { DVM(ON MB[1]) JACOBY(A1, B1, M, N1+1); 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 */

35