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

ЛИН1

DO 1 … (1)

ЛИН2

DO 1 … (2)

IF … THEN

ЛИН3

ELSE

ЛИН4

ENDIF

1 CONTINUE

DO 2 … (3)

ЛИН5

2 CONTINUE

Основными элементами программы, подлежащими изучению на предмет возможности распараллеливания, являются циклы. Такой подход представляется достаточно естественным, пос

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

§ Уникальный номер цикла. Служит для связи с расширенным графом.

§ Уровень вложенности – соответствует аналогичному полю из графа.

§ Ссылка на идентификатор счетчика цикла.

§ Начальное, конечное выражения счетчика, шаг цикла.

§ Количество итераций (витков) цикла.

§ Списки переменных и элементов массивов, используемых на чтение и на модификацию.

§ Список редукционных переменных.

§ Ссылки на оператор заголовка цикла и на оператор его завершения.

Все используемые в графе и списке циклов идентификаторы переменных и массивов объединяются в таблицу имен – третью составляющую нашего представления программы. Для каждого идентификатора хранится следующая информация:

§ Тэг вида идентификатора – переменная или массив.

§ Тип идентификатора.

§ Строка имени.

§ Размерность и длина по каждому измерению – для массива.

§ Ссылка на соответствующий элемент таблицы имен низкоуровнего представления.

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

3. Построение расширенного графа управления

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

3.1 Ограничения на входную программу

Первое требование к входной программе заключается в ее корректности с точки зрения синтаксиса и семантики Fortran77. Заключенные в ней ошибки, не определенные на этапе разбора текста средствами Sage++, могут привести к непредсказуемым результатам.

Общим для всей системы ограничением является также ее достаточно высокая чувствительность к плохой структурированности программы, а именно:

§ в программе не должны присутствовать операторы прекращения выполнения;

§ запрещены операторы перехода, за исключением выхода из тела цикла на первый за концом цикла оператор по условию.

Другим существенным требованием является запрет на использование COMMON-областей.

Ограничения, накладываемые в данной дипломной работе:

§ выражения в заголовках циклов (начальное, конечное, шаг) могут быть только линейными относительно некоторой переменной, т.е. иметь вид C1*V+C0, где C1 и C0 – константы, V - переменная;

§ индексные выражения в обращениях к массивам должны удовлетворять тому же условию;

§ отсутствие аппарата поиска зависимостей по данным влечет необходимость вставки пользователем комментария “DEPENDENCE” в теле цикла, содержащего зависимость.

3.2 Описание классов

В рамках дипломной работы реализовано два набора классов:

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

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

Рассмотрим назначение классов 1-го набора и их наиболее важные члены.

1) Класс cSourceProgramSg – представляет исходную последовательную программу. Обработка входной программы должна начинаться с создания объекта этого класса.

cSourceProgramSg (char *projfile) – конструктор класса, projfile – имя файла проекта Sage++; в этом конструкторе происходит открытие проекта, разбор входящего в него файла исходной программы, создание незаполненных графа, списка циклов и таблицы символов.

SgStatement *FirstSt () – 1-й оператор программы.

SgStatement *LastSt () - последний оператор программы.

cProgramGraphSg *PrgGraph () – граф программы.

cLoopListSg *LpList () – список циклов.

cSymbolTabSg *SymTab () – таблица символов.

void PrepareConsts () – замена в теле программы обращений к константам на их значения.

void PrepareLoops () – конвертация циклов программы к виду DO-ENDDO.

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

void BuildProgGraph () – построение графа программы.

void PrintLoopList (ostream&) – вывод в поток списка циклов для просмотра.

void PrintProgGraph (ostream&) – вывод графа.

void PrintSymbolTab (ostream&) – вывод таблицы имен.

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

void ImportData (char*) – импорт данных из файлов;

void Unparse (char*) – генерация результирующего текста в файле, имя которого определяется параметром метода.

При экспорте данных в файлы образуются следующие файлы:

filename.gr – узлы графа;

filename.gri – индексный файл;

filename.lp – список циклов;

filename.st – таблица символов, где filename – параметр метода ExportData(char*).

2) Класс cProgramGraphSg – представляет расширенный граф программы.

cProgramGraphSg (cSymbolTabSg*, cLoopListSg*) – конструктор класса, создает пустой граф управления. Параметры – таблица символов и список циклов, на которые будет ссылаться граф.

cLoopListSg *LpList () – список циклов, используемый графом.

cSymbolTabSg *SymTab () – таблица имен, используемая графом.

cProgramGraphNodeSg *CurNode () – текущий узел.

int IsStart () – является ли текущий узел начальным.

int GoStart (), GoDown (), GoUp (), GoLeft1 (), GoLeft2 (),

GoRight1 (), GoRight2 (), GoId (long int) – переместить указатель на текущий узел соответственно на 1-й узел, вниз, вверх, влево по 1-й ссылке, влево по 2-й ссылке, вправо по 1-й ссылке, вправо по 2-й ссылке, на узел с заданным номером. Возвращает 1 при удачном переходе, 0 в противном случае

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