Тема 04(2016)Доминаторы и постдоминаторы (Лекции)

4. Доминаторы ипостдоминаторы14.1 Доминаторы4.1.1 ОпределениеВ ГПУ вершина d является доминатором вершины n(этот факт записывается как d dom n или d = Dom(n)),если любой путь от вершины Entry до вершины n проходитчерез вершину d.Замечание. Из определения 4.2.1 следует, что каждая вершина nявляется доминатором самой себя, так как путь от Entry до nпроходит через n.24.1 ДоминаторыB14.1.2 Примеры доминаторовРассмотрим ГПУ с входной вершиной B1,показанный на рисунке.является доминаторомвсех узлов, включаяB4себя самого.B2является доминаторомB6только себя самого.B3является доминаторомвсех вершин, кроме B1 иB7B2.B4является доминаторомвсех вершин, кроме B1, B2и B3 .B5 и B6 являются доминаторамитолько себя.B3B2B1B5B8B10B934.1 ДоминаторыB14.1.2 Примеры доминаторовРассмотрим ГПУ с входной вершиной B1,показанный на рисунке.является доминаторомвершин B7, B8, B9 и B10.B8является доминаторомвершин B8, B9 и B10.B9 и B10являются доминаторамитолько себя.B3B2B7B4B6B5B7B8B10B944.1 Доминаторы4.1.3 Свойства отношения dom 1.Отношение dom рефлексивно, антисимметрично итранзитивно, т.е.

является отношением частичного порядка.(1)(2)(3) 2.Рефлексивность: a dom a.Антисимметрчность: если a dom b и b dom а,то a = b.Транзитивность: если a dom b и b dom с, то a dom c.Для любой вершины n ГПУ каждый ациклический путьот Entry до n проходит через все доминаторы n,причем на всех таких путях доминаторы проходятсяв одном и том же порядке54.1 Доминаторы4.1.3 Свойства отношения dom 3.Вершина i ГПУ является непосредственным доминаторомвершины n (i idom n), если(1)i dom n(2)не существует вершины m, m  i, m n,такой что i dom m и m dom n. 4.У каждой вершины n за исключением Entry существуетединственный непосредственный доминатор. 5.Вершина s ГПУ является строгим доминатором вершины n(s sdom n), если s dom n и s n.64.1 Доминаторы4.1.3 Свойства отношения dom 6Пусть n – вершина ГПУ,Pred(n) = {p1, p2, … , pk} и d  n.Тогда d dom n тогда и только тогда, когда  i d dom pi. 7Множество строгих доминаторов вершины n являетсяпересечением множеств доминаторов всех еепредшественников.74.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовЗадача поиска всех доминаторов вершин ГПУ формулируетсякак задача анализа потока данных в прямом направлении.Значением потока данных на входе в блок B является множествовершин (базовых блоков), являющихся доминаторами B.Операцией сбора является операция пересечения множеств.Передаточная функция fB добавляет вершину B крассматриваемому множеству вершин.Граничное условие: единственным доминатором вершиныEntry является она сама.84.1 Доминаторы4.1.4 Алгоритм вычисления доминаторов АлгоритмВход:граф потока G = N, Е с входным узлом Entry.Выход:для каждой вершины n  N множество D(n)ее доминаторов.Метод:найти решение следующей задачи потока данных(вершины n соответствуют базовым блокам):n  ND(n) = Out[Pred(n)].94.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовОбласть определенияМножество подмножеств базовых блоковНаправление обходаForwardПередаточная функцияfB(x) = x {B}Граничное условиеOut [Entry] = EntryОперация сбора ()Система уравненийOut[ B]  f B ( In[ B])In[ B]  Out[ P]PPred ( B )Начальное приближениеOut [B] = N104.1 ДоминаторыB14.1.4 Алгоритм вычисления доминаторов Пример.

