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

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

Доминатор в теории графов — бинарное отношение на узлах ориентированного графа с выделенным входным узлом, показывающее преимущество при прохождении пути от входного узла: узел 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].

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

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

Свойства отношения[править | править вики-текст]

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

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

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

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

  1. Компиляторы: принципы, технологии и инструменты, 2008, с. 787
  2. Prosser, Reese T. (1959). «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 (ACM): 133–138.
  3. Lowry, Edward S.; and Medlock, Cleburne W. (January 1969). «Object code optimization». Communications of the ACM 12 (1): 13–22.
  4. Cytron, Ron; Hind, Michael; and Hsieh, Wilson (1989). «Automatic Generation of DAG Parallelism». Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation: 54–68. Шаблон:Citeseerx.
  5. Dubrova, Elena (2005). «Structural Testing Based on Minimum Kernels». Proceedings of Design and Test in Europe Conference: 1168–1173.
  6. Компиляторы: принципы, технологии и инструменты, 2008, с. 788

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

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