Závislost na datech - Data dependency
A závislost na datech v počítačová věda je situace, ve které a programové prohlášení (instrukce) odkazuje na data předchozího příkazu. v teorie překladače se nazývá technika použitá k odhalení závislostí dat mezi příkazy (nebo pokyny) analýza závislosti.
Existují tři typy závislostí: data, název a ovládání.
Závislosti na datech
Předpokládané prohlášení a , záleží na li:
kde:
- je sada paměťových míst přečtená a
- je sada paměťových míst zapsaných
- a existuje proveditelná cesta spuštění za běhu na
Tato podmínka se nazývá Bernsteinova podmínka, pojmenovaná A. J. Bernsteinem.
Existují tři případy:
- Anti-závislost: , a čte něco předtím přepíše to
- Závislost na toku (data): , a píše, než něco přečte
- Závislost výstupu: , a oba zapisují stejné místo v paměti.
Závislost toku (skutečná závislost)
Závislost toku, známá také jako závislost na datech nebo skutečná závislost nebo čtení po zápisu (RAW), nastane, když instrukce závisí na výsledku předchozí instrukce:
1. A = 32. B = A3. C = B
Pokyn 3 je skutečně závislý na instrukci 2, protože konečná hodnota C závisí na aktualizaci instrukce B. Pokyn 2 je skutečně závislý na instrukci 1, protože konečná hodnota B závisí na aktualizaci instrukce A. Protože instrukce 3 je skutečně závislá na instrukci 2 a instrukci 2 skutečně závisí na instrukci 1, instrukce 3 také skutečně závisí na instrukci 1. Paralela na úrovni instrukcí proto v tomto příkladu není možnost.[1]
Anti-závislost
Anti-dependency, také známý jako write-after-read (WAR), nastane, když instrukce vyžaduje hodnotu, která je později aktualizována. V následujícím příkladu je instrukce 2 závislá na instrukci 3 - pořadí těchto instrukcí nelze změnit, ani je nelze provést paralelně (možná změna pořadí instrukcí), protože by to ovlivnilo konečnou hodnotu A.
1. B = 32. A = B + 13. B = 7
Anti-závislost je příkladem a závislost na jménu. To znamená, že přejmenování proměnných může odstranit závislost, jako v následujícím příkladu:
1. B = 3N. B2 = B2. A = B2 + 13. B = 7
Nová proměnná, B2, byla deklarována jako kopie B v nové instrukci, instrukci N. Byla odstraněna závislost mezi 2 a 3, což znamená, že tyto instrukce mohou být nyní prováděny paralelně. Modifikace však zavedla novou závislost: instrukce 2 je nyní skutečně závislá na instrukci N, která je skutečně závislá na instrukci 1. Protože závislost toku nelze tyto nové závislosti bezpečně odstranit.[1]
Závislost výstupu
Závislost výstupu, známá také jako write-after-write (WAW), nastane, když pořadí instrukcí ovlivní konečnou výstupní hodnotu proměnné. V níže uvedeném příkladu existuje výstupní závislost mezi instrukcemi 3 a 1 - změna pořadí instrukcí v tomto příkladu změní konečnou hodnotu A, takže tyto instrukce nelze provádět paralelně.
1. B = 32. A = B + 13. B = 7
Stejně jako u závislostí jsou výstupní závislosti pojmenování závislostí. To znamená, že mohou být odstraněny přejmenováním proměnných, jako v níže uvedené úpravě výše uvedeného příkladu:
1. B2 = 32. A = B2 + 13. B = 7
Běžně používaná konvence pojmenování závislostí dat je následující: Read-after-Write nebo RAW (závislost toku), Write-After-Read nebo WAR (anti-závislost), nebo Write-after-Write nebo WAW (závislost výstupu).[1]
Závislost kontroly
Instrukce B má závislost řízení na předchozí instrukci A, pokud výsledek A určuje, zda má být B proveden nebo ne. V následujícím příkladu instrukce má závislost ovládání na instrukci . Nicméně, nezávisí na protože se vždy provede bez ohledu na výsledek .
S1. if (a == b) S2. a = a + bS3. b = a + b
Intuitivně existuje závislost ovládání mezi dvěma výroky A a B if
- B by mohlo být provedeno po A
- Výsledek provedení A určí, zda bude B proveden nebo ne.
Typickým příkladem je, že existují kontrolní závislosti mezi podmínkovou částí příkazu if a příkazy v jeho tělech true / false.
Formální definici závislosti na kontrole lze uvést následovně:
Prohlášení se říká, že ovládání závisí na jiném tvrzení iff
- existuje cesta z na taková, že každé tvrzení ≠ v rámci bude následovat v každé možné cestě na konec programu a
- nebude nutně následovat , tj. existuje exekuční cesta z na konec programu, který neprojde .
Vyjádřeno pomocí (post-) dominance jsou obě podmínky rovnocenné
- post-dominuje všem
- nedominuje
Konstrukce kontrolních závislostí
Závislosti ovládání jsou v zásadě hranice dominance v opačném grafu kontrolní tokový graf (CFG).[2] Jedním ze způsobů jejich konstrukce by tedy bylo zkonstruovat post-dominantní hranici CFG a její obrácení, aby se získal graf závislosti na ovládání.
Následuje pseudokód pro konstrukci hranice po dominanci:
pro každé X při procházení zdola nahoru stromu dominátora proveďte: PostDominanceFrontier (X) ← ∅ pro každé Y ∈ Předchůdci (X) udělejte: pokud je okamžitéPostDominator (Y) ≠ X: pak PostDominanceFrontier (X) ← PostDominanceFrontier (X) ∪ {Y} uděláno za každé Z ∈ děti (X) udělají: za každé Y ∈ PostDominanceFrontier (Z) udělá: pokud je okamžitéPostDominátor (Y) ≠ X: pak PostDominanceFrontier (X) ← PostDominanceFrontier (X) ∪ {Y} hotovo darováno
Zde Children (X) je sada uzlů v CFG, které post-dominují X a Predecessors (X) jsou sada uzlů v CFG, které přímo předcházejí X v CFG.
Jakmile je vypočítána mapa post-dominance hranice, její obrácení bude mít za následek mapu z uzlů v CFG do uzlů, které na nich mají závislost na ovládání.
Důsledky
Konvenční programy jsou psány za předpokladu, že model postupného provádění. V rámci tohoto modelu se instrukce provádějí jedna po druhé, atomicky (tj. V daném okamžiku se provádí pouze jedna instrukce) a v pořadí určeném programem.
Závislosti mezi příkazy nebo instrukcemi však mohou bránit paralelismu - paralelní provádění více instrukcí, buď paralelizujícím kompilátorem nebo zneužitím procesoru paralelismus na úrovni instrukcí. Bezohledné provádění více instrukcí bez zvážení souvisejících závislostí může způsobit nebezpečí špatných výsledků, jmenovitě nebezpečí.
Reference
- ^ A b C John L. Hennessy; David A. Patterson (2003). Počítačová architektura: kvantitativní přístup (3. vydání). Morgan Kaufmann. ISBN 1-55860-724-2.CS1 maint: více jmen: seznam autorů (odkaz)
- ^ Cytron, R .; Ferrante, J .; Rosen, B. K .; Wegman, M. N .; Zadeck, F. K. (01.01.1989). "Efektivní metoda výpočtu statického formuláře jednoduchého přiřazení". Sborník 16. sympozia ACM SIGPLAN-SIGACT o zásadách programovacích jazyků. POPL '89. New York, NY, USA: ACM: 25–35. doi:10.1145/75277.75280. ISBN 0897912942.