Zavisnost podataka

Zavisnost podataka, u računarstvu, je situacija u kojoj iskaz programa (instrukcija) upućuje na podatak prethodnog iskaza. U teoriji kompajlera, tehnika koja se koristi da se otkriju zavisnosti podataka među iskazima (ili instrukcijama) se zove analiza zavisnosti.

Postoje tri tipa zavisnosti:

• Zavisnost podataka
• Zavisnost naziva i
• Zavisnost kontrole

Zavisnost podataka

Ako imamo iskaze $S_{1}$ i $S_{2}$, $S_{2}$ zavisi od $S_{1}$ ako:

$[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$

gde:

• $I(S_{i})$ predstavlja skup memorijskih lokacija pročitane od strane $S_{i}$
• $O(S_{j})$ je skup memorijskih lokacija koje je $S_{j}$ upisao
• postoje izvodljive putanje (u run-time izvršavanju programa) od $S_{1}$ do $S_{2}$

Ovo stanje se zove Bernštajn stanje (engl. Bernstein Condition, po A. J. Bernstein).

Postoje tri slučaja:

• Zavisnost toka (podataka) : O(S1) ∩ I (S2), S1 → S2; i S1 piše nešto što čita S2
• Anti-zavisnost: I(S1) ∩ O(S2), S1 → S2; i S1 čita nešto pre nego što ga S2 izmeni
• Zavisnost izlaznih podataka: O(S1) ∩ O(S2), S1 → S2; i oba pišu na istu memorijsku lokaciju

Zavisnost toka

Zavisnost toka (još poznato i kao zavinost podataka ili kao "suštinska" (engl. true) zavinost ili kao "čitaj posle pisanja" (RAW)), se događa kada neka instrukcija zavisi od rezultata prethodne instrukcije:

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

Instrukcija 3 "suštinski" zavisi od instrukcije 2, jer zaključna vrednost C zavisi od instrukcija koje ažuriraju B. Instrukcija 2 "suštinski" zavisi od istrukcije 1, jer zaključna vrednost B zavisi od instrukcija koje ažuriraju A. Pošto instrukcija 3 "suštinski" zavisi od instrukcije 2 i pošto instrukcija 2 "suštinski" zavisi od instrukcije 1, instrukcija 3 takođe "suštinski" zavisi od instrukcije 1. Paralelizam na nivou naredbe zbog toga ne može biti opcija u ovom primeru.

Anti-zavisnost

Anti-zavisnot (još poznato i kao "piši posle čitanja" (WAR)) se događa kada neka instrukcija zahteva vrednost koja će se tek kasnije ažurirati. U sledećem slučaju, instrukcija 2 anti-zavisi od intrukcije 3. Redosled ovih instrukcije se ne može promeriti, niti se mogu izvršiti paralelno, jer bi to uticalo na krajnju vrednost A.

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

Anti-zavisnost je jedan primer zavinosti naziva. Time, preimenovanje promenljivih bi moglo da ukloni zavisnost, što je i slučaj u sledećem primeru:

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

Nova promenljiva, B2, je deklarisana kao kopija B u novoj instrukciji N. Anti-zavisnost između 2 i 3 je uklonjena, što znači da se ove instrukcije sada mogu izvršiti paralelno. Međutim, ova promena nam donosi novu javisnost: instrukcija 2 sada "suštinski" zavisi od instrukcije N, koja "suštinski" zavisi od instrukcije 1. Kao zavisnosti toka, ove nove zavisnosti je nemoguće bezbedno ukloniti.

Zavisnost izlaznih podataka

Zavisnost izlaznih podataka (još poznata i kao "piši posle pisanja" (WAW)) se događa kada će pozivanje instrukcija uticati na konačanu vrednost izlazne promenljive. U primeru ispod, postoji zavisnost izlaznih podataka između instrukcija 3 i 1. Promena redosleda instrukcija, u ovom primeru, će promeniti konačnu vrednost B, čime se ove instrukcije neće moći izvršiti paralelno.

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

Kao i kod anti-zavisnosti, zavisnost izlaznih podataka je u stvari zavisnost naziva. Time bi ova zavisnost mogla biti uklonjena preimenovanjem promenljivih, kao u primeru ispod:

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

Često korišćena konvencija imena za zavisnost podataka je sledeća: "čitaj posle pisanja" ili RAW (zavisnost toka), "piši posle pisanja" ili WAW (zavisnost izlaznih podataka) i "piši posle čitanja" ili WAR (anti-zavisnost).

Zavisnost kontrole

Neka instrukcija je kontrolno zavisna od prethodne instrukcije ako kasniji ishod utvrdi da li prethodni treba da se izvrši ili ne. U primeru dole, instrukcija S2 je kontrolno zavisna od instrukcije S1. Međutim, S3 nije kontrolno zavisan od S1 zato što se S3 uvek izvršava bez obzira na ishod S1.

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

Intuitivno, postoji zavisnost kontrole između dva iskaza S1 i S2 ako bi:

• S1 bilo moguće izvršiti pre S2
• ishod izvršavanja S1 odlučio da li će se izvršiti S2

Tipičan primer je kada postoji zavinost kontrole između uslova if iskaza i iskaza "tačnog" ili "netačnog" tela.

Formalna definicija zavisnosti kontrole se može prezentovati ovako:

Za iskaz S2 se kaže da je kontrolno zavisan u odnosu na iskaz S1 ako i samo ako:

• postoji put P od S1 do S2 takav da bi svaki iskaz Si ≠ S1 u P bio praćen sa S2 u svakom mogućem putu do kraja programa; i
• S1 neće obavezno biti praćeno S2 tj. postoji put izvršavanja od S1 do kraja programa koji ne ide kroz S2.

Izraženo uz pomoć (post)dominacije, dva uslova su ekvivalentni sa:

• S2 post-dominira svim Si
• S2 ne post-dominira S1

Primer 2: kontrolno nezavisni:

for (i=0;i<n;i++)
{
a[i] = c[i];
if (a[i] < 0) a[i] = 1;
}

kontrolno zavisni:

for (i=1;i<n;i++) 
{		
if (a[i-1] < 0) a[i] = 1;                                
}

Implikacije

Konvencionalni programi su pisani uzimajući u obzir model sekvencijalnog izvršavanja. Pod ovim modelom, instrukcije se izvršavaju jedna za drugom, atomično (tj. u svakom trnutku vremena samo se jedna instrukcija izvršava) i u redosledu koji određuje program.

Međutim, zavisnosti među izjavama ili instrukcijama mogu ometati paralelizam, bilo paralelizovanjem kompajlera ili procesorovim iskorišćavanjem paralelizma na nivou bita. Bezobzirno izvršavanje više instrukcija bez razmatranja zavisnosti može izazvati opasnost dobijanja pogrešnih rezultata, naime konflikte protočne obrade.

Literatura

• Hennessy, John L.; Patterson, David A. (2003). Computer Architecture: a quantitative approach (3rd ed.). Morgan Kaufmann. ISBN 978-1-55860-724-8.