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

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

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

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

История

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

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

Ключевое наблюдение, касающееся доминаторов, заключается в том, что если мы возьмем любой ациклический путь от входного узла к узлу $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$.

Применение

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

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

Литература

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