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


Преобразование последовательных программ в последовательно-параллельные - часть 3


Множество направленных дуг U = {u1, u2, ..., um} соответствует возможным переходам между операторами программы.

Из теории графов известно, что ориентированный граф полностью описывается соответствующей матрицей смежности такой, что ее элемент

 

ì 1, если существует дуга (ui,uj);

Сij =

í

  

î 0, если такой дуги нет.


Пусть рассматриваемый граф G является произвольным циклическим графом с одной входной и одной выходной вершинами. Следуя определению сильносвязного подграфа, будем идентифицировать его с таким фрагментом в программе, из любого оператора которого существует переход в любой другой оператор, принадлежащий этому же фрагменту. Например, сильносвязным подграфом будут фрагменты 2, 3, 4 (рис. 10.3).

Рис. 10.3. Сильносвязный подграф

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

программе.

Итак, ставится задача – преобразовать алгоритм решения задачи, заданный последовательной программой, для параллельной его реализации на многопроцессорной вычислительной системе.

Для преобразования программы из одной (последовательной) формы в другую (последовательно-параллельную) мы используем ее интерпретацию в виде орграфа. Вообще говоря, идея использовать некоторый "формализм" в качестве посредника для преобразования программ встречалась и раньше в связи с другими задачами. Так, в трансляторе системы АЛЬФА был введен дополнительный проход, во время которого по исходной программе строилась ее модель в виде схемы Лаврова, что позволило обнаруживать и анализировать информационные связи в целях глобальной экономии памяти.

Построим схему алгоритма распараллеливания программ, используя некоторые сведения из теории графов.




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



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