Analýza závislosti na smyčce - Loop dependence analysis - Wikipedia

Analýza závislosti na smyčce je proces, který lze použít k nalezení závislostí v iteracích smyčky s cílem určit různé vztahy mezi příkazy. Tyto závislé vztahy jsou vázány na pořadí, ve kterém různé příkazy přistupují k místům paměti. Pomocí analýzy těchto vztahů lze organizovat provedení smyčky tak, aby umožňovala více procesory paralelně pracovat na různých částech smyčky. Toto je známé jako paralelní zpracování. Obecně mohou smyčky spotřebovat hodně Doba zpracování při provedení jako Sériové číslo. Prostřednictvím paralelního zpracování je možné snížit celkovou dobu provádění programu sdílením zátěže zpracování mezi více procesory.

Proces organizování příkazů, který umožňuje více procesorům pracovat na různých částech smyčky, se často označuje jako paralelizace. Abychom zjistili, jak můžeme využít paralelizaci, musíme nejprve analyzovat závislosti v rámci jednotlivých smyček. Tyto závislosti pomohou určit, které příkazy ve smyčce je třeba dokončit před spuštěním dalších příkazů a které příkazy ve smyčce lze provést paralelně s ohledem na ostatní příkazy ve smyčce. Dvě obecné kategorie závislostí, které budou ve smyčce analyzovány, jsou datové závislosti a řídit závislosti.

Popis

Analýza závislosti na smyčce se vyskytuje na a normalizovaná smyčka formuláře:


Protože já1 až do U1 udělat pro i2 až do U2 dělat ... pro in až do Un dělat tělo    hotovo donedone


kde tělo může obsahovat:


S1 a [f1(tj1, ..., in), ..., fm(tj1, ..., in)]: = ... ... S2 ...: = a [h1(tj1, ..., in), ..., hm(tj1, ..., in)]


Kde A je m-rozměrné pole a Fn, hnatd. jsou mapování funkcí ze všech iteračních indexů (tjn) k přístupu do paměti v konkrétní dimenzi pole.

Například v C:

pro (i = 0; i < U1; i++)  pro (j = 0; j < U2; j++)    A[i+4-j] = b[2*i-j] + i*j;

F1 bylo by i + 4-j, ovládání zápisu na první dimenzi A a h2 bylo by 2 * i-j, řízení čtení na první dimenzi b.

Úkolem problému je najít všechny možné závislosti mezi nimi S1 a S2. Abychom byli konzervativní, musí být každá závislost, kterou nelze prokázat jako nepravdivou, považována za pravdivou.

Nezávislost se projevuje demonstrací, že neexistují dva případy S1 a S2 přistupovat nebo upravovat stejné místo v poli A. Když je nalezena možná závislost, analýza závislosti na smyčce obvykle dělá každý pokus o charakterizaci vztahu mezi závislými instancemi, protože některé optimalizace mohou být stále možné. Je také možné přeměnit smyčka k odebrání nebo úpravě závislosti.

V průběhu (ne) prokázání takových závislostí prohlášení S mohou být rozloženy podle toho, z jaké iterace pochází. Například, S[1,3,5] odkazuje na iteraci, kde i1 = 1, i2 = 3 a i3 = 5. Samozřejmě, odkazy na abstraktní iterace, jako např S[d1+1,d2,d3], jsou povolené i běžné.

Závislost na datech

Závislosti dat ukazují vztahy mezi proměnnými v kódu. Existují tři různé typy závislostí dat:

  • Skutečná závislost (někdy označovaná jako závislost na toku)
  • Proti závislosti
  • Závislost na výstupu

Skutečná závislost

A skutečná závislost nastane, když je místo v paměti zapsáno před čtením.[1][2][3] Představuje nebezpečí čtení a zápisu (RAW) protože instrukce, která čte z umístění v paměti, musí počkat, dokud nebude zapsána předchozí instrukcí, jinak instrukce pro čtení přečte nesprávnou hodnotu.[2] Příklad skutečné závislosti je:

 S1: A = 5; S2: b = A;

V tomto příkladu existuje skutečná závislost mezi S1 a S2, protože proměnná a se nejprve zapíše do příkazu S1 a poté se proměnná a načte příkazem S2. Tuto skutečnou závislost lze vyjádřit pomocí S1 → T S2.

