Доминатор (теория графов)

Доминатор в теории графов — бинарное отношение на узлах ориентированного графа с выделенным входным узлом, показывающее преимущество при прохождении пути от входного узла: узел $d$ графа доминирует над узлом $n$ (записывается как $d\,\mathrm {dom} \,n$ или $d\gg n$ ), если любой путь от входного узла графа к $n$ проходит через $d$ . В частности, каждый узел доминирует над самим собой.

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

Полезным способом представления информации о доминаторах является дерево, именуемое деревом доминаторов, в котором входной узел является корнем, а каждый узел $d$ доминирует только над своими потомками в дереве[1].

История

Доминирование в информатике впервые ввёл Рис Проссер (Reese T. Prosser) в 1959 году[2], алгоритм вычисления доминирования впервые опубликован спустя 10 лет Лоури и Медлоком (E. S. Lowry, C. W. Medlock)[3]. Возобновление интереса к применению отношения доминирования связано с работой Рона Ситрона (Ron Cytron) 1989 года, в которой это отношение использовано для эффективного вычисления φ-функций, которые используются в SSA-представлении[4].

Свойства отношения

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

Транзитивность: если $a\,\mathrm {dom} \,b$ и $b\,\mathrm {dom} \,c$ , то $a\,\mathrm {dom} \,c$ ,
Антисимметричность: если $a\neq b$ , то невозможно одновременное выполнение $a\,\mathrm {dom} \,b$ и $b\,\mathrm {dom} \,a$ .

Если и $a$ и $b$ являются доминаторами $n$ , то должно выполняться либо $a\,\mathrm {dom} \,b$ , либо $b\,\mathrm {dom} \,a$ . Из этого следует, что каждый узел $n$ за исключением входного должен иметь единственный непосредственный доминатор, то есть доминатор, находящийся ближе всего к $n$ вдоль любого ациклического пути от входного узла до $n$ [5].

Применение

Доминирование используется в компиляторах для формирования SSA-представления. Ряд оптимизаций компилятора может также извлечь выгоду из использования доминаторов. Для автоматического распараллеливания выгодно знать все узлы, над которыми доминирует данный узел. Анализ использования памяти может извлечь выгоду из дерева доминаторов, с помощью которого легко найти утечку и определить излишнее использование памяти. В программных системах, они используются для уменьшения размеров тестового набора[6].

Доминатор импликационного графа ищется в CDCL-решателях задач выполнимости булевых формул при анализе структуры конфликта[7].

Примечания

Компиляторы: принципы, технологии и инструменты, 2008, с. 787.
Prosser, Reese T. Applications of Boolean matrices to the analysis of flow diagrams (англ.) // AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference : journal. — Boston, MA: ACM, 1959. — P. 133—138.
Lowry, Edward S.; and Medlock, Cleburne W. Object code optimization (англ.) // Communications of the ACM : journal. — 1969. — January (vol. 12, no. 1). — P. 13—22.
Cytron, Ron; Hind, Michael; and Hsieh, Wilson. Automatic Generation of DAG Parallelism (неопр.) // Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. — 1989. — С. 54—68.
Компиляторы: принципы, технологии и инструменты, 2008, с. 788.
Dubrova, Elena. Structural Testing Based on Minimum Kernels (неопр.) // Proceedings of Design and Test in Europe Conference. — 2005. — С. 1168—1173.
Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsch. Chapter 4. Conflict-Driven Clause Learning SAT Solvers // Handbook of Satisfiability. — IOS Press, 2008. — P. 135.

Литература

Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструменты = Compilers: Principles, Techniques, and Tools. — Издательский дом "Вильямс", 2008. — ISBN 0-321-48681-1.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_5ee3ed8e22dfdb2b-1] Компиляторы: принципы, технологии и инструменты, 2008, с. 787.

[2] Prosser, Reese T. Applications of Boolean matrices to the analysis of flow diagrams (англ.) // AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference : journal. — Boston, MA: ACM, 1959. — P. 133—138.

[3] Lowry, Edward S.; and Medlock, Cleburne W. Object code optimization (англ.) // Communications of the ACM : journal. — 1969. — January (vol. 12, no. 1). — P. 13—22.

[4] Cytron, Ron; Hind, Michael; and Hsieh, Wilson. Automatic Generation of DAG Parallelism (неопр.) // Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. — 1989. — С. 54—68.

[_5ee3ed8e22dfdb24-5] Компиляторы: принципы, технологии и инструменты, 2008, с. 788.

[6] Dubrova, Elena. Structural Testing Based on Minimum Kernels (неопр.) // Proceedings of Design and Test in Europe Conference. — 2005. — С. 1168—1173.

[7] Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsch. Chapter 4. Conflict-Driven Clause Learning SAT Solvers // Handbook of Satisfiability. — IOS Press, 2008. — P. 135.