перем = {перем} {операция} {выражение}, или (1)
перем =min/max({выражение} {перем}), или (2)
IF ({перем}.GT.{выражение})
{перем}={выражение} (3)
{операция}="+"|"*" (4)
где {выражение} не содержит {перем}, а также {перем} нигде больше не используется в данном цикле. Условие (3) есть другая реализация условия (2). Также необходимо обнаруживать редукционные переменные в выражениях вида:
{перем}={выражение}{операция}{перем}{операция}{выражение} (5), где выполняются те же условия, что и в (1)-(4), но при этом {операция} стоящая по обе стороны {перем} одинакова и если {операция} ="+", то {выражения} не содержат операций умножения и деления.
void cSourceProgramSg::BuildProgGraph().
PrgGraph()->Build(FirstSt(), LastSt(), 0, sy_DIR_RIGHT1); - построение графа.
PrgGraph()->Analyse(); - анализ построенного графа.
void cProgramGraphSg::Analyse().
CountOpers();
void cProgramGraphSg::Build (SgStatement *first_line, SgStatement *last_line, int cur_lev, int cur_dir).
Для идентификации каждого из возможных направлений добавления новых элементов определены константы:
sy_DIR_RIGHT1, sy_DIR_RIGHT2, sy_DIR_DOWN
Добавление нового звена в некотором направлении осуществляется при помощи методов cProgramGraphSg::AddNewRight1 ();
cProgramGraphSg::AddNewRight2 ();
cProgramGraphSg::AddNewRightFull (); - специальное добавление для блока слияния;
cProgramGraphSg::AddNewDown ();
При этом текущий указатель графа перемещается на новый блок.
Поскольку в графе отсутствует заглавное звено, первый узел графа строится особым образом независимо от указанного направления.
Алгоритм работы метода (рекурсивный):
Перемещение текущего указателя списка циклов на первый элемент.
Запомнить номер текущего элемента графа в переменной 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++.
Возможные варианты использования разработанных классов не ограничиваются системой автоматического распараллеливания. Они могут быть полезны также для решения задач, связанных с оптимизацией программ, поиска логических ошибок в их структуре, профилированием и др.
Направления развития блока, связаны, в первую очередь, со снятием ограничений на входную программу и реализацией не вошедших в дипломную работу видов анализа.
“Sage++ user's guide (online)”, May 1995, Version 1.9
“Designing and Building Parallel Programs (Online) v1.3”, © Copyright 1995 by Ian Foster
“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.
“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
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
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
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
Id= 4 Lev= 2 Type= 1 Opers[0]=2 Opers[2]=1 Opers[4]=2 IsParal=0
Moving up
Repeat Id= 3
Repeat Id= 2
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
Id= 6 Lev= 1 Type= 1 Opers[4]=1 IsParal=0
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
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
Id= 9 Lev= 3 Type= 1 Opers[1]=1 Opers[4]=2 Opers[6]=1 Opers[7]=1 IsParal=0
Repeat Id= 8
Repeat Id= 7
Id= 10 Lev= 1 Type= 2 Loopid= 6 Opers[0]=36 Opers[1]=18 Opers[2]=12 Opers[3]=6 IsParal=1
Id= 11 Lev= 2 Type= 2 Loopid= 7 Opers[0]=6 Opers[1]=3 Opers[2]=2 Opers[3]=1 IsParal=1
Id= 12 Lev= 3 Type= 1 Opers[0]=6 Opers[1]=3 Opers[2]=2 Opers[3]=1 IsParal=0
Repeat Id= 11
Repeat Id= 10
Id= 13 Lev= 1 Type= 1 IsParal=0
Id= 14 Lev= 1 Type= 3 Opers[5]=1 IsParal=0
Id= 16 Lev= 1 Type= 1 IsParal=0
Id= 15 Lev= 1 Type= 4 IsParal=0
Moving left1
Repeat Id= 16
Repeat Id= 14
Moving right2
Repeat Id= 15
Moving left2
Repeat Id= 13
Repeat Id= 6
Repeat Id= 5
Id= 17 Lev= 0 Type= 1 IsParal=0
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
Соответствующий распечатке граф.
Страницы: 1, 2, 3, 4, 5, 6, 7
