Dominator (teoria graficelor)

Dominator în teoria grafurilor este o relație binară pe nodurile unui graf direcționat cu un nod de intrare distins, arătând avantajul atunci când treceți calea de la nodul de intrare: nodul graf domină nodul (scris ca sau ) dacă există vreo cale din graf nodul de intrare care trece prin . În special, fiecare nod se domină pe sine. $d$ $n$ $d\,\mathrm{dom}\,n$ $d \gg n$ $n$ $d$

Cea mai răspândită utilizare este în graficele de flux de control utilizate în teoria construcției compilatorului.

O modalitate utilă de a reprezenta informații despre dominatori este un arbore numit arbore dominator , unde nodul de intrare este rădăcina, iar fiecare nod domină doar copiii săi în arbore [1] . $d$

Istorie

Dominanța în informatică a fost introdusă pentru prima dată de Reese T. Prosser în 1959 [2] , algoritmul de calcul al dominanței a fost publicat pentru prima dată 10 ani mai târziu de către Lowry și Medlock ( ES Lowry , CW Medlock ) [3] . Interesul reînnoit pentru utilizarea relației de dominanță vine din lucrarea lui Ron Cytron din 1989, care utilizează această relație pentru a calcula eficient funcțiile φ care sunt utilizate în reprezentarea SSA [4] .

Proprietăți ale relației

Observația cheie despre dominatori este că, dacă luăm orice cale aciclică de la nodul de intrare la nod , atunci toți dominatorii vor fi localizați pe această cale, în plus, ei vor fi localizați în aceeași ordine de-a lungul oricărei căi. $n$ $n$

Tranzitivitate : dacă și , atunci , $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,c$ $a\,\mathrm{dom}\,c$
Antisimetrie : dacă , atunci executarea simultană a și este imposibilă . $a \neq b$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$

Dacă și și sunt dominatori ai , atunci fie , fie . Rezultă că fiecare nod , cu excepția nodului de intrare, trebuie să aibă un singur dominator imediat, adică dominatorul cel mai apropiat de-a lungul oricărei căi aciclice de la nodul de intrare la [5] . $A$ $b$ $n$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$ $n$ $n$ $n$

Aplicație

Dominanța este folosită în compilatoare pentru a forma reprezentarea SSA . Un număr de optimizări ale compilatorului pot beneficia, de asemenea, de utilizarea dominatorilor. Pentru paralelizarea automată, este benefic să cunoaștem toate nodurile dominate de un anumit nod. Analiza utilizării memoriei poate beneficia de un arbore dominator, ceea ce facilitează identificarea scurgerilor și identificarea utilizării excesive a memoriei. În sistemele software, acestea sunt utilizate pentru a reduce dimensiunea setului de testare [6] .

Dominatorul grafului de implicație este căutat în CDCL-rezolvatorii de probleme de satisfacție pentru formule booleene la analiza structurii conflictului [7] .

Note

↑ Compilatorii: principii, tehnologii și instrumente, 2008 , p. 787.
↑ Prosser, Reese T. Applications of Boolean matrices to the analysis of flow diagrams // AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, Eastern joint IRE-AIEE-ACM computer Conference : journal. - Boston, MA: ACM, 1959. - P. 133-138 .
↑ Lowry, Edward S.; și Medlock, Cleburne W. Optimizarea codului obiect // Communications of the ACM : journal. - 1969. - ianuarie ( vol. 12 , nr. 1 ). - P. 13-22 .
↑ Cytron, Ron; Hind, Michael; și Hsieh, Wilson. Generarea automată a paralelismului DAG (nedefinită) // Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. - 1989. - S. 54-68 .
↑ Compilatorii: principii, tehnologii și instrumente, 2008 , p. 788.
↑ Dubrova, Elena. Testare structurală pe bază de nuclee minime (nedefinită) // Conferința Proceedings of Design and Test in Europe. - 2005. - S. 1168-1173 .
↑ Armin Biere, Marijn Heule, Hans van Maaren și Toby Walsch. Capitolul 4. Învățarea clauzelor determinate de conflicte SAT Solvers // Manual de satisfacție. - IOS Press, 2008. - P. 135.

Literatură

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilatoare: principii, tehnici și instrumente = Compilers: Principles, Techniques, and Tools. - Editura Williams, 2008. - ISBN 0-321-48681-1 .