Система автоматизации распараллеливания: DVM-эксперт Блюменберг Э.П. 528 Научный руководитель: профессор В.А. Крюков. - презентация

1 Система автоматизации распараллеливания: DVM-эксперт Блюменберг Э.П. 528 Научный руководитель: профессор В.А. Крюков

2 DVM рекомендации OpenMP рекомендации Последовательная программа Пользователь program compute_pi parameter (n = 1000) integer i double precision w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision !$OMP PARALLEL DO PRIVATE(x), HARED(w) w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision !$OMP PARALLEL DO PRIVATE(x), HARED(w) w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end Анализ программы База данных OpenMP эксперт OpenMP эксперт DVM эксперт DVM эксперт program compute_pi parameter (n = 1000) integer i double precision DVM PARALLEL DO… w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end program compute_pi parameter (n = 1000) integer i double precision DVM PARALLEL DO… w,x,sum,pi,f,a f(a) = 4.d0/(1.d0+a*a) w = 1.0d0/n … end

3 Цели дипломной работы Исследование возможных подходов к распределению данных и вычислений между узлами кластера Создание программы - модуля для распределения данных и вычислений, организации доступа к удаленным данным, формирования и вставки распараллеливающих DVM-указаний в тело программы

4 Исходные данные Дерево циклов с описанием циклов. Описание цикла содержит: указание на переменную цикла; первое, последнее значение, шаг; наличие в цикле операторов ввода-вывода, побочных выходов и т.п. оценка трудоемкости одного витка цикла; признак тесной вложенности; список обращений к массивам и переменным. список зависимостей Список массивов (и простых переменных). Для каждого массива: идентификатор; размер по каждому измерению; список обращений к массиву. Вариант задачи: список пар (переменная, значение)

5 Описание работы DVM-эксперта 1) Выявляются циклы программы, которые могут выполняться параллельно в рамках модели DVM-системы. Основную сложность представляют элементы массива и переменные в которые производится запись, они должны быть на одном узле кластера. Данные, которые только читаются в цикле, могут быть на других узлах, к ним можно осуществить удалённый доступ. REAL A(L,L),B(L,L) DO 2 IT = 1, ITMAX DO 21 J = 2, L-1 DO 21 I = 2, L-1 A(I, J) = B(I, J) 21CONTINUE DO 22 J = 2, L-1 DO 22 I = 2, L-1 B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J) + A( I, J+1 )) / 4 22CONTINUE 2 CONTINUE

6 Описание работы DVM-эксперта 2) 2) Формируются возможные варианты распараллеливания выбранных циклов и схема выравнивания массивов. Каждый цикл накладывает ограничения на распределение данных. Варианты распараллеливания циклов Номер варианта Параллельные циклы 1 1, Выравнивание массивов: A(I,J), B(I,J) 1DO 21 J = 2, L-1 2DO 21 I = 2, L-1 A(I, J) = B(I, J) 21CONTINUE

7 Описание работы DVM-эксперта 3) 3) Для каждого варианта определяются DVM-указания по организации доступа к удаленным данным и вычисляется время выполнения с учётом расходов на коммуникации между узлами кластера DO 22 j = 2, L-1 DO 22 i = 2, L-1 b(i, j) = (a( i-1, j ) + a( i, j-1 ) + a( i+1, j) + a( i, j+1 )) / 4 22CONTINUE DISTRIBUTE b( BLOCK, BLOCK ) ALIGN a( i, j ) WITH b( i, j ) SHADOW a(1,1) SHADOW_RENEW (a(1,1)) PARALLEL ( j, i ) ON b( i, j ), SHADOW_RENEW (a(1,1)) Пример:

8 Описание работы DVM-эксперта 4) Находится лучшая схема распределения массивов всей программы путём объединения лучших вариантов распараллеливания циклов DO 2 it = 1, ITMAX DO 21 j = 2, L-1 DO 21 i = 2, L-1 a(i, j) = b(i, j) 21CONTINUE DO 22 j = 2, L-1 DO 22 i = 2, L-1 b(i, j) = (a( i-1, j ) + a( i, j-1 ) + a( i+1, j) + a( i, j+1 )) / 4 22CONTINUE 2 CONTINUE DISTRIBUTE b( BLOCK, BLOCK ) ALIGN a( i, j ) WITH b( i, j )

9 Описание работы DVM-эксперта 5)В базу данных заносятся DVM-указания, соответствующие построенному варианту распараллеливания, и генерируется DVM-программа do j = 2,L - 1 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 CDVM$ DISTRIBUTE b( BLOCK, BLOCK ) CDVM$ ALIGN a( i, j ) WITH b( i, j ) CDVM$ SHADOW a(1,1) real a(l,l),b(l,l) do it = 1,itmax CDVM$ PARALLEL ( j, i ) ON a( i, j ) do j = 2,L - 1 do i = 2,L - 1 a(i,j) = b(i,j) enddo CDVM$ PARALLEL ( j, i ) ON b( i, j ), CDVM$* SHADOW_RENEW (a(1,1))

10 Заключение Разработаны алгоритмы распределения данных и вычислений, организации доступа к удаленным данным. Реализован блок "DVM-эксперт" экспериментальной системы автоматизации распараллеливания. Общий объём кода составил более 2000 строк на языке Си++. Работа DVM-эксперта была протестирована на нескольких примерах. Результаты для классических тестов Якоби и SOR представлены в дипломной работе.