Граф программных зависимостей: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Граф программных зависимостей''' (''Program dependence graph'') - орграф, вершины которо...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Граф программных зависимостей''' (''Program dependence graph'') | '''Граф программных зависимостей''' (''[[Program dependence graph]]'') — [[орграф]], [[вершина|вершины]] которого суть операторы и предикаты программы и в котором две вершины <math>S</math> и <math>T</math> соединены [[дуга|дугой]] <math>(S,T)</math> в том и только том случае, если оператор <math>T</math> зависит (по данным или по управлению) от оператора <math>S</math>. Для удобства представляется в виде двух [[подграф|подграфов]]: подграфа зависимостей по управлению и подграфа зависимостей по данным. Как и [[управляющий граф]] '''граф программных зависимостей''' является теоретико-графовой формой промежуточного представления программ в распараллеливающем компиляторе. Другими аналогичными формами являются иерархический граф заданий, идеограф и др. В последних двух зависимости по данным и по управлению рассматриваются совместно. | ||
орграф, вершины которого суть операторы и предикаты программы и в | |||
котором | |||
две вершины <math>S</math> и <math>T</math> соединены дугой <math>(S,T)</math> в том и только том | |||
случае, если оператор <math>T</math> зависит (по данным или по управлению) | |||
от оператора <math>S</math>. Для удобства представляется в виде двух подграфов: | |||
подграфа зависимостей по управлению и подграфа зависимостей по данным. | |||
Как и управляющий граф ''' | |||
промежуточного представления программ в распараллеливающем | |||
компиляторе. Другими аналогичными формами являются иерархический граф | |||
заданий, идеограф и др. В последних двух зависимости по данным и по | |||
управлению рассматриваются совместно. | |||
==Литература== | ==Литература== | ||
* Векторизация программ: теория, методы, реализация. — М.: Мир, 1991. | |||
Текущая версия от 16:48, 1 февраля 2011
Граф программных зависимостей (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.