Стр. 19 - Параллельное программирование

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
17
МОДЕЛЬ ВЫЧИСЛЕНИЙ В ВИДЕ ГРАФА
"ОПЕРАЦИИ-ОПЕРАНДЫ"
Для описания информационных зависимостей в алгоритмах решения задач
может быть использована модель в виде графа "операции-операнды" [3, 16, 18, 23,
26, 28].
Для удобства изложения материала предположим, что время выполнения лю-
бых вычислительных операций является одинаковым и равняется 1 (в заданных
единицах измерения), а передача данных между вычислительными устройствами
выполняется мгновенно (это справедливо при наличии общей разделяемой памяти в
параллельной вычислительной системе).
Обозначим существующие между операциями, выполняемыми в алгоритме
решения вычислительной задачи, информационные зависимости в виде ацикличе-
ского ориентированного графа G = (V, R) , где V = {1, …, |V|} - множество вершин
графа, представляющее выполняемые операции алгоритма, а R есть множество дуг
графа (при этом дуга r = (i, j) принадлежит графу только, если операция j использует
результат выполнения операции i).
Рассмотрим алгоритм вычисления площади прямоугольника (рис. 2.1),
заданного координатами двух углов. Для выполнения выбранного алгоритма реше-
ния задачи могут быть использованы разные схемы вычислений и построены соот-
ветственно разные вычислительные модели, а разные схемы вычислений обладают
разными возможностями для распараллеливания и, тем самым, при построении мо-
дели вычислений может быть поставлена задача выбора наиболее подходящей для
параллельного исполнения вычислительной схемы алгоритма. Здесь вершины без
входных дуг используются для задания операций ввода, а вершины без выходных
дуг – для операций вывода. Обозначим через V множество вершин графа без вер-
шин ввода, а через d(G) диаметр (длина максимального пути) графа.