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

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

Определение

Дан набор объектов $S$ и транзитивное отношение $R\subseteq S\times S$ с $(a,b)\in R$ моделирование зависимости « a зависит от b » (« a требует сначала оценки b »), граф зависимостей представляет собой граф $G=(S,T)$ с $T\subseteq R$ транзитивная редукция R .

Например, возьмем простой калькулятор. Этот калькулятор поддерживает присвоение постоянных значений переменным и присвоение суммы ровно двух переменных третьей переменной. Учитывая несколько уравнений типа « 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 необходимо вычислить до того, как A. можно будет вычислить Однако значения C и D известны сразу, поскольку они являются числовыми литералами.

Признание невозможных оценок

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

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

Получение заказа на оценку

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

Может быть более одного правильного порядка оценки. На самом деле правильная нумерация — это топологический порядок , а любой топологический порядок — это правильная нумерация. Таким образом, любой алгоритм, который выводит правильный топологический порядок, выводит правильный порядок вычислений.

Предположим еще раз простой калькулятор, показанный выше. Учитывая систему уравнений « A = B + C ; B = 5+ D ; C =4; D =2;», правильный порядок оценки будет ( D , C , B , A ). Однако ( C , D , B , A ) также является правильным порядком вычисления.

Моноидная структура

Граф ациклических зависимостей соответствует следу моноида следа следующим образом: ^[1]^: 12

Функция $\phi :S\to \Sigma$ помечает каждую вершину символом из алфавита $\Sigma$
Есть край $a\to b$ или $b\to a$ тогда и только тогда, когда $(\phi (a),\phi (b))$ находится в отношении зависимости $D$ .
Два графа считаются равными, если их метки и ребра совпадают.

Тогда строка, состоящая из меток вершин, упорядоченных по правильному порядку вычисления, соответствует строке трассы.

операция Моноидальная $(S_{12},R_{12})=(S_{1},R_{1})\bullet (S_{2},R_{2})$ принимает непересекающийся союз $S_{12}=S_{1}\sqcup S_{2}$ наборов вершин двух графов, сохраняет существующие ребра в каждом графе и рисует новые ребра от первого ко второму, где это позволяет отношение зависимости, ^[1]^: 14

R_{12}=R_{1}\sqcup R_{2}\sqcup \{(a,b)\mid a\in S_{1}\land b\in S_{2}\land (\phi (a),\phi (b))\in D\}

Идентичность — это пустой граф.

Примеры

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

Автоматические установщики программного обеспечения . Они ходят по графику в поисках пакетов программного обеспечения необходимых, но еще не установленных . Зависимость определяется связью пакетов .
Скрипты сборки программного обеспечения, такие как Unix Make , установка Node npm, php композитор, установка Twitter Bower или Apache Ant . Им необходимо знать, какие файлы были изменены, поэтому перекомпилировать нужно только правильные файлы.
В технологии компилятора и реализации формального языка :
- Планирование инструкций : графы зависимостей вычисляются для операндов ассемблерных или промежуточных инструкций и используются для определения оптимального порядка инструкций.
- Устранение мертвого кода : если от переменной не зависит никакая побочная операция, эта переменная считается мертвой и может быть удалена.
Динамическая графическая аналитика: GraphBolt ^[2] и Кикстартер ^[3] захватывать зависимости значений для дополнительных вычислений при изменении структуры графа.
Табличные калькуляторы. Им необходимо вывести правильный порядок вычислений, аналогичный тому, который приведен в примере, использованном в этой статье.
Стандарты веб-форм, такие как XForms, чтобы знать, какие визуальные элементы обновлять в случае изменения данных в модели.
Видеоигры, особенно головоломки и приключенческие видеоигры , которые часто представляют собой график зависимых отношений между внутриигровыми действиями. ^[4]

Графы зависимостей являются одним из аспектов:

Типы производственных предприятий : Сырье перерабатывается в продукцию в несколько зависимых этапов.
Планирование рабочего места : Сборник связанных теоретических проблем в области информатики.

См. также

Ссылки

^ Jump up to: ^а ^б Мазуркевич, Антони (1995). «Введение в теорию следов» (PDF) . В Розенберге, Г.; Дикерт, В. (ред.). Книга Следов . Сингапур: World Scientific. ISBN 981-02-2058-8 . Проверено 18 апреля 2021 г.
^ Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: синхронная обработка потоковых графов на основе зависимостей». На Европейской конференции по компьютерным системам (EuroSys'19) . стр. 25:1–25:16. дои : 10.1145/3302424.3303974 .
^ Кеваль Вора; Раджив Гупта; Гоцин Сюй (2017). «KickStarter: быстрые и точные вычисления на потоковых графах с помощью усеченных аппроксимаций». На Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS'17) . стр. 237–251. дои : 10.1145/3093337.3037748 .
^ Гилберт, Рон. «Головоломки с диаграммами зависимостей» . Угрюмый геймер . Проверено 11 января 2020 г.

Балмас, Франсуаза (2001) Отображение графиков зависимостей: иерархический подход. Архивировано 11 февраля 2012 г. в Wayback Machine , [1] wcre, стр. 261, Восьмая рабочая конференция по обратному проектированию (WCRE'01)

[IntroToTraceTheory-1] Jump up to: ^а ^б Мазуркевич, Антони (1995). «Введение в теорию следов» (PDF) . В Розенберге, Г.; Дикерт, В. (ред.). Книга Следов . Сингапур: World Scientific. ISBN 981-02-2058-8 . Проверено 18 апреля 2021 г.

[2] Мугилан Мариаппан; Кеваль Вора (2019). «GraphBolt: синхронная обработка потоковых графов на основе зависимостей». На Европейской конференции по компьютерным системам (EuroSys'19) . стр. 25:1–25:16. дои : 10.1145/3302424.3303974 .

[3] Кеваль Вора; Раджив Гупта; Гоцин Сюй (2017). «KickStarter: быстрые и точные вычисления на потоковых графах с помощью усеченных аппроксимаций». На Международной конференции по архитектурной поддержке языков программирования и операционных систем (ASPLOS'17) . стр. 237–251. дои : 10.1145/3093337.3037748 .

[4] Гилберт, Рон. «Головоломки с диаграммами зависимостей» . Угрюмый геймер . Проверено 11 января 2020 г.

[1]

[2]

[3]

[4]