Методика распараллеливания программ в модели DVM Институт прикладной математики им. М.В.Келдыша РАН - презентация

1 Методика распараллеливания программ в модели DVM Институт прикладной математики им. М.В.Келдыша РАН

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

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

4 Компилятор C-DVM Компилятор Fortran-DVM Система поддержки параллельного выполнения (Lib-DVM) DVM-отладчик Анализатор производительности DVM-программ Предсказатель производительности DVM-программ Состав DVM-системы

5 Правило собственных вычислений: OWN(A[i]) - процессор, на который распределен A[i] A[i] = expr Оператор всегда выполняется на процессоре OWN(A[i]) Локализация данных: Операнды expr распределены на процессор OWN(A[i])

6 Распараллеливание последовательной программы Согласованное распределение массивов данных и параллельных циклов на массив виртуальных процессоров. Цель: максимум параллелизма и максимум локализации Определение общих (не локальных данных) и их спецификация. Общие данные: данные, вычисляемые на одних процессорах и используемые на других процессорах.

7 Выполнение программы Модель: одна программа - множество потоков данных На всех процессорах - одна и та же программа Проба: свой - чужой оператор по правилу собственных вычислений

8 Абстрактная схема распределения данных и витков параллельных циклов Объекты: P -индексное пространство массива виртуальных процессоров, определяется пользователем и задается при запуске программы A i -индексное пространство i-ого массива данных L j -индексное пространство j-ого параллельного цикла

9 Директивы распределения устанавливают соответствие между точками (элементами) индексных пространств: ALIGN: A i1 =>A i2 Каждой точке (элементу) A i2 ставится в соответствие подмножество точек (элементов) массива A i1 PARALLEL: L j =>A i Каждой точке (элементу) A i ставится в соответствие подмножество точек (витков цикла) L j DISTRIBUTE: A i =>P Каждой точке (виртуальному процессору) P ставится в соответствие подмножество точек (элементов) массива A i

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

11 Распределение данных DISTRIBUTE DVM( DISTRIBUTE f1…fk ) где fi= [ BLOCK ]- распределение равными блоками (распределенное измерение) [ ]- распределение целым измерением (локальное измерение) k- количество измерений массива P(m)- линейка виртуальных процессоров

12 Распределение данных DISTRIBUTE Примеры: DVM( DISTRIBUTE [ BLOCK ] ) float A[N]; DVM( DISTRIBUTE [ ] ) float A[N]; DVM( DISTRIBUTE [ BLOCK ] [ ] ) float B[N][N]; DVM( DISTRIBUTE [ ] [ BLOCK ] ) float B[N][N]; P(m1,m2) - массив виртуальных процессоров

13 Локализация данных ALIGN DVM( ALIGN a1…an WITH B b1…bm ) где ai - параметр i-го измерения выравниваемого массива А bj - параметр j-го измерения базового массива B n - количество измерений массива А m - количество измерений массива В ai = a[Idi] bj=[c*Idj +d] [ ] [ ] Idi, Idj - идентификаторы c, d - целочисленные константы

14 Локализация данных ALIGN Примеры: DVM( ALIGN [ i ] WITH B[ 2*i+1] ) float A[N]; DVM( ALIGN [ i ] [ j ] WITH C[ j ] [ i ] ) float D[N][N]; DVM( ALIGN [ i ] WITH C[ ] [ i ] ) float E[N]; DVM( ALIGN [ i ] [ ] WITH B[ i ] )float C[N][N];

15 Распределение витков цикла PARALLEL Макросы заголовков циклов: # define DO ( v, f, u, s ) for(v=f; v

16 Распределение витков цикла PARALLEL DVM( PARALLEL [ I1 ]… [ In ] ON A e1… em ) где Ij - индекс j-го заголовка параллельного цикла, n - количество заголовков цикла, m - количество измерений массива, A - идентификатор распределенного массива, ei = [a* Ik +b], a, b - целочисленные переменные

17 Распределение витков цикла PARALLEL Цикл не удовлетворяет требованиям массива витков цикла: Не тесно-гнездовой цикл FOR(i,N) { a=5.; FOR(j,N) {... } } Не прямоугольное индексное пространство FOR(i,N) DO(j,i,N,1) {... }

18 Распределение витков цикла PARALLEL Цикл не удовлетворяет требованиям массива витков цикла: Виток цикла на разных процессорах FOR(i,N) { D[2*i] =...; { D[2*i] =...; } D[2*i+1]= …; } FOR(i,N) {D[2*i+1]= …; } DVM( DISTRIBUTE [ BLOCK ] [ BLOCK ] ) float A[N+1][N+1], B[N][N]; FOR(i,N) FOR(j,N) { A[i+1][j+1] = …; B[i][j] = …; } DVM( ALIGN [ i ] [ j ] WITH A[i+1] [j+1] ) float B[N][N];

19 Общие (удаленные) данные Сравнение индексных выражений по распределенным измерениям левой и правой части оператора присваивания Выражение условного оператора - правая часть A[i] = (C[i] > D[i]) ? B[i] : 0.

