Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления (стр. 7 из 7)
Запомнить номер текущего элемента графа в переменной node1.
Начать цикл прохода с first_line.
switch
Если текущий оператор – заголовок цикла
Если перед этим прошли какое-то количество операторов, т.е. надо добавить линейный блок, определяем направление добавления следующим образом:
Если еще ничего не добавляли и cur_dir == sy_DIR_DOWN
Добавить вниз.
Иначе
Если ничего не добавляли и cur_dir == sy_DIR_RIGHT2
Добавить вправо2.
Иначе
Добавить вправо1.
{такой анализ связан с тем, что когда мы добавляем 1-е звено в данном вызове метода, мы должны учитывать переданное направление; в остальных случаях добавление блоков на одном уровне происходит вправо1}
Запомнить номер текущего (только что добавленного) элемента в node1.
Заполнить блок информацией.
{теперь надо добавить блок для найденного цикла}
Определить направление аналогично и добавить.
Заполнить блок информацией.
Добавить в него информацию из текущего элемента списка циклов и сдвинуться в списке вправо.
Вызвать рекурсивно Build с телом найденного цикла, cur_lev+1, sy_DIR_DOWN.
Установить указатель текущего оператора на конец цикла (ENDDO).
Если текущий оператор – заголовок ветвления
Проверка на необходимость добавления линейного блока – аналогично.
Добавить блок развилки в нужном направлении – аналогично.
Запомнить номер текущего блока (развилка) в переменной node2.
Заполнить блок информацией.
Добавить слияние.
Запомнить номер текущего блока (слияние) в переменной node3.
Вернуться влево (на развилку).
Вызвать Build с телом 1-й ветви, cur_lev, sy_DIR_RIGHT1.
Перейти на блок node2.
Вызвать Build с телом 2-й ветви, cur_lev, sy_DIR_RIGHT2.
Перейти на блок node3 (далее надо добавлять после слияния).
Установить указатель текущего оператора на конец ветвления (ENDIF).
Если текущий оператор – логический IF
Аналогично, только второй ветви нет.
Если текущий оператор – IF-ELSEIF
Аналогично, только ELSEIF обрабатывается как новый IF-THEN.
Конец switch
Если текущий оператор == last_line
Закончить цикл просмотра
Проверка на наличие линейного участка – аналогично.
Перейти на блок node1 (тот, на котором были перед вызовом).
Заключение
Реализованные в дипломной работе классы C++ выполняют следующие функции, соответствующие ее задачам:
- построение расширенного графа потока управления программы, списка циклов и таблицы используемых идентификаторов;
- экспорт этих структур в файлы;
- предоставление блоку распределения вычислений и данных методов доступа к сохраненным структурам;
- дополнение внутреннего представления программы директивами FortranDVM, сформированными блоком распределения вычислений и данных.
Общий объем разработанного программного кода – около 4500 строк на языке C++.
Возможные варианты использования разработанных классов не ограничиваются системой автоматического распараллеливания. Они могут быть полезны также для решения задач, связанных с оптимизацией программ, поиска логических ошибок в их структуре, профилированием и др.
Направления развития блока, связаны, в первую очередь, со снятием ограничений на входную программу и реализацией не вошедших в дипломную работу видов анализа.
Библиография
1. “Sage++ user’s guide (online)”, May 1995, Version 1.9
2. “Designing and Building Parallel Programs (Online) v1.3”, © Copyright 1995 by Ian Foster
3. “The Polaris Internal Representation.” Keith A. Faigin, Jay P. Hoeflinger, David A. Padua, Paul M. Petersen, and Stephen A. Weatherford. International Journal of Parallel Programming, October 1994.
4. “The Structure of Parafrase-2: An Advanced Parallelizing Compiler for C and Fortran” Constantine Polychronopoulos, Milind B. Girkar, Mohammad R. Haghighat, Chia L. Lee, Bruce P.Leung, Dale A. Schouten. Languages and Compilers for Parallel Computing, MIT Press, 1990
Приложение
В качестве одной из тестовых программ использовалась реализация на языке Fortran77 алгоритма Якоби поиска решения системы линейных уравнений A x = b.
PROGRAM JACOB
PARAMETER (L=8, ITMAX=20)
REAL A(L,L), EPS, MAXEPS, B(L,L)
W = 0.5
MAXEPS = 0.5E - 7
DO 1 I = 1, L
DO 1 J = 1, L
A(I,J) = 0.
B(I,J) = (1. +I+J)*2.3
1 CONTINUE
DO 2 IT = 1, ITMAX
EPS = 0.
DO 21 I = 2, L-1
DO 21 J = 2, L-1
EPS = MAX (EPS, ABS(B(I,J)-A(I,J)))
A(I,J) = B(I,J)
21 CONTINUE
DO 22 I = 2, L-1
DO 22 J = 2, L-1
B(I,J) = (W/4)*(A(I-1,J)+A(I,J-1)+A(I+1,J)+A(I,J+1))+(1-W)*A(I,J)
22 CONTINUE
PRINT *, 'IT = ', IT, ' EPS = ', EPS
IF (EPS .LT. MAXEPS) THEN
GO TO 3
ENDIF
2 CONTINUE
3 OPEN (3, FILE='JACOBI.DAT', FORM='FORMATTED')
WRITE (3,*) B
END
Результат вывода в поток cout структур данных, построенных тестирующей программой.
Building Loop List
Building Loop List - ok
Building Prog Graph
Building Prog Graph - ok
Printing Loop List
Count= 7
Id= 1 Lev= 0 Counter: Id= 1 Name= i Start: 1 End: 8 Step: 1 IterNum: 8
Left vars: Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0 Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: i j
Id= 2 Lev= 1 Counter: Id= 3 Name= j Start: 1 End: 8 Step: 1 IterNum: 8
Left vars: Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0 Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: i j
Id= 3 Lev= 0 Counter: Id= 5 Name= it Start: 1 End: 20 Step: 1 IterNum: 20 Left vars: eps Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0 Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: eps Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0 w Array name= a Subscr0: 1*i+-1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+-1 Array name= a Subscr0: 1*i+1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+1
Id= 4 Lev= 1 Counter: Id= 1 Name= i Start: 2 End: 7 Step: 1 IterNum: 6
Left vars: eps Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: eps Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Id= 5 Lev= 2 Counter: Id= 3 Name= j Start: 2 End: 7 Step: 1 IterNum: 6
Left vars: eps Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: eps Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Id= 6 Lev= 1 Counter: Id= 1 Name= i Start: 2 End: 7 Step: 1 IterNum: 6
Left vars: Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: w Array name= a Subscr0: 1*i+-1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+-1 Array name= a Subscr0: 1*i+1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+1 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Id= 7 Lev= 2 Counter: Id= 3 Name= j Start: 2 End: 7 Step: 1 IterNum: 6
Left vars: Array name= b Subscr0: 1*i+0 Subscr1: 1*j+0
Right vars: w Array name= a Subscr0: 1*i+-1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+-1 Array name= a Subscr0: 1*i+1 Subscr1: 1*j+0 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+1 Array name= a Subscr0: 1*i+0 Subscr1: 1*j+0
Printing Loop List - ok
Printing Prog Graph
Count= 17
Id= 1 Lev= 0 Type= 1 Opers[4]=2 IsParal=0
Moving right1
Id= 2 Lev= 0 Type= 2 Loopid= 1 Opers[0]=16 Opers[2]=8 Opers[4]=16 IsParal=1
Moving down
Id= 3 Lev= 1 Type= 2 Loopid= 2 Opers[0]=2 Opers[2]=1 Opers[4]=2 IsParal=1
Moving down
Id= 4 Lev= 2 Type= 1 Opers[0]=2 Opers[2]=1 Opers[4]=2 IsParal=0
Moving up
Repeat Id= 3
Moving up
Repeat Id= 2
Moving right1
Id= 5 Lev= 0 Type= 2 Loopid= 3 Opers[0]=36 Opers[1]=24 Opers[2]=12 Opers[3]=6 Opers[4]=13 Opers[5]=1 Opers[6]=6 Opers[7]=6 IsParal=0
Moving down
Id= 6 Lev= 1 Type= 1 Opers[4]=1 IsParal=0
Moving right1
Id= 7 Lev= 1 Type= 2 Loopid= 4 Opers[1]=6 Opers[4]=12 Opers[6]=6 Opers[7]=6 RedVar[0]: var= eps op= 5 IsParal=1
Moving down
Id= 8 Lev= 2 Type= 2 Loopid= 5 Opers[1]=1 Opers[4]=2 Opers[6]=1 Opers[7]=1 RedVar[0]: var= eps op= 5 IsParal=1
Moving down
Id= 9 Lev= 3 Type= 1 Opers[1]=1 Opers[4]=2 Opers[6]=1 Opers[7]=1 IsParal=0
Moving up
Repeat Id= 8
Moving up
Repeat Id= 7
Moving right1
Id= 10 Lev= 1 Type= 2 Loopid= 6 Opers[0]=36 Opers[1]=18 Opers[2]=12 Opers[3]=6 IsParal=1
Moving down
Id= 11 Lev= 2 Type= 2 Loopid= 7 Opers[0]=6 Opers[1]=3 Opers[2]=2 Opers[3]=1 IsParal=1
Moving down
Id= 12 Lev= 3 Type= 1 Opers[0]=6 Opers[1]=3 Opers[2]=2 Opers[3]=1 IsParal=0
Moving up
Repeat Id= 11
Moving up
Repeat Id= 10
Moving right1
Id= 13 Lev= 1 Type= 1 IsParal=0
Moving right1
Id= 14 Lev= 1 Type= 3 Opers[5]=1 IsParal=0
Moving right1
Id= 16 Lev= 1 Type= 1 IsParal=0
Moving right1
Id= 15 Lev= 1 Type= 4 IsParal=0
Moving left1
Repeat Id= 16
Moving left1
Repeat Id= 14
Moving right2
Repeat Id= 15
Moving left2
Repeat Id= 14
Moving left1
Repeat Id= 13
Moving left1
Repeat Id= 10
Moving left1
Repeat Id= 7
Moving left1
Repeat Id= 6
Moving up
Repeat Id= 5
Moving right1
Id= 17 Lev= 0 Type= 1 IsParal=0
Moving left1
Repeat Id= 5
Moving left1
Repeat Id= 2
Moving left1
Repeat Id= 1
Printing Prog Graph - ok
Printing Symbol Table
Id= 1 Name= i
Id= 2 Name= a Dim= 2 DimLen0= 8 DimLen1= 8
Id= 3 Name= j
Id= 4 Name= b Dim= 2 DimLen0= 8 DimLen1= 8
Id= 5 Name= it
Id= 6 Name= eps
Id= 7 Name= w
Printing Symbol Table - ok
Export Data
Export Data - ok
Opers[0] – ‘+’
Opers[1] – ‘-’
Opers[2] – ‘*’
Opers[3] – ‘/’
Opers[4] – ‘:=’
Opers[5] – ‘<’, ‘>’,…
Opers[6] – ABS()
Opers[7] – MAX()
Redop=5 - MIN
Соответствующий распечатке граф.
