Adatfüggőség

Az adatfüggőség a számítástechnikában olyan helyzet, amelyben egy utasítás egy korábbi utasításban lévő adatra utal. A fordítóelméletben az utasítások adattól való függőségének felfedezésére alkalmazott technikát függőségelemzésnek hívják. Háromféle függőség van: adat-, név- és vezérlésfüggőség.

Adatfüggőségek

Feltételezve $S_1$ és $S_2$ utasítást, $S_2$ függ $S_1$-től ha $[I(S_1)\cap O(S_2)]\cup [O(S_1)\cap I(S_2)]\cup [O(S_1)\cap O(S_2)]\ne \varnothing ,$ ahol

• $I(S_i)$ az $S_i$ által olvasott memóriahelyek halmaza;
• $O(S_j)$ az $S_j$ által írt memóriahelyek halmaza;
• és van egy megvalósítható végrehajtási útvonal $S_1$ és $S_2$ között.

Ez a Bernstein-állapot, amelyet A. J. Bernstein nevezett el. Három eset létezik:

• Valódi függőség: $O(S_1)\cap I(S_2)\ne \varnothing$, $S_1\to S_2$ és $S_1$ ír valamit, mielőtt azt $S_2$ olvasná.
• Hamis függőség: $I(S_1)\cap O(S_2)\ne \varnothing$, $S_1\to S_2$ és $S_1$ olvas valamit, mielőtt azt $S_2$ felülírná.
• Kimeneti függőség: $O(S_1)\cap O(S_2)\ne \varnothing$, $S_1\to S_2$ és mindkettő ugyanarra a memóriahelyre ír.

Valódi függőség

Valódi függőség (read after write, RAW) akkor fordul elő, ha egy utasítás egy előző utasítás eredményétől függ:

1. A = 3
2. B = A
3. C = B

A 3. és a 2. utasítás között valódi függőség van, mivel a C végső értéke a B frissítésétől függ. A 2. és az 1. utasítás között is valódi függőség van, mivel a B végső értéke az A frissítésétől függ. Mivel a 3. és a 2., illetve a 2. és az 1. utasítás között valódi függőség van, ezért a 3. és az 1. utasítás között is valódi függőség lesz. Az utasításszintű párhuzamosság ezért ebben a példában nem lehetséges.

Hamis függőség

Hamis függőség (write after read, WAR) akkor fordul elő, amikor egy utasítás egy később frissített változót igényel. A következő példában a 3. és a 2. utasítás között hamis függőség van – ezeknek az utasításoknak a sorrendje nem változtatható meg, és nem hajthatók végre párhuzamosan, mivel ez befolyásolja az A végső értékét.

1. B = 3
2. A = B + 1
3. B = 7

A hamis függőség egy példa a névfüggőségre. Vagyis a változók átnevezése megszüntetheti a függőséget, mint a következő példában:

1. B = 3
N. B2 = B
2. A = B2 + 1
3. B = 7

Egy új B2 változót vezetünk be a B jelölésére egy új, N. utasításban. A 3. és a 2. utasítás között a függőség megszűnt, ami azt jelenti, hogy ezeket az utasításokat most párhuzamosan is végre lehet hajtani. A módosítás azonban új függőséget vezetett be: a 2. és az N., valamint az N. és az 1. utasítás között valódi függőség van. Mivel valódi függőségek, ezért ezeket lehetetlen biztonságosan eltávolítani.

Kimeneti függőség

Kimeneti függőség (write after write, WAW) akkor fordul elő, amikor az utasítások rendezése befolyásolja egy változó végső kimeneti értékét. Az alábbi példában egy kimeneti függőség van a 3. és az 1. utasítás között – ebben a példában az utasítások sorrendjének módosítása megváltoztatja az A végső értékét, így ezeket az utasításokat nem lehet párhuzamosan végrehajtani.

1. B = 3
2. A = B + 1
3. B = 7

Mint a hamis függőségnél, a kimeneti függőségek névfüggőségek is. Vagyis ezek eltávolíthatók a változók átnevezésével, a fenti példa alábbi módosítása szerint:

1. B2 = 3
2. A = B2 + 1
3. B = 7

Az adattfüggőségek általánosan használt elnevezései a következők: read after write vagy RAW (valódi függőség), write after read vagy WAR (hamis függőség), write after write vagy WAW (kimeneti függőség).

Vezérlésfüggőség

Az A és a B utasítás között vezérlésfüggőség van, ha az A kimenetele határozza meg, hogy a B-t végre kell-e hajtani, vagy sem. A következő példában az $S_2$ és az $S_1$utasítás között vezérlésfüggőség van. Azonban az $S_3$ nem függ az $S_1$-től, mivel az $S_3$-at mindig végrehajtják, függetlenül az $S_1$-től.

S1.         if (a == b)
S2.             a = a + b
S3.         b = a + b

Intuitív módon a B és az A utasítás között vezérlésfüggőség van, ha

• a B végrehajtása az A után lehetséges, és
• az A végrehajtásának kimenetele határozza meg, hogy a B végrehajtásra kerül-e, vagy sem.

Jellemző példa, hogy vezérlésfüggőségek vannak az if állítás feltételes része és az igaz/hamis állításai között. A vezérlésfüggőség formális meghatározása az alábbiak szerint adható meg: Az $S_2$ és az $S_1$ utasítás között akkor és csak akkor van vezérlésfüggőség, ha

• létezik egy $P$ út $S_1$ és $S_2$ között, amelyen minden utasításra teljesül, hogy $S_i\ne S_1$, és amelyet a program végéig minden lehetséges úton követ $S_2$, továbbá
• $S_2$-nek nem feltétlenül kell követnie $S_1$-et, például ha létezik egy végrehajtási út $S_1$-től a program végéig, amely nem megy keresztül $S_2$-n.

Fordítás

• Ez a szócikk részben vagy egészben a Data dependency című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.