Dominator (grafteori)

Dominator i grafteori är en binär relation på noderna i en riktad graf med en framstående ingångsnod, som visar fördelen när man passerar vägen från ingångsnoden: grafnoden dominerar noden (skriven som eller ) om någon väg från grafen ingångsnod till passerar genom . I synnerhet dominerar varje nod sig själv. $d$ $n$ $d\,\mathrm{dom}\,n$ $d \gg n$ $n$ $d$

Den mest utbredda användningen är i kontrollflödesdiagram som används i teorin om kompilatorkonstruktion.

Ett användbart sätt att representera information om dominatorer är ett träd som kallas ett dominatorträd , där ingångsnoden är roten, och varje nod dominerar endast sina barn i trädet [1] . $d$

Historik

Dominans inom datavetenskap introducerades först av Reese T. Prosser 1959 [ 2] , dominansberäkningsalgoritmen publicerades först 10 år senare av Lowry och Medlock ( ES Lowry , CW Medlock ) [3] . Förnyat intresse för användningen av dominansrelationen kommer från Ron Cytrons papper från 1989, som använder denna relation för att effektivt beräkna φ-funktionerna som används i SSA-representationen [4] .

Relationsegenskaper

Den viktigaste observationen om dominatorer är att om vi tar någon acyklisk väg från ingångsnoden till noden , kommer alla dominatorerna att vara placerade på denna väg, dessutom kommer de att vara placerade i samma ordning längs vilken väg som helst. $n$ $n$

Transitivitet : om och , då , $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,c$ $a\,\mathrm{dom}\,c$
Antisymmetri : om , då är samtidig utförande av och omöjlig . $a \neq b$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$

Om och och är dominatorer av , då antingen , eller . Det följer att varje nod utom ingångsnoden måste ha en enda omedelbar dominator, det vill säga dominatorn närmast längs någon acyklisk väg från ingångsnoden till [5] . $a$ $b$ $n$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$ $n$ $n$ $n$

Applikation

Dominans används i kompilatorer för att bilda SSA-representationen . Ett antal kompilatoroptimeringar kan också dra nytta av användningen av dominatorer. För automatisk parallellisering är det fördelaktigt att känna till alla noder som domineras av en given nod. Minnesanvändningsanalys kan dra nytta av ett dominatorträd, vilket gör det enkelt att hitta läckor och identifiera överdriven minnesanvändning. I mjukvarusystem används de för att minska storleken på testsetet [6] .

Dominatorn för implikationsgrafen söks efter i CDCL-lösare av tillfredsställbarhetsproblem för booleska formler vid analys av konfliktstrukturen [7] .

Anteckningar

↑ Kompilatorer: principer, teknologier och verktyg, 2008 , sid. 787.
↑ Prosser, Reese T. Tillämpningar av booleska matriser för analys av flödesdiagram // AFIPS Joint Computer Conferences: Dokument som presenterades vid den 1–3 december 1959, östra gemensamma IRE-AIEE-ACM datorkonferens: tidskrift. - Boston, MA: ACM, 1959. - P. 133-138 .
↑ Lowry, Edward S.; och Medlock, Cleburne W. Objektkodsoptimering // Communications of the ACM : journal. - 1969. - Januari ( vol. 12 , nr 1 ). - S. 13-22 .
↑ Cytron, Ron; Hind, Michael; och Hsieh, Wilson. Automatisk generering av DAG-parallellism (obestämd) // Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. - 1989. - S. 54-68 .
↑ Kompilatorer: principer, teknologier och verktyg, 2008 , sid. 788.
↑ Dubrova, Elena. Strukturell testning baserad på minimala kärnor (obestämd tid) // Konferens för design och test i Europa. - 2005. - S. 1168-1173 .
↑ Armin Biere, Marijn Heule, Hans van Maaren och Toby Walsch. Kapitel 4. Konfliktdriven klausul Inlärning av SAT-lösare // Handbook of Satisfiability. - IOS Press, 2008. - S. 135.

Litteratur

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Compilers: Principles, Techniques and Tools = Compilers: Principles, Techniques and Tools. - Williams Publishing House, 2008. - ISBN 0-321-48681-1 .