ZALEZNOSCI DANYCH

Zaleznosci w programach - fakt wykonania lub nie wykonania jakiejs instrukcji zalezy od wyniku innej instrukcji

s1: if (A>B) then

s2: X=Y

endif

instrukcja s2 nie musi byc wykonana!

Zaleznosc danych: odwolanie do zmiennej programu to jest odczytanie jej dotychczasowej wartosci lub nadanie tej zmiennej nowej wartosci - odczyt lub zapis. Zaleznosc danych wystepuje wowczas gdy w dwoch instrukcjach nastepuje odwolanie do tej samej zmiennej programu i wynikiem wywyolania przynajmniej jednej z nich jest nadanie tej zmiennej nowej wartosci. w konsekwencji wywolanie instr odwolujacej sie do zmiennej drugiej kolejnosci moze nastapic dopiero po zakonczeniu wykonywania instrukcji, ktora odwolywala sie do tej zmiennej wczesniej. instrukcja ktora musi byc wykonana wczesniej to zrodlo zaleznosci, instrukcja ktora jest wywolywana pozniej to ujscie zaleznosci.

S1 -> S2

TYPY ZALEZNOSCI(a,b,c)

a) s1:A=B+C

/

\

S2:D=A*2, dane sa salezne S1 -> S2 - zaleznosc przeplywu

zaleznosc przeplywu (prawdziwa) - zapis do zmiennej jest w zrodle, a odczyt w ujsciu

b) s1:A=X+1

s2:X=Y+Z, dane zalezne - przeciwzaleznosc (sztuczna)

odczyt jest w zrodla a zapis w ujsciu

c)

s1:P=P+Q+R

s2:S=P/2

s3:P=T*T

zaleznosc wyjsc(wynikow), s1->s3, w obu wywolaniach nastepuje zapis do zmiennej (sztuczna)

D)

S1:A=B+C

S2:D=E-F

DANE NIE ZALEZNE

E)

S1:A=B+C

S2:D=B-E

DANE NIE ZALEZNE

S1:A=X+Y

S2:B=C*A S1->S2

S3:X=W-V S1->S3

S4:A=X-Y S3->S4, S1->S4, S2->S4

S1:A1=X+Y

S2:B=C*A1

S3:X1=W-V

S4:A=X1-Y

WYNIK JAK POPRZEDNIO, ALE NIE MA ZALEZNOSCI - TECHNIKA PRZEMIANOWANIA

ZALEZNOSCI DANYCH W PETLACH

Ciag instukcji jest wykonywany wiele razy - tyle ile iteracji

a) zaleznosc wenatrziteracyjna - zrodlo i ujscie znajduja sie w tej samej iteracji petli

b) zaleznasc miedzyiteracyjna - zrodlo i ujscie sa w roznych iteracjach, zrodlo jest we wczesniejszej petli a ujsci w poznijejszej

do I=1,10

A(I)=X(I)

Y(I)=A(I), moznaby bylo usunosc a i przypisac x do y, ale tu tak tylko zakladamy

enddo

iter1: A(1)=X(1)

Y(1)=A(1) zaleznosc przpylwu

iter2: A(2)=X(2)

Y(2)=A(2)

.......

iter 10: A(10)=X(10)

Y(10)=A(10)

do I=2,10

A(I)=X(I)

Y(I)=A(I-1)

enddo

iter1: A(2)=X(2)

Y(2)=A(1)

iter2: A(3)=X(3)

Y(3)=A(2)

.......

iter 9: A(10)=X(10)

Y(10)=A(9)

zrodlo i ujsci sa w roznych iteracjach, A(I)->Y(I)

zaleznsc wewnatrziteracyjna nie stanowi przeszkody w zrownoleglaniu

zaleznosc miedzy iteracyjna nie pozwala na zrownoleglenie

do I=2,100 |zaleznosc|typ |rodzaj |tablica|

| | | | |

__________________________________________________________________

S1:A(I)=B(I*2)+X(I) |S1->S2 |przeplyw |wewnatrziter|A |

s2:ci=ai/2.0 |S1->S3 |przeplyw |wewnatrziter|A |

s3:fi=c(i+1)-A(I) |S1->S5 |przeciwzal|wenatrziter |X |

s4:D(I+1)=C(I)*C(I) |S2->S4 |przeplyw |wewnatrziter|C |

S5:X(I)=D(I)+C(I-1) |S2->S5 |przeplyw |miedzyiterac|C |

s6:x(i+2)=E(I)+F(I) |S3->S6 |przeplyw |wewnatrziter|F |

enddo |S3->S2 |przeciwzal|miedzyiterac|C |

|S4->S5 |przeplyw |miedzyiterac|D |

|s6->s1 |przeplyw |miedzyiterac|X |

|s6->s5 |wyjsc |miedzyiterac|X |

do i=2,26

a(i)=a(i)+a(i-1)

enddo

zaleznosc iteracyjna, zrodlem i ujsciem jest to samo, a->a

---