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

· заголовочные операторы;

· операторы объявления;

· управляющие операторы;

· исполняемые и другие операторы.

Примеры классов, относящихся к этим семействам.

Заголовочные:

- SgProgHedrStmt – заголовок программы (Fortran);

- SgProcHedrStmt – заголовок подпрограммы (Fortran);

- SgBlockDataStmt – оператор блока данных (Fortran).

Операторы объявления:

- SgVarDeclStmt – оператор объявления переменной;

- SgParameterStmt – оператор объявления констант (Fortran);

- SgImplicitStmt – оператор Implicit (Fortran).

Управляющие:

- SgForStmt – цикл FOR;

- SgIfStmt - операторветвления If-Then-Else (Fortran), if (C);

- SgLogIfStmt - оператор логического If (Fortran);

- SgArithIfStmt - оператор арифметического If (Fortran).

Исполняемые и другие:

- SgAssignStmt - оператор присваивания (Fortran);

- SgCallStmt - оператор Call (Fortran);

- SgContinueStmt - оператор Continue;

- SgControlEndStmt - обозначает конец одного из основных блоков (напр. ENDIF);

- SgReturnStmt - оператор Return;

- SgGotoStmt - оператор Goto.

Большинство операторов программы содержат некоторые выражения. Класс SgExpression является базовым для выражений всех видов:

int variant() - тэг вида выражения;

SgExpression *lhs() - левое поддерево выражения;

SgExpression *rhs() - правое поддерево выражения;

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

- SgValueExp - представляет значение одного из базовых типов;

- SgVarRefExp - ссылка на переменную или на массив;

- SgArrayRefExp - ссылка на элемент массива;

- SgFunctionCallExp - вызов функции.

Разработчиками Sage++ предлагается следующий алгоритм разбора исходной программы. Производится последовательный перебор файлов, входящих в проект. Начиная с указателя SgStatement* SgFile:: firstStatement() осуществляется обход операторов текущего файла. При этом анализируется оператор, входящие в него выражения, тело(а) – для операторов, содержащих таковое (например, управляющей группы). Переход на следующий оператор реализуется кодом cur_stmt=cur_stmt->lastNodeOfStmt()->lexNext() для операторов, не являющихся листом дерева разбора, и cur_stmt=cur_stmt->lexNext() для остальных (где cur_stmt – указатель на текущий оператор). Использование рекурсивного подхода к просмотру дерева представляется достаточно естественным.

2.2 Внутреннее представление программы высокого уровня

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

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

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

- Количество вычислительных операций в блоке – арифметические операции и стандартные функции. Эти данные требуются для оценки времени выполнения блока.

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

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

- Список переменных специального вида и их характеристики. Примером могут служить редукционные переменные.

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

2.3 Расширенный граф управления. Вспомогательные структуры

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

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

- расширенный граф управления;

- список циклов программы;

- таблица символов программы.

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

Типы блоков:

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

- Цикл. Представляет циклы программы.

- Ветвление. Соответствует условным операторам программы.

- Слияние. Это блок, в котором сходятся ветви развилки. Строгое соответствие блоков ветвления и слияния обеспечивает возможность изучения находящихся между ними элементов как единого целого.

Отношение между двумя блоками может двух типов:

1) второй блок выполняется сразу после первого;

2) второй блок содержится внутри первого - такой тип отношения может быть только между блоком-циклом и первым блоком из его тела.

Для облегчения дальнейшего описания структуры графа и его визуального представления, введем следующие названия для типов отношений между блоками:

- если второй блок следует за первым, будем говорить, что он “находится справа” от первого, соответственно первый блок “находится слева” от второго;

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

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

Блок ветвления требует наличие двух вправо – по числу возможных ветвей. Соответственно, блок слияния всегда имеет две входящие слева ссылки. Для осуществления всевозможных вариантов обхода графа требуются также использования обратных дуг – вверх и\или влево.

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

1) – 1-я ссылка вправо

2) – 2-я ссылка вправо

3) – ссылка вниз

4) – ссылка вверх

5) – 1-я ссылка влево

6) – 2-я ссылка влево

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

- уникальный номер;

- тип блока;

- уровень, характеризующий глубину вложенности;

- флаг возможности параллельного исполнения;

- количество каждой из возможных вычислительных операций;

- ссылки на 1-й и последний операторы блока.

Специфические данные:

для циклов - уникальный номер цикла;

для ветвлений – вероятность перехода по каждой из ветвей.

Количество операций определяется следующим образом:

1) линейный блок - общее их количество во всех входящих в него операторов;

2) блок цикла - сумма операций во всех входящих в его тело блоков;

3) блок ветвления – сумма слагаемых вида: число операций в i-й ветви * вероятность перехода по ней;

4) блок слияния не имеет операций;

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

Приведем схему фрагмента некоторой программы и соответствующий ей граф.

ЛИН1

DO 1 … (1)

ЛИН2

DO 1 … (2)

IF … THEN

ЛИН3

ELSE

ЛИН4

ENDIF

1 CONTINUE

DO 2 … (3)

ЛИН5

2 CONTINUE

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