Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
Установить указатель текущего оператора на конец ветвления (ENDIF).
Если текущий оператор - логический IF
Аналогично, только второй ветви нет.
Если текущий оператор - IF-ELSEIF
Аналогично, только ELSEIF обрабатывается как новый IF-THEN.
Конец switch
Если текущий оператор == last_line
Закончить цикл просмотра
Проверка на наличие линейного участка - аналогично.
Перейти на блок node1 (тот, на котором были перед вызовом).
Заключение
Реализованные в дипломной работе классы C++ выполняют следующие функции, соответствующие ее задачам:
- построение расширенного графа потока управления программы, списка циклов и таблицы используемых идентификаторов;
- экспорт этих структур в файлы;
- предоставление блоку распределения вычислений и данных методов доступа к сохраненным структурам;
- дополнение внутреннего представления программы директивами FortranDVM, сформированными блоком распределения вычислений и данных.
Общий объем разработанного программного кода - около 4500 строк на языке C++.
Возможные варианты использования разработанных классов не ограничиваются системой автоматического распараллеливания. Они могут быть полезны также для решения задач, связанных с оптимизацией программ, поиска логических ошибок в их структуре, профилированием и др.
Направления развития блока, связаны, в первую очередь, со снятием ограничений на входную программу и реализацией не вошедших в дипломную работу видов анализа.
Библиография
- Sage++ users 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)
22CONTINUE
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] - +