Граф программных зависимостей

Материал из WEGA
Перейти к навигации Перейти к поиску

Граф программных зависимостей (Program dependence graph) — орграф, вершины которого суть операторы и предикаты программы и в котором две вершины [math]\displaystyle{ S }[/math] и [math]\displaystyle{ T }[/math] соединены дугой [math]\displaystyle{ (S,T) }[/math] в том и только том случае, если оператор [math]\displaystyle{ T }[/math] зависит (по данным или по управлению) от оператора [math]\displaystyle{ S }[/math]. Для удобства представляется в виде двух подграфов: подграфа зависимостей по управлению и подграфа зависимостей по данным. Как и управляющий граф граф программных зависимостей является теоретико-графовой формой промежуточного представления программ в распараллеливающем компиляторе. Другими аналогичными формами являются иерархический граф заданий, идеограф и др. В последних двух зависимости по данным и по управлению рассматриваются совместно.

Литература

  • Векторизация программ: теория, методы, реализация. — М.: Мир, 1991.