Доминатор (теория графов)
1 | дом | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
2 | дом | 2 | 3 | 4 | 5 | 6 | |
3 | дом | 3 | |||||
4 | дом | 4 | |||||
5 | дом | 5 | |||||
6 | дом | 6 | |||||
Соответствующее отношение доминирования: Серые узлы не доминируют строго Красные узлы сразу доминируют |
В информатике узел d должен доминирует графа потока управления над узлом n , если каждый путь от входного узла до n проходить через d . Условно это записывается как d dom n (или иногда d ≫ n ). По определению, каждый узел доминирует сам над собой.
Существует ряд связанных понятий:
- Узел d строго доминирует над узлом n, если d доминирует над n и d не равен n .
- или Непосредственный доминатор идом узла n — это уникальный узел, который строго доминирует над n, но не строго доминирует над каким-либо другим узлом, который строго доминирует над n . У каждого узла, кроме входного, есть непосредственный доминатор. [1]
- Граница доминирования узла d — это набор всех узлов n i таких, что d доминирует над непосредственным предшественником узла n i , но d не доминирует строго над n i . Это набор узлов, где . доминирование d прекращается
- Дерево -доминатор — это дерево , в котором дочерними узлами каждого узла являются те узлы, над которыми оно непосредственно доминирует. Начальный узел является корнем дерева.
История
[ редактировать ]Доминирование было впервые представлено Риз Т. Проссер в статье 1959 года об анализе блок-схем. [2] Проссер не представил алгоритм вычисления доминирования, которого Эдварду С. Лоури и К. У. Медлоку пришлось ждать десять лет. [3] Рон Сайтрон и др. возобновили интерес к доминированию в 1989 году, когда они применили его к проблеме эффективного вычисления размещения φ-функций, которые используются в статической форме с одним присваиванием . [4]
Приложения
[ редактировать ]Доминаторы и, в частности, границы доминирования находят применение в компиляторах для вычисления статической формы одиночного присваивания . Ряд оптимизаций компилятора также могут выиграть от доминаторов. Граф потока в этом случае состоит из базовых блоков .
Доминаторы играют решающую роль в анализе потока управления, определяя поведение программы, соответствующее конкретному оператору или операции, что помогает оптимизировать и упростить поток управления программами для анализа. [5]
Автоматическое распараллеливание выигрывает от границ постдоминирования. Это эффективный метод расчета зависимости управления, который имеет решающее значение для анализа.
Анализ использования памяти может помочь с использованием дерева доминаторов, позволяющего легко находить утечки и выявлять высокий уровень использования памяти. [6]
В аппаратных системах доминаторы используются для вычисления вероятностей сигналов для генерации тестов, оценки активности переключения для анализа мощности и шума, а также выбора точек отсечения при проверке эквивалентности. [7] В программных системах они используются для уменьшения размера набора тестов в методах структурного тестирования, таких как покрытие операторов и ветвей. [8]
Алгоритмы
[ редактировать ]Позволять быть исходным узлом на графе потока управления . Доминаторы узла даются максимальным решением следующих уравнений потока данных:
Доминатором начального узла является сам начальный узел. Набор доминаторов для любого другого узла является пересечением множества доминаторов для всех предшественников из . Узел также входит в набор доминаторов для .
Алгоритм прямого решения:
// dominator of the start node is the start itself Dom(n0) = {n0} // for all other nodes, set all nodes as the dominators for each n in N - {n0} Dom(n) = N; // iteratively eliminate nodes that are not dominators while changes in any Dom(n) for each n in N - {n0}: Dom(n) = {n} union with intersection over Dom(p) for all p in pred(n)
Прямое решение квадратично по числу узлов, или O( n 2 ). Ленгауэр и Тарьян разработали алгоритм, который является почти линейным. [1] и на практике, за исключением нескольких искусственных графов, этот алгоритм и его упрощенная версия работают так же быстро или даже быстрее, чем любой другой известный алгоритм для графов всех размеров, и его преимущество увеличивается с размером графа. [9]
Кит Д. Купер , Тимоти Дж. Харви и Кен Кеннеди из Университета Райса описывают алгоритм, который по существу решает приведенные выше уравнения потока данных, но использует хорошо спроектированные структуры данных для повышения производительности. [10]
Постдоминирование
[ редактировать ]Аналогично определению доминирования, приведенному выше, узел z говорят, что пост-доминирует над узлом n, если все пути к выходному узлу графа, начинающиеся с n, должны проходить через z . Аналогично, непосредственный постдоминатор узла n — это постдоминатор узла n , который не строго постдоминирует над любыми другими строгими постдоминаторами узла n .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Ленгауэр, Томас ; Тарьян, Роберт Эндре (июль 1979 г.). «Быстрый алгоритм поиска доминаторов в блок-графе». Транзакции ACM в языках и системах программирования . 1 (1): 121–141. CiteSeerX 10.1.1.117.8843 . дои : 10.1145/357062.357071 . S2CID 976012 .
- ^ Проссер, Риз Т. (1959). «Применение булевых матриц для анализа блок-схем» . Совместные компьютерные конференции AFIPS: доклады, представленные на Восточной совместной компьютерной конференции IRE-AIEE-ACM 1–3 декабря 1959 г. IRE-AIEE-ACM '59 (Восточный): 133–138. дои : 10.1145/1460299.1460314 . S2CID 15546681 .
- ^ Лоури, Эдвард С.; Медлок, Клеберн В. (январь 1969 г.). «Оптимизация объектного кода» . Коммуникации АКМ . 12 (1): 13–22. дои : 10.1145/362835.362838 . S2CID 16768560 .
- ^ Сайтрон, Рон; Ферранте, Жанна; Розен, Барри К.; Вегман, Марк Н.; Задек, Ф. Кеннет (1989). «Эффективный метод вычисления статической формы одиночного присваивания» . Материалы 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '89 . ПОПЛ '89. стр. 25–35. дои : 10.1145/75277.75280 . ISBN 0897912942 . S2CID 8301431 .
- ^ Тамрави, Ахмед; Котари, Суреш (01 октября 2018 г.). «Проецируемый граф управления для расчета соответствующего поведения программы» . Наука компьютерного программирования . 163 : 93–114. дои : 10.1016/j.scico.2018.04.003 . ISSN 0167-6423 .
- ^ «Дерево Доминатора» . eclipse.org . SAP AG и корпорация IBM. 2012 [2008] . Проверено 21 июня 2013 г.
- ^ Тесленко Максим; Дуброва, Елена (2005). «Эффективный алгоритм поиска двухвершинных доминаторов в цепных графах». Проектирование, автоматизация и тестирование в Европе . Дата '05. стр. 406–411. CiteSeerX 10.1.1.598.3053 . дои : 10.1109/ДАТА.2005.53 . ISBN 9780769522883 . S2CID 10305833 .
- ^ Дуброва, Елена (2005). «Структурное тестирование на основе минимального количества ядер» . Проектирование, автоматизация и тестирование в Европе . Дата '05. стр. 1168–1173. CiteSeerX 10.1.1.583.5547 . дои : 10.1109/ДАТА.2005.284 . ISBN 9780769522883 . S2CID 11439732 .
- ^ Георгиадис, Лукас; Тарьян, Роберт Э .; Вернек, Ренато Ф. (2006). «Нахождение доминаторов на практике» (PDF) .
- ^ Купер, Кейт Д .; Харви, Тимоти Дж; Кеннеди, Кен (2001). «Простой и быстрый алгоритм доминирования» (PDF) .