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

В информатике узел $d$ графа потока управления доминирует над узлом $n$ , если каждый путь от узла входа до $n$ должен проходить через $d$ . Обозначительно это записывается как $d$ $dom$ $n$ (или иногда $d$ $≫$ $n$ ). По определению, каждый узел доминирует над самим собой.

Существует ряд связанных концепций:

Узел $d$ строго доминирует над узлом $n,$ если $d$ доминирует $над n$ и $d$ не равно $n$ .
Непосредственный доминатор или idom узла n $—$ это уникальный узел, который строго доминирует $над n$ , но не доминирует строго над любым другим узлом, который строго доминирует $над n$ . Каждый узел, за исключением узла входа, имеет непосредственного доминатора. ^[1]
Граница доминирования узла $d$ — это множество всех узлов $n i ,$ таких, что $d$ доминирует над непосредственным предшественником $n i$ , но $d$ не доминирует строго над $n i$ . Это множество узлов, где доминирование d заканчивается $.$
Дерево доминаторов — это дерево , в котором дочерними узлами каждого узла являются те узлы, над которыми он непосредственно доминирует. Начальный узел — это корень дерева.

История

Доминирование было впервые введено Ризом Т. Проссером в статье 1959 года по анализу потоковых диаграмм. ^[2] Проссер не представил алгоритм для вычисления доминирования, который должен был ждать десять лет Эдварда С. Лоури и К. У. Медлока. ^[3] Рон Ситрон и др. возродили интерес к доминированию в 1989 году, когда применили его к проблеме эффективного вычисления размещения функций φ, которые используются в статической форме одиночного присваивания . ^[4]

Приложения

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

Доминаторы играют решающую роль в анализе потока управления, определяя поведение программы, которое имеет отношение к конкретному оператору или операции, что помогает оптимизировать и упростить поток управления программ для анализа. ^[5]

Автоматическое распараллеливание выигрывает от постдоминантных границ. Это эффективный метод вычисления зависимости управления, что имеет решающее значение для анализа.

Анализ использования памяти может выиграть от использования дерева доминаторов, чтобы легко находить утечки и определять высокое использование памяти. ^[6]

В аппаратных системах доминаторы используются для вычисления вероятностей сигналов для генерации тестов, оценки коммутационной активности для анализа мощности и шума, а также выбора точек среза при проверке эквивалентности. ^[7] В программных системах они используются для уменьшения размера тестового набора в методах структурного тестирования, таких как покрытие операторов и ветвей. ^[8]

Алгоритмы

Пусть будет исходным узлом на графе потока управления . Доминаторы узла задаются максимальным решением следующих уравнений потока данных: $n_{0}$ $n$

\operatorname {Dom} (n)={\begin{cases}\left\{n\right\}&{\mbox{ if }}n=n_{0}\\\left\{n\right\}\cup \left(\bigcap _{p\in {\text{preds}}(n)}^{}\operatorname {Dom} (p)\right)&{\mbox{ if }}n\neq n_{0}\end{cases}}

Доминатор начального узла — это сам начальный узел. Набор доминаторов для любого другого узла — это пересечение набора доминаторов для всех предшественников . Узел также входит в набор доминаторов для . $n$ $p$ $n$ $n$ $n$

Алгоритм прямого решения:

// доминант начального узла — это сам старт Дом(n ₀ ) = {n ₀ } // для всех остальных узлов, сделать все узлы доминирующими для каждого n в N - {n ₀ } Дом(n) = N; // итеративно исключаем узлы, которые не являются доминирующими в то время как изменения в любом Dom(n) для каждого n из N - {n ₀ }: Dom(n) = {n} объединение с пересечением по Dom(p) для всех p из pred(n)

Прямое решение квадратично по числу узлов, или O( n ² ). Ленгауэр и Тарьян разработали алгоритм, который почти линейный, ^[1] и на практике, за исключением нескольких искусственных графов, алгоритм и его упрощенная версия так же быстры или быстрее, чем любой другой известный алгоритм для графов всех размеров, и его преимущество увеличивается с размером графа. ^[9]

Кит Д. Купер , Тимоти Дж. Харви и Кен Кеннеди из Университета Райса описывают алгоритм, который по сути решает приведенные выше уравнения потока данных, но использует хорошо спроектированные структуры данных для повышения производительности. ^[10]

Постдоминирование

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

Смотрите также

Ссылки

^ ab Lengauer, Thomas ; Tarjan, Robert Endre (июль 1979). "Быстрый алгоритм поиска доминаторов в потоковом графе". ACM Transactions on Programming Languages and Systems . 1 (1): 121–141. CiteSeerX 10.1.1.117.8843 . doi :10.1145/357062.357071. S2CID 976012.
^ Проссер, Риз Т. (1959). «Применение булевых матриц к анализу потоковых диаграмм». Объединенные компьютерные конференции AFIPS: доклады, представленные на Восточной объединенной компьютерной конференции IRE-AIEE-ACM 1–3 декабря 1959 г. IRE-AIEE-ACM '59 (Восточная): 133–138. doi :10.1145/1460299.1460314. S2CID 15546681.
^ Lowry, Edward S.; Medlock, Cleburne W. (январь 1969). «Оптимизация объектного кода». Communications of the ACM . 12 (1): 13–22. doi : 10.1145/362835.362838 . S2CID 16768560.
^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; Zadeck, F. Kenneth (1989). "Эффективный метод вычисления статической формы одиночного присваивания". Труды 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '89 . POPL '89. стр. 25–35. doi :10.1145/75277.75280. ISBN 0897912942. S2CID 8301431.
^ Тамрави, Ахмед; Котари, Суреш (2018-10-01). «Проецируемый граф управления для вычисления соответствующих поведений программ». Наука компьютерного программирования . 163 : 93–114. doi :10.1016/j.scico.2018.04.003. ISSN 0167-6423.
^ "Dominator Tree". eclipse.org . SAP AG и IBM Corporation. 2012 [2008] . Получено 21 июня 2013 г. .
^ Тесленко, Максим; Дуброва, Елена (2005). "Эффективный алгоритм поиска доминаторов с двойной вершиной в графах цепей". Проектирование, автоматизация и тестирование в Европе. Дата '05. С. 406–411. CiteSeerX 10.1.1.598.3053 . doi :10.1109/DATE.2005.53. ISBN 9780769522883. S2CID 10305833.
^ Дуброва, Елена (2005). «Структурное тестирование на основе минимальных ядер». Проектирование, автоматизация и тестирование в Европе . Дата '05. С. 1168–1173. CiteSeerX 10.1.1.583.5547 . doi :10.1109/DATE.2005.284. ISBN 9780769522883. S2CID 11439732.
^ Георгиадис, Лукас; Тарьян, Роберт Э .; Вернек, Ренато Ф. (2006). «Поиск доминаторов на практике» (PDF) . Архивировано из оригинала (PDF) 15 апреля 2024 г.
^ Купер, Кит Д .; Харви, Тимоти Дж.; Кеннеди, Кен (2001). «Простой, быстрый алгоритм доминирования» (PDF) .

Внешние ссылки

Библиотека анализа потока управления Machine-SUIF