Skutečnou závislost lze také vidět při čtení a zápisu mezi různými iteracemi ve smyčce. Následující příklad ukazuje skutečnou závislost mezi různými iteracemi.

 pro(j = 1; j < n; j++)    S1: A[j] = A[j-1];

V tomto příkladu existuje skutečná závislost mezi příkazem S1 v j-té iteraci a S1 v j + 1. Iteraci. Existuje skutečná závislost, protože hodnota bude zapsána do [j] v jedné iteraci a poté dojde ke čtení pomocí [j-1] v další iteraci. Tuto skutečnou závislost lze vyjádřit pomocí S1 [j] → T S1 [j + 1].

Proti závislosti

An proti závislosti nastane, když je místo v paměti načteno před zapsáním stejného umístění.[1][2][3] To zavádí nebezpečí zápisu po přečtení (WAR) protože instrukce, která zapisuje data do paměťového místa, musí počkat, dokud toto paměťové místo nebylo přečteno předchozí instrukcí, jinak by instrukce pro čtení přečetla nesprávnou hodnotu.[2] Příkladem anti-závislosti je:

 S1: A = b; S2: b = 5;

V tomto příkladu existuje anti závislost mezi příkazy S1 a S2. Toto je anti závislost, protože proměnná b se nejprve přečte v příkazu S1 a poté se proměnná b zapíše do příkazu S2. To může být reprezentováno S1 → A S2. Anti závislost může být viděna různými iteracemi ve smyčce. Následující příklad ukazuje příklad tohoto případu:

 pro(j = 0; j < n; j++)    S1: b[j] = b[j+1];

V tomto příkladu existuje anti závislost mezi j-tou iterací S1 a j + 1. Prvkem S1. Zde se čte j + 1. Prvek před zapsáním stejného prvku v další iteraci j. Tuto anti závislost lze vyjádřit pomocí S1 [j] → A S1 [j + 1].

Závislost výstupu

An výstupní závislost nastane, když je místo v paměti zapsáno před tím, než je stejné místo zapsáno znovu v jiném příkazu.[1][2][3] To zavádí nebezpečí zápisu za zápisem (WAW) protože druhá instrukce k zápisu hodnoty do paměťového místa musí počkat, dokud první instrukce nedokončí zápis dat do stejného paměťového místa, nebo když bude paměťové místo přečteno později, bude obsahovat nesprávnou hodnotu.[2] Příklad výstupní závislosti je:

  S1: C = 8;   S2: C = 15;

V tomto příkladu existuje výstupní závislost mezi příkazy S1 a S2. Zde se proměnná c nejprve zapíše do S1 a potom se proměnná c znovu zapíše do příkazu S2. Tato výstupní závislost může být reprezentována S1 → O S2. Závislost výstupu může být viděna různými iteracemi ve smyčce. Následující fragment kódu ukazuje příklad tohoto případu:

 pro(j = 0; j < n; j++)    S1: C[j] = j;      S2: C[j+1] = 5;

V tomto příkladu existuje výstupní závislost mezi j-tým prvkem v S1 a j + 1. Prvkem v S2. Zde je c [j + 1] ve výpisu S2 zapsáno do jedné iterace. V další iteraci se znovu zapíše c [j] v příkazu S2, což je stejné paměťové místo jako c [j + 1] v předchozí iteraci. Tuto výstupní závislost lze vyjádřit jako S1 [j] → O S2 [j + 1].

Ovládejte závislost

Při analýze závislostí mezi různými příkazy ve smyčce je třeba vzít v úvahu také kontrolní závislosti. Závislosti řízení jsou závislosti zavedené kódem nebo samotným programovacím algoritmem. Řídí pořadí, ve kterém se pokyny vyskytují při provádění kódu.[4] Běžným příkladem je prohlášení „pokud“. "if" příkazy vytvářejí větve v programu. Část „then“ výrazu „if“ výslovně řídí nebo řídí akce, které mají být provedeny.[3]

 // Kódový blok 1 (SPRÁVNÝ) // Kódový blok 2 (NESPRÁVNÝ) // Kódový blok 3 (NESPRÁVNÝ) -li (A == b) pak {                 -li (A == b) pak {                 -li (A == b) pak {                   C = "řízený";               }                                     C = "řízený"; }                                  C = "řízený";                     d = "neřízený"; d = "neřízený";              d = "neřízený";              }