20 Локализация данных DVM( DISTRIBUTE [ BLOCK ] ) float A[N]; DVM( ALIGN [ i ] WITH A[ i ] ) float B[N],C[N]; DVM( PARALLEL [ i ] ON A[ i ] ) FOR( i, N ) { A[i] = B[i] + C[i] ; }

21 Локализация с помощью TEMPLATE DVM( DISTRIBUTE [ BLOCK ] ; TEMPLATE [N+d1+d2] ) void *TABC; DVM( ALIGN [ i ] WITH TABC[ i ] ) float B[N]; DVM( ALIGN [ i ] WITH TABC[ i +d1] )float A[N]; DVM( ALIGN [ i ] WITH TABC[ i +d1+d2] )float C[N]; DVM( PARALLEL [ i ] ON A[ i ] ) FOR( i, N ) { A[i] = B[i-d1] + C[i+d2] ; }

22 Схема отображения ALIGN P1 P2P3 P4 TABC B d1 A d1+d2 C

23 Общие данные типа SHADOW DVM( DISTRIBUTE [ BLOCK ] ) float A[N]; DVM( ALIGN [ i ] WITH A[ i ]; SHADOW [d1:d2]) float B[N]; DVM( PARALLEL [ i ] ON A[ i ] ; SHADOW_RENEW B) DO( i,d1, N-d2-1,1 ) { A[i] = B[i-d1] + B[i+d2] ; }

24 Общие данные типа ACROSS DVM( DISTRIBUTE [ BLOCK ]; SHADOW [d1:d2]) float A[N]; DVM( PARALLEL [ i ] ON A[ i ] ; ACROSS A[d1:d2]) DO( i,d1, N-d2-1,1 ) { A[i] = A[i-d1] + A[i+d2] ; }

25 Общие данные типа REMOTE_ACCESS DVM( DISTRIBUTE [ BLOCK ] ) float A[N], C[2*N]; DVM( PARALLEL [ i ] ON A[ i ] ; REMOTE_ACCESS C[5] C[i+N] ) FOR( i, N ) { A[i] = C[5] + C[i+N] ; }

26 Общие данные типа REDUCTION DVM( DISTRIBUTE [ BLOCK ] ) float A[N]; DVM( PARALLEL [ i ] ON A[ i ] ; REDUCTION SUM (s) ) FOR( i, N ) { s = s + A[i] ; } DVM( DISTRIBUTE [ BLOCK ] ; TEMPLATE [N] ) void *TM; DVM( PARALLEL [ i ] ON TM[ i ] ; REDUCTION PRODUCT (sm) ) FOR( i, N ) { sm = sm * i ; }

27 Параллельный цикл Левая часть: распределенный массив, редукционная переменная, приватная переменная. Распределенный цикл => распределенное измерение Локальный цикл => локальное измерение

28 Программа JACOBI на C-DVM

29

30 Distribution of array A [8][8]

31 Программа SOR на C-DVM

32 Параллелизм по гиперплоскостям CDVM$ DISTRIBUTE A (BLOCK,BLOCK) j i t1 t2 t3

33 Конвейерный параллелизм CDVM$ DISTRIBUTE A (BLOCK,*) 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

34 Оптимизация 1. Совмещение вычислений и доступа к общим данным 2. Избыточные вычисления вместо общих данных SHADOW 3. Асинхронное копирование вместо общих данных REMOTE

35 Спецификация обновления значений общих данных Перед циклом использования Между циклом вычислений и циклом использования Матрица цикл-массив ({use,def}) Порядок выполнения циклов (граф управления)

36 Совмещение вычислений и доступа к общим данным DVM(CREATE_SHADOW_GROUP grshad: A);... DVM(SHADOW_START grshad );... DVM(PARALLEL [ i ] [ j ] ON A[ i ] [ j ]; SHADOW_WAIT grshad ) 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;

37 Избыточные вычисления DVM(PARALLEL [i] ON A[i]; SHADOW_COMPUTE) FOR(i,n) A[i] = i; DVM(PARALLEL [i] ON A[i] ) DO(i,1,n-2,1) C[i] = A[i-1] +A[i+1];

38 Асинхронное копирование секций массивов k = N/4 - 1; FOR (i, N-1) FOR (j, N-1) A[ i+k ] [ j+k ] = f( A[ 2*i ] [ 2*j ] ) ; 2N N N

39 DVM( DISTRIBUTE [ BLOCK ] [ BLOCK ] ) float A[2*N][2*N]; DVM( ALIGN [ i ] [ j ] WITH A[ i] [ j ] ) float B[2*N][2*N]; DVM( COPY_FLAG) void *flagS; k = N/4 - 1; DVM( PARALLEL [ i ] [ j ] ON B[2*i] [2*j] ) FOR (i, N-1) FOR (j, N-1) B[ 2*i ] [ 2*j ] = f( A[ 2*i ] [ 2*j ] ) ; DVM( COPY_START &flagS) FOR (i, N-1) FOR (j, N-1) A[ i+k ] [ j+k ] = B[ 2*i ] [ 2*j ] ; DVM( COPY_WAIT &flagS)