 |
Расширенный граф управления. Вспомогательные структуры
|
|
|
|
Классической структурой для описания последовательности выполнения операторов программы является граф потока управления. Разработанное в данной дипломной работе представление программы выполняет те же функции, только в качестве его элементов используются блоки более высокого уровня. Такое представление - назовем его расширенным графом потока управления программы - в совокупности с некоторыми вспомогательными структурами содержит в себе всю информацию, необходимую для следующих в цикле работы блоков системы распараллеливания.
В процессе обработки исходной программы реализованным в дипломной работе блоком автоматического распараллеливателя производится построение следующих структур, образующих вместе высокоуровневое представление программы:
· расширенный граф управления;
· список циклов программы;
· таблица символов программы.
Рассмотрим устройство основной структуры - графа управления. Граф состоит из блоков, соответствующих логическим элементам представления, и дуг, отражающих отношение между ними.
Типы блоков:
· Линейный участок. Объединяет в себе непрерывную группу операторов, выполняющихся последовательно один за другим.
· Цикл. Представляет циклы программы.
· Ветвление. Соответствует условным операторам программы.
· Слияние. Это блок, в котором сходятся ветви развилки. Строгое соответствие блоков ветвления и слияния обеспечивает возможность изучения находящихся между ними элементов как единого целого.
Отношение между двумя блоками может двух типов:
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
Основными элементами программы, подлежащими изучению на предмет возможности распараллеливания, являются циклы. Такой подход представляется достаточно естественным, поскольку во многих приложениях основная вычислительная нагрузка находится именно в циклах. Примерами могут служить реализации всевозможных численных методов. Очевидная нецелесообразность размещения всей специфической для циклов информации в узлах графа, а также существование этапов изучения циклов программы без учета их расположения в графе повлекли за собой разработку дополнительной структуры данных - списка циклов. Он представляет собой двунаправленный линейный список, в котором каждому циклу соответствует уникальный элемент, содержащий следующие данные:
· Уникальный номер цикла. Служит для связи с расширенным графом.
· Уровень вложенности - соответствует аналогичному полю из графа.
· Ссылка на идентификатор счетчика цикла.
· Начальное, конечное выражения счетчика, шаг цикла.
· Количество итераций (витков) цикла.
· Списки переменных и элементов массивов, используемых на чтение и на модификацию.
· Список редукционных переменных.
· Ссылки на оператор заголовка цикла и на оператор его завершения.
Все используемые в графе и списке циклов идентификаторы переменных и массивов объединяются в таблицу имен - третью составляющую нашего представления программы. Для каждого идентификатора хранится следующая информация:
· Тэг вида идентификатора - переменная или массив.
· Тип идентификатора.
· Строка имени.
· Размерность и длина по каждому измерению - для массива.
· Ссылка на соответствующий элемент таблицы имен низкоуровнего представления.
Описанные структуры образуют представление исходной последовательной программы достаточно высокого уровня абстракции, соответствующего проблематике рассматриваемой нами предметной области. Оно позволяет хранить всю необходимую для распределения вычислений и данных информацию о программе, сокращая при этом количество функциональных блоков до минимума.
|
|
|