V tomto příkladu jsou znázorněna omezení toku řízení. Blok kódu 1 ukazuje správné pořadí při použití příkazu if v programovacím jazyce C. Blok kódu 2 ilustruje problém, kdy příkaz, který má být řízen příkazem if, již ním není řízen. Blok kódu 3 ilustruje problém, kdy příkaz, který nemá být řízen příkazem „if“, byl nyní přesunut pod jeho kontrolu. Obě tyto dvě možnosti by mohly vést k nesprávnému provedení programu a je třeba je zohlednit při paralelizaci těchto příkazů ve smyčce.

Závislost na smyčce vs. závislost na smyčce

Závislosti nesené smyčkou a závislosti nezávislé na smyčce jsou určeny vztahy mezi příkazy v iteracích smyčky. Když příkaz v jedné iteraci smyčky nějakým způsobem závisí na příkazu v jiné iteraci stejné smyčky, existuje závislost nesená smyčkou.[1][2][3] Pokud však příkaz v jedné iteraci smyčky závisí pouze na příkazu ve stejné iteraci smyčky, vytvoří se závislost nezávislá na smyčce.[1][2][3]

 // Blok kódu 1 // Blok kódu 2 pro (i = 0; i < 4; i++)                               pro (i = 0; i < 4; i++)    S1: b[i] = 8;                                           S1: b[i] = 8;    S2: A[i] = b[i-1] + 10;                                 S2: A[i] = b[i] + 10;

V tomto příkladu ukazuje blok kódu 1 závislost na smyčce mezi iterací příkazu S2 iterace i a iterací příkazu S1 i-1. To znamená, že příkaz S2 nemůže pokračovat, dokud nedojde k dokončení příkazu S1 v předchozí iteraci. Blok kódu 2 zobrazuje závislost nezávislou na smyčce mezi příkazy S1 a S2 ve stejné iteraci.

Průchozí grafy závislosti závislosti a iterace prostoru

Iterační prostorové traversální grafy (ITG) ukazují cestu, kterou se kód vydává při procházení iteracemi smyčky.[1] Každá iterace je reprezentována uzlem. Grafy závislostí nesené smyčkou (LDG) poskytují vizuální reprezentaci všech skutečných závislostí, závislostí proti a výstupních závislostí, které existují mezi různými iteracemi ve smyčce.[1] Každá iterace je reprezentována uzlem.

Je snazší ukázat rozdíl mezi těmito dvěma grafy pomocí vnořené smyčky for.

 pro (i = 0; i < 4; i++)    pro (j = 0; j < 4; j++)       S1: A[i][j] = A[i][j-1] * X;

V tomto příkladu existuje skutečná závislost mezi j iterací příkazu S1 a j + 1. Příkazem S1. Toto může být reprezentováno jako S1 [i, j] → T S1 [i, j + 1] Graf iteračního prostoru a graf závislosti smyčky je: Iterační prostor Traversal Graph: Loop Carry Dependence Graph:

Graf závislosti na smyčce (LDG)
Traversální graf iteračního prostoru (ITG)


Viz také

Reference

  1. ^ A b C d E F G Solihin, Yan (2016). Základy paralelní počítačové architektury: vícečipové a vícejádrové systémy. [USA?]: Solihin Pub. ISBN  978-1-4822-1118-4.
  2. ^ A b C d E F G h Devan, Pradip; Kamat, R.K. (2014). Msgstr "Recenze - analýza závislosti smyčky pro paralelizující překladač". International Journal of Computer Science and Information Technologies. 5.
  3. ^ A b C d E F John, Hennessy; Patterson, David (2012). Počítačová architektura - kvantitativní přístup. 225 Wyman Street, Waltham, MA 02451, USA: Morgan Kaufmann Publishers. str. 152–156. doi:10.1016 / B978-0-12-383872-8.00003-3 (neaktivní 11. 11. 2020). ISBN  978-0-12-383872-8.CS1 maint: umístění (odkaz) CS1 maint: DOI neaktivní od listopadu 2020 (odkaz)
  4. ^ Allen, J. R .; Kennedy, Ken; Porterfield, Carrie; Warren, Joe (01.01.1983). Msgstr "Převod závislosti kontroly na závislost dat". Sborník z 10. sympozia ACM SIGACT-SIGPLAN o zásadách programovacích jazyků. POPL '83. New York, NY, USA: ACM: 177–189. doi:10.1145/567067.567085. ISBN  0897910907. S2CID  39279813.