Граф зависимостей

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Граф зависимостей — ориентированный граф, отображающий соотношение элементов некоторой совокупности в соответствии с выбранным транзитивным отношением над ней. Широко применяется в информатике и цифровой электронике, в частности, по графу зависимостей определяется порядок вычислений или его недостатки, согласованные с данными зависимостями в графе.

Определение[править | править вики-текст]

Dependencygraph.png

Пусть дано множество объектов S и отношение транзитивности R = S \times S где (a,b) \in R, моделирующее зависимость «для вычисления a нужно сначала вычислить b», тогда граф зависимостей — это граф G = (S, T) где T \subseteq R и R является транзитивным замыканием T.

Например, некоторый калькулятор поддерживает запись константы в некоторую переменную и сложение двух переменных с записью результата в некоторую третью переменную. Пусть дано несколько выражений, например, A = B + C; B = 5 + D; C = 4; D = 2. Тогда S={A,B,C,D} и R={(A,B),(A,C),(B,D)}. Можно явно вывести все отношения: A зависит B и C, потому что две переменные можно складывать тогда и только тогда, когда известны значения обеих переменных. Таким образом, B и C должны быть вычислены перед A. Однако, значение D известно сразу, потому что это числовая константа.

Обнаружение невозможных вычислений[править | править вики-текст]

Циклические зависимости в графе зависимостей приводят к ситуации, в которой нет доступного порядка вычислений, потому что ни один из объектов цикла не может считаться первым. Если циклических зависимостей нет, то мы имеем направленный ациклический граф, и порядок вычислений может быть определен с помощью топологической сортировки. Большинство алгоритмов топологической сортировки способны обнаруживать циклы на входе, однако, желательно обнаруживать циклы отдельно от топологической сортировки.

В примере на основе калькулятора, вычислительная система A=B; B=D+C; C=D+A; D=12 содержит циклическую зависимость. B должно быть вычислено до A, C должно быть вычислено до B, A должно быть вычислено до C.

Определение порядка вычислений[править | править вики-текст]

Корректный порядок вычислений — это нумерация  n : S \rightarrow N объектов, которая упорядочивает узлы графа зависимостей так, что имеет место равенство:  n(a) < n(b) \Rightarrow (a, b) \notin R , где  a, b \in S. Это означает, что если нумераций определяется, что а вычисляется перед b, то а не может зависеть от b. Более того, может существовать более одного корректного порядка вычислений. По сути, корректная нумерация является топологической сортировкой, и любая топологическая сортировка является корректной нумерацией. На самом деле, любой алгоритм, производящий корректную топологическую сортировку, одновременно определяет корректный порядок вычисления.

Для системы (в примере с калькулятором) A = B+C; B = 5+D; C=4; D=2 корректный порядок: (D, C, B, A), однако, (C, D, B, A) также является корректным порядком вычислений.

Примеры[править | править вики-текст]

Граф зависимостей используется в:

  • Планирование инструкций. Граф зависимостей вычисляется для операндов ассемблера или промежуточных инструкций и используется для определения оптимального порядка инструкций.
  • Удаление мёртвого кода.

Графы зависимости это один из вопросов:

  • Теории ограничений. Исходные данные перерабатываются в результирующие в ходе нескольких зависимых этапов.
  • Планирования. Набор взаимосвязанных теоретических проблем в области компьютерных наук.

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]