Jump to content

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

Пример графа потока управления с входным узлом 1
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 .

См. также

[ редактировать ]
  1. ^ Перейти обратно: а б Ленгауэр, Томас ; Тарьян, Роберт Эндре (июль 1979 г.). «Быстрый алгоритм поиска доминаторов в блок-графе». Транзакции ACM в языках и системах программирования . 1 (1): 121–141. CiteSeerX   10.1.1.117.8843 . дои : 10.1145/357062.357071 . S2CID   976012 .
  2. ^ Проссер, Риз Т. (1959). «Применение булевых матриц для анализа блок-схем» . Совместные компьютерные конференции AFIPS: доклады, представленные на Восточной совместной компьютерной конференции IRE-AIEE-ACM 1–3 декабря 1959 г. IRE-AIEE-ACM '59 (Восточный): 133–138. дои : 10.1145/1460299.1460314 . S2CID   15546681 .
  3. ^ Лоури, Эдвард С.; Медлок, Клеберн В. (январь 1969 г.). «Оптимизация объектного кода» . Коммуникации АКМ . 12 (1): 13–22. дои : 10.1145/362835.362838 . S2CID   16768560 .
  4. ^ Сайтрон, Рон; Ферранте, Жанна; Розен, Барри К.; Вегман, Марк Н.; Задек, Ф. Кеннет (1989). «Эффективный метод вычисления статической формы одиночного присваивания» . Материалы 16-го симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования - POPL '89 . ПОПЛ '89. стр. 25–35. дои : 10.1145/75277.75280 . ISBN  0897912942 . S2CID   8301431 .
  5. ^ Тамрави, Ахмед; Котари, Суреш (01 октября 2018 г.). «Проецируемый граф управления для расчета соответствующего поведения программы» . Наука компьютерного программирования . 163 : 93–114. дои : 10.1016/j.scico.2018.04.003 . ISSN   0167-6423 .
  6. ^ «Дерево Доминатора» . eclipse.org . SAP AG и корпорация IBM. 2012 [2008] . Проверено 21 июня 2013 г.
  7. ^ Тесленко Максим; Дуброва, Елена (2005). «Эффективный алгоритм поиска двухвершинных доминаторов в цепных графах». Проектирование, автоматизация и тестирование в Европе . Дата '05. стр. 406–411. CiteSeerX   10.1.1.598.3053 . дои : 10.1109/ДАТА.2005.53 . ISBN  9780769522883 . S2CID   10305833 .
  8. ^ Дуброва, Елена (2005). «Структурное тестирование на основе минимального количества ядер» . Проектирование, автоматизация и тестирование в Европе . Дата '05. стр. 1168–1173. CiteSeerX   10.1.1.583.5547 . дои : 10.1109/ДАТА.2005.284 . ISBN  9780769522883 . S2CID   11439732 .
  9. ^ Георгиадис, Лукас; Тарьян, Роберт Э .; Вернек, Ренато Ф. (2006). «Нахождение доминаторов на практике» (PDF) .
  10. ^ Купер, Кейт Д .; Харви, Тимоти Дж; Кеннеди, Кен (2001). «Простой и быстрый алгоритм доминирования» (PDF) .
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 0e05916c1995ca5f71dade420377ecc9__1722028860
URL1:https://arc.ask3.ru/arc/aa/0e/c9/0e05916c1995ca5f71dade420377ecc9.html
Заголовок, (Title) документа по адресу, URL1:
Dominator (graph theory) - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)