Основы распараллеливания алгоритмов

Минимальной высотой всех возможных ЯПФ графа является его критический путь. Построение ЯПФ с высотой, меньшей критического пути, невозможно.
Критичиский путь – это самый длинный путь в графе.
Для примера на рисунке показан граф алгоритма вычисления площади прямоугольника, заданного координатами двух углов.



Рис. 8.1. Пример вычислительной модели алгоритма в виде графа "операции-операнды"
В рассматриваемой вычислительной модели алгоритма вершины без входных дуг могут использоваться для задания операций ввода, а вершины без выходных дуг – для операций вывода. Обозначим через множество вершин графа без вершин ввода, а через d(G) диаметр (длину максимального пути, кратчайший путь) графа.
Операции алгоритма, между которыми нет пути в рамках выбранной схемы вычислений, могут быть выполнены параллельно.
Для вычислительной схемы на рисунке, например, параллельно могут быть выполнены сначала все операции умножения, а затем первые две операции вычитания.
Для выполнения выбранного алгоритма решения задачи могут быть использованы разные схемы вычислений и построены соответственно разные вычислительные модели. Разные схемы вычислений обладают разными возможностями для распараллеливания и, тем самым, при построении модели вычислений может быть поставлена задача выбора наиболее подходящей для параллельного исполнения вычислительной схемы алгоритма.
Например, рассмотрим выражение E = (x + (a * ((b / c) * d))) - (y - z) (Рис.8.2а.)
Дерево вычислений одного из возможных эквивалентных для E выражений:
Ep = ((a * b) / (c / d)) - ((y - z) - x) (Рис.8.2б.).

Рисунок 8.2
Характеристики сложности (Рис.8.2а., Рис.8.2б.):

для выражения E:	для выражения Ep:
t = 5	tр = 3
p = 2	pр = 3
w = 6	wр = 6

•