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 ${\displaystyle S_{1}}$ és ${\displaystyle S_{2}}$ utasítást, ${\displaystyle S_{2}}$ függ ${\displaystyle S_{1}}$-től ha

${\displaystyle [I(S_{1})\cap O(S_{2})]\cup [O(S_{1})\cap I(S_{2})]\cup [O(S_{1})\cap O(S_{2})]\neq \varnothing ,}$

ahol

• ${\displaystyle I(S_{i})}$ az ${\displaystyle S_{i}}$ által olvasott memóriahelyek halmaza;
• ${\displaystyle O(S_{j})}$ az ${\displaystyle S_{j}}$ által írt memóriahelyek halmaza;
• és van egy megvalósítható végrehajtási útvonal ${\displaystyle S_{1}}$ és ${\displaystyle 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: ${\displaystyle O(S_{1})\cap I(S_{2})\neq \varnothing }$, ${\displaystyle S_{1}\rightarrow S_{2}}$ és ${\displaystyle S_{1}}$ ír valamit, mielőtt azt ${\displaystyle S_{2}}$ olvasná.
• Hamis függőség: ${\displaystyle I(S_{1})\cap O(S_{2})\neq \varnothing }$, ${\displaystyle S_{1}\rightarrow S_{2}}$ és ${\displaystyle S_{1}}$ olvas valamit, mielőtt azt ${\displaystyle S_{2}}$ felülírná.
• Kimeneti függőség: ${\displaystyle O(S_{1})\cap O(S_{2})\neq \varnothing }$, ${\displaystyle S_{1}\rightarrow 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.^[1]

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.^[1]

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).^[1]

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 ${\displaystyle S_{2}}$ és az ${\displaystyle S_{1}}$utasítás között vezérlésfüggőség van. Azonban az ${\displaystyle S_{3}}$ nem függ az ${\displaystyle S_{1}}$-től, mivel az ${\displaystyle S_{3}}$-at mindig végrehajtják, függetlenül az ${\displaystyle 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 ${\displaystyle S_{2}}$ és az ${\displaystyle S_{1}}$ utasítás között akkor és csak akkor van vezérlésfüggőség, ha

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

Jegyzetek

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.