Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления

Для идентификации каждого из возможных направлений добавления новых элементов определены константы:

sy_DIR_RIGHT1, sy_DIR_RIGHT2, sy_DIR_DOWN

Добавление нового звена в некотором направлении осуществляется при помощи методов cProgramGraphSg::AddNewRight1 ();

cProgramGraphSg::AddNewRight2 ();

cProgramGraphSg::AddNewRightFull (); - специальное добавление для блока слияния;

cPro

gramGraphSg::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++.

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

Направления развития блока, связаны, в первую очередь, со снятием ограничений на входную программу и реализацией не вошедших в дипломную работу видов анализа.

Библиография

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

 Скачать реферат