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

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 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 Последовательная программа Статический анализатор Динамический анализатор База данных OpenMP-эксперт Генератор программы Диалоговая оболочка DVM-эксперт Параллельная программа Система автоматизации распараллеливания

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

Входные данные Таблица переменных из базы данных idNameroutineT_typedimno1A1REAL2 2abs1REAL0 3b1REAL2 4eps1REAL0 Class Variable Int id; String name; String type; Int number_of_dim; Class Variable Int id; String name; String type; Int number_of_dim; Внутреннее представление DVM-Эксперт получает на вход информации последовательной программы и результат ее анализа из базы данных.

Ограничение на последовательной программы DVM-эксперт проектировался для работы с программами, которые удовлетворяют следующим ограничениям: Программа должна состоять из одной подпрограммы, написанной на языке FORTRAN. Циклы, присутствующие в программе не должны содержать: операций ввода/вывода вызовов процедур (кроме тех редукционных операций, которые поддерживаются DVM-системой) операторов выхода из цикла Индексное пространство циклов должно быть прямоугольным (нижняя, верхняя границы цикла, а так же шаг цикла – целые константы). Обращение к элементам массива может быть только внутри циклов, индексные выражения в этих случаях должно быть линейным и зависеть только от индексной переменной цикла : a*I + b: a, b – константы, I – индексная переменная.

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

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

Описание работы DVM-эксперта 2) Для каждого гнезда циклов формируются ограничение на распределение данных, схему выравнивания и возможный вариант распределения массивов Выравнивание массивов: 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 Гнездо циклов – набор циклов, расположенных таким образом, что один цикл является телом другого цикла, гнездо циклов может состоять из одного цикла.

Описание работы DVM-эксперта 3) Для каждого варианта распределения данных генерируются DVM- директивы выравнивания массивов и организации доступа к удаленным данным для каждого гнезда циклов и вычисляется время параллельного выполнения с учётом расходов на коммуникации между узлами кластера для данного варианта DO 22 J = 2, L-1 DO 22 I = 2, L-1 A(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)) Пример:

Описание работы DVM-эксперта 4) Находится наилучший вариант распределения данных для всех гнезд циклов на основе полученных времен параллельного выполнения DO 2 IT = 1, ITMAX DO 21 J = 1, L DO 21 I = 1, L A(I, J) = B(I, J) 21 CONTINUE 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 22 CONTINUE 2CONTINUE DISTRIBUTE b( BLOCK, BLOCK ) ALIGN a( i, j ) WITH b( i, j )

Описание работы DVM-эксперта 5) После нахождения наилучшего варианта формируются окончательные 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)) LINE 3, OPERATOR 1 LINE 5, OPERATOR 3

Описание работы DVM-эксперта filelineoperpverT_dir1311 CDVM$ DISTRIBUTE b( BLOCK, BLOCK ) 1311 CDVM$ ALIGN a(I,J) WITH b(I, J) 1311 CDVM$ SHADOW a(1, 1) 1531 CDVM$* PARALLEL ( j, i ) ON a( i, j ) Class Pdir Int file; Int line; Int oper; Int pver; String T_dir Class Pdir Int file; Int line; Int oper; Int pver; String T_dir Выходные данные БД Внутреннее представление Результат работы заносятся в базу данных

Заключение В данный момент был реализован прототип эксперта на языке С++, объем кода которого составляет более 1000 строк. Эксперт может корректно построить внутреннее представление программы и выявить параллельные циклы на следующих тестах: Якоби, Последовательная верхняя релаксация (SOR), и их модифицированные версии. Модуль генерации вариантов и DVM-директив распараллеливания в текущий момент находится на стадии отладки. Описание работы эксперта на тестах и ожидаемые результаты работы представлены в приложение в дипломе.