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

SgArrayRefExp *poSgArrRef – исходный объект Sage++.

cSymbolSg *poSym – идентификатор массива.

int SubscrNum – количество индексных выражений в ссылке.

cExpressionSg* SubscrList [df_MAX_DIM] – массив индексных выражений.

long int ExportData (ofstream&) – экспорт в файловый поток.

int operator == (cArrayRefSg&)

int opera

tor != (cArrayRefSg&)

10) Класс cVarListElemSg – представляет элемент списка обращений к переменным и массивам.

cVarListElemSg (SgVarRefExp*, cSymbolTabSg*), cVarListElemSg (SgArrayRefExp*, cSymbolTabSg*) – конструкторы класса, 1-й для разбора обращения к переменной, параметрами являются ссылка на переменную, представленная объектом Sage++, и таблица символов, в которую будут добавлены идентификаторы; 2-й для разбора ссылки на массив, параметры имеют тот же смысл.

int Variant () – тэг вида элемента (ссылка на переменную или на массив).

cSymbolSg *poSym – идентификатор переменной для ссылки 1-го вида.

cArrayRefSg *poArr – ссылка на массив для 2-го вида.

long int ExportData (ofstream&) – экспорт в файловый поток.

int operator == (cVarListElemSg&)

int operator != (cVarListElemSg&).

Для каждого из описанных классов существует его аналог во втором наборе, имеющий такое же имя за исключением постфикса “Sg”. В классах-аналогах отсутствуют методы для построения структур и конструкторы разбора. Корректная инициализация объектов этих классов производится только за счет введенных методов импорта из файлового потока. В классе cProgramGraphNode добавлены члены-данные для хранения директив FortranDVM, формирование которых осуществляет блок распределения вычислений и данных, и методы для их вставки, а также реализован экспорт этих комментариев в файл.

3.3 Алгоритмы

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

На самом внешнем уровне программы построения и экспорта всех структур находится функция main(). Ее основное содержание заключается в следующих строках:

cSourceProgramSg TestProg(projfile);

TestProg.PrepareAll();

TestProg.BuildAll();

TestProg.PrintAll(cout);

TestProg.ExportData(trgfile);

В первую очередь создается объект класса cSourceProgramSg, параметром конструктора которого является имя файла-проекта Sage++. Далее вызываются методы этого класса:

PrepareAll() – предварительная обработка Sage++ представления исходного приложения;

BuildAll() – построение всех структур;

PrintAll(cout) – вывод в поток cout построенных структур для просмотра;

ExportData(trgfile) – экспорт данных в файлы.

void cSourceProgramSg::PrepareAll()

Вызывает методы того же класса:

PrepareConsts(); - подготовка констант.

PrepareLoops(); - подготовка циклов.

void cSourceProgramSg::PrepareConsts()

Осуществляет замену обращений к константам их значениями. Алгоритм:

- Просмотр таблицы имен Sage++ и составление списка объявленных констант и их значений.

- Обход всех операторов программы и поиск во входящих в них выражениях использования каждой из констант.

- При положительном результате поиска, производится рекурсивный обход дерева разбора выражения с заходом только в те ветки, в которых используются константы. Вместо листа, соответствующего константе, строится новое выражение – значение константы, и оно возвращается на предыдущий уровень рекурсии, для остальных листьев возвращается исходное выражение. Вернувшись из рекурсивного вызова, заменяем всю ветку возвращенной. После этого текущее поддерево анализируется на возможность его вычисления. Если удается – вместо этого поддерева возвращается вычисленное значение.

При таком алгоритме, например, выражение 2*N+M+t, где N=100, M=5, будет заменено выражением 205+t.

void cSourceProgramSg::PrepareLoops().

Приводит все циклы программы к виду DO-ENDDO. Просматривает операторы программы. Для найденных циклов применяет метод Sage++, выполняющий такое преобразование.

void cSourceProgram::BuildAll().

BuildLoopList(); - построение списка циклов.

BuildProgGraph(); - построение графа.

void cSourceProgram::BuildLoopList().

LpList()->Build(FirstSt(), LastSt(), 0); - построение списка циклов.

LpList()->Analyse(); - анализ построенного списка.

void cLoopListSg::Build(SgStatement *first_line, SgStatement *last_line, int cur_lev).

Этот метод производит последовательный просмотр операторов в промежутке от first_line до last_line включительно с обеих сторон. При обнаружении оператора-заголовка цикла, осуществляется добавление к списку циклов нового элемента, в качестве его уровня вложенности принимается значение cur_lev. Затем метод вызывает себя со следующими параметрами: следующий оператор после обнаруженного заголовка цикла – first_line, оператор завершения найденного цикла – last_line, cur_lev+1 – для cur_lev в новом вызове. После возвращения из рекурсивного вызова просмотр продолжается с оператора завершения найденного цикла. Метод добавления нового элемента к списку цикла устроен так, что текущий указатель списка перемещается на вновь добавленный.

void cLoopListSg::Analyse().

Для каждого элемента списка:

AnalyseHead(SymTab()); - анализ заголовка.

AnalyseBodyVars(SymTab()); - анализ обращений к переменным и массивам в теле.

AnalyseRedVars(SymTab()); - поиск редукционных переменных.

AnalyseIoOp(); - поиск операторов ввода\вывода.

AnalyseGotoOp(); - анализ операторов перехода.

void cLoopListSg::AnalyseRedVars(cSymbolTabSg*).

В нашей задаче переменная считается редукционной, если выполнены следующие условия:

перем = {перем} {операция} {выражение}, или (1)

перем =min/max({выражение} {перем}), или (2)

IF ({перем}{.GT.|.LT.}{выражение})

{перем}={выражение} (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).

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