Dominator (gráfelmélet)

A dominátor a gráfelméletben egy bináris reláció egy megkülönböztetett bemeneti csomóponttal rendelkező irányított gráf csomópontjain, amely megmutatja az előnyt a bemeneti csomóponttól való útvonal áthaladásakor: a gráf csomópontja uralja a csomópontot ( vagy ként írva ), ha van olyan út a gráfból. bemeneti csomópont áthalad . Különösen minden csomópont önmagát uralja. $d$ $n$ $d\,\mathrm{dom}\,n$ $d \gg n$ $n$ $d$

A legelterjedtebb a fordítói konstrukció elméletében használt vezérlési folyamatgráfok alkalmazása.

A dominátorokkal kapcsolatos információk megjelenítésének hasznos módja egy dominátorfának nevezett fa , ahol a bemeneti csomópont a gyökér, és minden csomópont csak a gyermekeit uralja a fában [1] . $d$

Történelem

A dominanciát a számítástechnikában először Reese T. Prosser vezette be 1959 -ben [2] , a dominanciaszámítási algoritmust 10 évvel később tette közzé először Lowry és Medlock ( ES Lowry , CW Medlock ) [3] . A dominancia reláció alkalmazása iránti érdeklődés Ron Cytron 1989-es cikkéből származik , amely ezt a relációt használja az SSA-reprezentációban használt φ-függvények hatékony kiszámítására [4] .

Kapcsolat tulajdonságai

A dominátorokkal kapcsolatos legfontosabb észrevétel az, hogy ha bármilyen aciklikus utat választunk a bemeneti csomóponttól a csomópontig , akkor az összes dominátor ezen az úton fog elhelyezkedni, sőt, bármely útvonal mentén ugyanabban a sorrendben. $n$ $n$

Tranzitivitás : ha és , akkor , $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,c$ $a\,\mathrm{dom}\,c$
Antiszimmetria : ha , akkor a és egyidejű végrehajtása lehetetlen . $a \neq b$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$

Ha és és a dominátorai , akkor vagy , vagy . Ebből az következik, hogy a bemeneti csomópont kivételével minden csomópontnak egyetlen közvetlen dominátorral kell rendelkeznie, vagyis a bemeneti csomóponttól [5] -ig tartó bármely aciklikus útvonalhoz legközelebb eső dominátorral . $a$ $b$ $n$ $a\,\mathrm{dom}\,b$ $b\,\mathrm{dom}\,a$ $n$ $n$ $n$

Alkalmazás

A dominanciát a fordítókban használják az SSA reprezentáció kialakítására . Számos fordítóoptimalizálás is előnyös lehet a dominátorok használatából. Az automatikus párhuzamosításhoz előnyös, ha ismerjük az adott csomópont által dominált összes csomópontot. A memóriahasználat elemzése előnyös lehet egy dominátorfából, amely megkönnyíti a szivárgások megtalálását és a túlzott memóriahasználat azonosítását. Szoftverrendszerekben a teszthalmaz méretének csökkentésére használják [6] .

Az implikációs gráf dominánsát a logikai formulák kielégítési problémáinak CDCL-megoldóiban keresik a konfliktusstruktúra elemzésekor [7] .

Jegyzetek

↑ Összeállítók: alapelvek, technológiák és eszközök, 2008 , p. 787.
↑ Prosser, Reese T. Boole-mátrixok alkalmazása folyamatábrák elemzésére // AFIPS Joint Computer Conferences: Az 1959. december 1–3-án tartott előadások, keleti közös IRE-AIEE-ACM számítógépes konferencia : folyóirat. - Boston, MA: ACM, 1959. - P. 133-138 .
↑ Lowry, Edward S.; és Medlock, Cleburne W. Objektumkód optimalizálás // Communications of the ACM : Journal. - 1969. - január ( 12. évf. , 1. sz.). - P. 13-22 .
↑ Cytron, Ron; Hind, Michael; és Hsieh, Wilson. A DAG párhuzamosság automatikus generálása (határozatlan) // Az ACM SIGPLAN 89 Programozási Nyelvek tervezéséről és megvalósításáról szóló konferencia előadásai. - 1989. - S. 54-68 .
↑ Összeállítók: alapelvek, technológiák és eszközök, 2008 , p. 788.
↑ Dubrova, Elena. Minimum kerneleken alapuló szerkezeti tesztelés (határozatlan) // Proceedings of Design and Test in Europe Conference. - 2005. - S. 1168-1173 .
↑ Armin Biere, Marijn Heule, Hans van Maaren és Toby Walsch. 4. fejezet Konfliktusvezérelt záradékok tanulása SAT-megoldók // Kézikönyv a kielégíthetőségről. - IOS Press, 2008. - 135. o.

Irodalom

Alfred W. Aho, Monica S. Lam, Ravi Seti, Jeffrey D. Ullman. Fordítók: alapelvek, technikák és eszközök = Compilers: Principles, Techniques and Tools. - Williams Publishing House, 2008. - ISBN 0-321-48681-1 .