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


Схема алгоритма - часть 2


При этом

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

hij =

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

 

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

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

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

В результате выполнения этого этапа граф G¢¢ преобразуется в граф

, в матрице смежности
 которого учтены как информационные связи между операторами, так и связи возможных переходов.

4. Распределение вершин графа по уравнениям готовности. На данном этапе исходя из графа

 и матрицы
 строится так называемое Е-разделение, т. е. выделяются классы E1, E2, E3, ... , En

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

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

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

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




Начало  Назад  Вперед



Книжный магазин