Учебное пособие москва мади 2020 ббк 32. 81 В 683 Волосова, А. В. В683

 

---

66 
6.2. Граф алгоритма и параллельные вычисления 
В процессе разработки программы присутствует частичный порядок 
выполнения операций, который предполагает установку очередности 
выполнения операции во времени или независимое их выполнение. Для 
программы частичный порядок сохраняется в независимости от совокупного 
времени выполнения множества операций, которое может меняться. То есть 
предполагается возможность выбора некоторой реализации в пределах 
неизменного частичного порядка. 
Пусть некоторая программа описывает алгоритм с фиксированными 
входными данными. 
П
построении ориентированного графа в качестве 
вершин выберем множество точек арифметического пространства, которое 
взаимно однозначно отображается на множество всех операций алгоритма. 
Для любой пары вершин u, v будем считать, что операция, которая 
соответствует вершине u, отвечает за доставку соответствующей вершине v 
аргумента операции. В случае, если операции зависимы друг от друга, 
проведем дугу из вершины u в вершину v. Если соответствующие операции 
могут выполняться независимо друг от друга, дуга не проводится. Случаи, в 
которых аргументы операции являются начальными данными или результат 
операции нигде не используется, вершины графа не будут иметь 
соответственно входящие и выходящие дуги. Такие вершины будем называть 
соответственно входными или выходными вершинами графа. Граф 
алгоритма почти всегда зависит от входных данных, поэтому граф - граф 
параметризованный. От значений параметров зависит число вершин, и 
совокупность дуг. Граф определяется, как граф информационной 
зависимости и соответствует реализации алгоритма при фиксированных 
входных данных. Такой граф еще принято называть 
графом алгоритм
.
В случае наличия в программе условных операторов, соответствующий 
алгоритм называется