Введение в архитектуру компьютеров

Схема алгоритма


1. Представление исходной программы в виде графа. Этот процесс достаточно подробно изложен выше.

2. Сведение циклического графа к ациклическому. Большое количество вершин графа G приводит к большому порядку матрицы смежности C. Для уменьшения порядка матрицы произведем сжатие линейных участков программы в отдельные обобщенные операторы, т. е. выделим в исходном графе G линейные подграфы и поставим им в соответствие одну обобщенную вершину графа, не нарушая при этом ни одного из существующих ориентированных циклов. Таким образом, из исходного графа G мы получаем граф G¢. Затем в графе G¢ выделим множество сильносвязных подграфов. Каждый сильносвязный подграф заменим отдельной вершиной. После выполнения указанных действий в общем случае циклический граф G превращается в сжатый ациклический граф G¢¢, представляющий собой модель исходной программы. Вершинами графа G¢¢ будут фрагменты исходной программы в виде линейных участков и сильносвязных областей.

3. Наложение информационных связей, заданных между операторами программы, на связи возможных переходов. До этого момента информационно-логические связи, заданные между операторами программы, не претерпевали существенных изменений. Преобразуем их, учитывая взаимосвязи укрупненных вершин графа G¢¢.

Если в графе G¢¢ существует переход от вершины vi

к вершине vj, то это совсем не означает, что начало выполнения оператора, соответствующего вершине vj, должно тут же следовать за окончанием оператора, соответствующего вершине vi. Однако, если результат оператора vi

является аргументом оператора vj, то в данном случае выполнение оператора vj не может начаться раньше, чем окончится выполнение оператора vi.

После анализа входов и выходов для всех компонент приведенного графа G¢¢ производится наложение информационных связей на связи возможных переходов, т. е. на связи, представленные в матрице смежности графа G¢¢. Для анализа входов и выходов всех компонент графа G¢¢ необходимо составить матрицу H информационной зависимости, элементы которой hij принимают соответственно значения 0 или 1.
При этом



ì 1, если j- й оператор зависит от значений переменных,

hij =

í   полученных в i-м операторе;

î 0, в противном случае.

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

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

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

4. Распределение вершин графа по уравнениям готовности. На данном этапе исходя из графа
 и матрицы
 строится так называемое Е-разделение, т. е. выделяются классы E1, E2, E3, ... , En

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

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

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


Содержание раздела