Применим алгоритм к ГПУна рисунке в предположении, что блокипосещаются в порядке их номеров, аEntry это блок B1.Pred(B2) = {B1}D(B2) = {B2} D(B1) ={B1, B2}B2B4Первая итерацияГраничное условие: D(B1) = {B1}B3B6B5B7B8B10B9114.1 ДоминаторыB14.1.4 Алгоритм вычисления доминаторов Пример. Применим алгоритм к ГПУна рисунке в предположении, что блокипосещаются в порядке их номеров, аEntry это блок B1.B2B4Первая итерацияГраничное условие: D(B1) = {B1}B3B6Pred(B2) = {B1}D(B2) = {B2} D(B1) ={B1, B2}Pred(B3) = {B1, B2, B4, B8}D(B3) = {B3}  (D(B1)  D(B2) D(B4)  D(B8)) = {B3} ({B1}  {B1, B2}  N  N ) ={B1, B3}N = {B1, B2, B3, B4, B5, B6, B7, B8, B9, B10}B5B7B8B10B9124.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4}  (D(B3)  D(B7)) = {B4}  ({B1, B3}  N ) == {B1, B3, B4}134.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4}  (D(B3)  D(B7)) = {B4}  ({B1, B3}  N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5}  D(B4) = {B5}  {B1, B3, B4} = {B1, B3, B4, B5}D(B6) = {B6}  D(B4) = {B6}  {B1, B3, B4} = {B1, B3, B4, B6}144.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4}  (D(B3)  D(B7)) = {B4}  ({B1, B3}  N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5}  D(B4) = {B5}  {B1, B3, B4} = {B1, B3, B4, B5}D(B6) = {B6}  D(B4) = {B6}  {B1, B3, B4} = {B1, B3, B4, B6}Pred(B7) = {B5, B6, B10}D(B7) = {B7}  (D(B5)  D(B6))  D(B10)) = {B7}  ({B1, B3, B4, B5} = {B1, B3, B4, B6}  N ) = {B1, B3, B4, B7}Pred(B8) = {B7}154.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4}  (D(B3)  D(B7)) = {B4}  ({B1, B3}  N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5}  D(B4) = {B5}  {B1, B3, B4} = {B1, B3, B4, B5}D(B6) = {B6}  D(B4) = {B6}  {B1, B3, B4} = {B1, B3, B4, B6}Pred(B7) = {B5, B6, B10}D(B7) = {B7}  (D(B5)  D(B6))  D(B10)) = {B7}  ({B1, B3, B4, B5} = {B1, B3, B4, B6}  N ) = {B1, B3, B4, B7}Pred(B8) = {B7}D(B8) = {B8}  D(B7) = {B8}  {B1, B3, B4, B7} = {B1, B3, B4, B7, B8}Pred(B9) = Pred(B10) = {B8}D(B9) = {B9}  D(B8) = {B9}  {B1, B3, B4, B7, B8} = {B1, B3,B4, B7,B8,B9}D(B10) = {B10}  D(B8) = {B10}  {B1, B3, B4, B7, B8} == {B1, B3, B4, B7, B8, B10}164.1 Доминаторы4.1.4 Алгоритм вычисления доминаторовПервая итерация (окончание)Pred(B4) = {B3, B7}D(B4) = {B4}  (D(B3)  D(B7)) = {B4}  ({B1, B3}  N ) == {B1, B3, B4}Pred(B5) = Pred(B6) = {B4}D(B5) = {B5}  D(B4) = {B5}  {B1, B3, B4} = {B1, B3, B4, B5}ПолученныезначенияD(B6) = {B6}  D(B4) = {B6}  {B1, B3, B4} = {B1, B3, B4, B6}Pred(B7) = {B5, B6D(B, B101}) – D(B10) на второйитерациине изменяютсяD(B7) = {B7}  (D(BD(B10)) = {B7}  ({B1, B3, B4, B5} 5)  D(B6))= {B1, B3, B4, B6}  N ) = {B1, B3, B4, B7}Pred(B8) = {B7}D(B8) = {B8}  D(B7) = {B8}  {B1, B3, B4, B7} = {B1, B3, B4, B7, B8}Pred(B9) = Pred(B10) = {B8}D(B9) = {B9}  D(B8) = {B9}  {B1, B3, B4, B7, B8} = {B1, B3,B4, B7,B8,B9}D(B10) = {B10}  D(B8) = {B10}  {B1, B3, B4, B7, B8} == {B1, B3, B4, B7, B8, B10}174.1 Доминаторы4.1.5 Непосредственные доминаторы и дерево доминаторовnB1B2B3B4B5B6B7B8B9B10D(n)B1B1, B2B1, B3B1, B3, B4B1, B3, B4, B5B1, B3, B4, B6B1, B3, B4, B7B1, B3, B4, B7, B8B1, B3, B4, B7, B8, B9B1, B3, B4, B7, B8, B10IDom(n)–B1B1B3B4B4B4B7B8B8В таблице приведенысписки доминаторовкаждой вершины ГПУиз рассмотренногопримера.Непосредственныйдоминатор в каждомсписке предпоследний.Соединив дугами длякаждого n  NIDom(n) с n, получимдерево доминаторов.Оно изображено наследующем слайде184.1 Доминаторы4.1.5 Непосредственные доминаторы и дерево доминаторовB1B3B2B1B2B3B4B6B4B5B5B7B6B7B8B8ГПУB10B9B9ДереводоминаторовB10194.2 Граница доминирования4.2.1.

Определение границы доминирования (Dominance Frontier)Определение. Множество узлов m, удовлетворяющих условиям:n является доминатором предшественника mp  Pred(m) & n  Dom(p)(2)n не является строгим доминатором mn  (Dom (m) – {m}).называется границей доминирования n и обозначается DF(n).(1)Неформально: DF(n) содержит все первые узлы, которыедостижимы из n, на любом пути графа потока, проходящемчерез n, но над которыми n не доминирует.204.2 Граница доминирования4.2.1. Определение границы доминированияПример.

На рисунке справаB3  Dom(B4), B3  Dom(B5),B3  Dom(B6),B3  (Dom(B7) – {B7}),т.е. B3 является доминатором B4, B5 и B6,но не является доминатором B7.Более того, на любом пути, выходящем из B3,B7 – первая вершина, для которойB3 не является доминаторомСледовательно, B7  DF(B3)а так как узел B3 не является доминаторомузлов B0, B1 и B2, то DF(B3) = {B7}214.2 Граница доминирования4.2.2. Построение границы доминированияСвойства узлов, входящих в границу доминирования(1)узел, принадлежащий границе доминирования долженбыть точкой сбора графа потока.(2)если j – точка сбора: n  Pred(j) & n  Dom(j),то j  DF(n)т.е. точка сбора j входит в границу доминированиялюбого своего предшественника n, не являющегосядоминатором j.(3)если j – точка сбора:m  Pred(j) & n  Dom(m) & n  Dom(j), то j  DF(n)т.е.

доминаторы предшественников точки сбора j должныиметь j в своих множествах границ доминирования,если только они не доминируют над j.224.2 Граница доминирования4.2.2. Построение границы доминированияСвойства узлов границы доминирования позволяют составитьпростой алгоритм ее построенияШаг 1.Найти все точки сбора j графа потока, т.е. все узлы j, укоторых |Pred(j)| > 1.Шаг 2.Исследовать каждый узел p  Pred(j) и продвинутьсяпо дереву доминаторов, начиная с p и вплоть донепосредственного доминатора j: при этом j входит всостав границы доминирования каждого из пройденныхузлов, за исключением непосредственного доминатора j.234.2 Граница доминирования4.2.3.