1 | дом | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
2 | дом | 2 | 3 | 4 | 5 | 6 | |
3 | дом | 3 | |||||
4 | дом | 4 | |||||
5 | дом | 5 | |||||
6 | дом | 6 | |||||
Соответствующее отношение господства | |||||||
Серые узлы строго не доминируют | |||||||
Красные узлы сразу преобладают |
В информатике , в графах потока управления , узел d доминирует узел п , если каждый путь от узла ввода в п должен пройти через д . Условно это записывается как d dom n (или иногда d п ). По определению, каждый узел доминирует над собой.
Есть ряд связанных понятий:
- Узел d строго доминирует над узлом n, если d доминирует над n и d не равно n .
- Немедленный доминатор или IDOM узла п является единственным узлом , который строго доминирует п , но не доминируют строго над любым другим узлом , который строго доминирует над п . У каждого узла, кроме входного, есть непосредственный доминант. [1]
- Доминирование границы из узла д представляет собой набор всех узлов п я такое , что d доминирует непосредственный предшественник п I , но д не доминирует строго над п я . Это набор узлов, в которых доминирование d прекращается.
- Доминатор дерево представляет собой дерево , где дети каждого узла являются теми узлами , он сразу же доминирует. Поскольку непосредственный господин уникален, это дерево. Начальный узел - это корень дерева.
История
Доминирование было впервые введено Риз Т. Проссер в статье 1959 года об анализе блок-схем. [2] Проссер не представил алгоритм для вычисления доминирования, которому пришлось ждать десять лет Эдварда С. Лоури и К.У. Медлока. [3] Рон Цитрон и др. возродили интерес к доминированию в 1989 году, когда они применили его к проблеме эффективного вычисления размещения функций φ, которые используются в статической форме с одним присваиванием . [4]
Приложения
Доминаторы и, в частности, границы доминирования имеют приложения в компиляторах для вычисления статической формы единственного присваивания . Некоторые оптимизации компилятора также могут выиграть от доминирования. Блок-граф в этом случае состоит из базовых блоков .
Автоматическое распараллеливание извлекает выгоду из границ постдоминирования. Это эффективный метод вычисления зависимости управления, который имеет решающее значение для анализа.
Для анализа использования памяти может быть полезно использовать дерево доминирования, чтобы легко находить утечки и определять высокий уровень использования памяти. [5]
В аппаратных системах доминаторы используются для вычисления вероятностей сигналов для генерации тестов, оценки коммутационных действий для анализа мощности и шума и выбора точек отсечки при проверке эквивалентности. [6] В программных системах они используются для уменьшения размера набора тестов в таких методах структурного тестирования, как покрытие операторов и переходов. [7]
Алгоритмы
Позволять быть исходным узлом на графе потока управления . Доминаторы узла даются максимальным решением следующих уравнений потока данных:
Доминирующим элементом начального узла является сам начальный узел. Набор доминаторов для любого другого узла является пересечением множества доминаторов для всех предшественников из . Узел также входит в набор доминаторов для .
Алгоритм прямого решения:
// доминирующим элементом стартового узла является сам старт Dom (n 0 ) = {n 0 } // для всех остальных узлов установить все узлы как доминирующие для каждого n в N - {n 0 } Dom (n) = N; // итеративно удаляем узлы, которые не являются доминирующими в то время как изменения в любом Dom (n) для каждого n в N - {n 0 }: Dom (n) = {n} объединение с пересечением над Dom (p) для всех p в pred (n)
Прямое решение квадратично по числу узлов, или O ( n 2 ). Ленгауэр и Тарьян разработали алгоритм, который является почти линейным, [1] и на практике, за исключением нескольких искусственных графов, алгоритм и его упрощенная версия так же быстры или быстрее, чем любой другой известный алгоритм для графов всех размеров и их преимущество увеличивается с размером графа. [8]
Кейт Д. Купер , Тимоти Дж. Харви и Кен Кеннеди из Университета Райса описывают алгоритм, который по существу решает приведенные выше уравнения потока данных, но использует хорошо спроектированные структуры данных для повышения производительности. [9]
Постдоминирование
По аналогии с определением доминирования выше, узел z считается пост-доминирующим над узлом n, если все пути к выходному узлу графа, начинающемуся с n, должны проходить через z . Точно так же непосредственный постдоминатор узла n - это постдоминатор узла n , который строго не постдоминирует какие-либо другие строгие постдоминаторы узла n .
Смотрите также
Рекомендации
- ^ а б Ленгауэр, Томас ; Тарджан, Роберт Эндре (июль 1979 г.). «Быстрый алгоритм поиска доминаторов в потоковом графе». Транзакции ACM по языкам и системам программирования . 1 (1): 121–141. CiteSeerX 10.1.1.117.8843 . DOI : 10.1145 / 357062.357071 .
- ^ Проссер, Риз Т. (1959). «Приложения булевых матриц к анализу блок-схем» . Совместные компьютерные конференции AFIPS: доклады, представленные на 1–3 декабря 1959 г., Восточную объединенную компьютерную конференцию IRE-AIEE-ACM . IRE-AIEE-ACM '59 (Восточный): 133–138. DOI : 10.1145 / 1460299.1460314 .
- ^ Лоури, Эдвард С .; Медлок, Клеберн В. (январь 1969 г.). «Оптимизация объектного кода». Коммуникации ACM . 12 (1): 13–22. DOI : 10.1145 / 362835.362838 .
- ^ Ситрон, Рон; Ферранте, Жанна; Розен, Барри К .; Wegman, Mark N .; Задек, Ф. Кеннет (1989). «Эффективный метод вычисления статической формы единого присвоения» . Материалы 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования . POPL '89: 25–35. DOI : 10.1145 / 75277.75280 . ISBN 0897912942.
- ^ «Дерево Доминатора» . 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.
- ^ Дуброва, Елена (2005). Структурное тестирование на основе минимальных ядер . Труды конференции по проектированию и испытаниям в Европе . Дата '05. С. 1168–1173. CiteSeerX 10.1.1.583.5547 . DOI : 10.1109 / DATE.2005.284 . ISBN 9780769522883.
- ^ Георгиадис, Лукас; Тарджан, Роберт Э .; Вернек, Ренато Ф. (2006). «Поиск доминаторов на практике» (PDF) .
- ^ Купер, Кейт Д .; Харви, Тимоти Дж; Кеннеди, Кен (2001). «Простой и быстрый алгоритм доминирования» (PDF) .
Внешние ссылки
- Библиотека анализа потока управления Machine-SUIF