1 Zrównoleglanie programu sekwencyjnego1. Analiza zależności pomiędzy danymi (ang. data dependence analysis) – w fazie tej identyfikuje się występujące w programie zależności danych w celu określenia części programu, które mogą być wykonywane równolegle. 2. Transformacje programu (ang. transformation techniques) - w fazie tej decydujemy, która z możliwych transformacji programu może zostać zastosowana. Istnieje wiele sposobów transformacji dostosowanych do różnych architektur oraz języków programowania. Mają one na celu takie przekształcenie programu aby zlikwidować istniejące zależności, bądź ułatwić późniejszą transformację do programu równoległego. 3. Generowanie kodu źródłowego programu równoległego (ang. code generation) - w zależności od architektury komputera oraz modelu pamięci, generowany jest kod wynikowy programu równoległego.

2 Zależności w programieWe wszystkich przedstawionych poniżej przykładach programów sekwencyjnych przyjęto założenie, że sekwencja ich wykonania jest zgodna z kolejnością ich zapisu. I tak, analizując dwie poniższe instrukcje możemy stwierdzić, że są zależne, ponieważ wynik działania drugiej z nich zależy od wyniku pierwszej. b = 2*a; c = b;

3 Zależności w programieZazwyczaj wyróżnia się trzy podstawowe typy zależności: Zależność właściwa lub przepływowa (ang. true/flow dependence), występuje pomiędzy dwoma instrukcjami, jeżeli pierwsza z nich zapisuje dane do komórki pamięci M, natomiast druga odczytuje oraz nie istnieje instrukcja zapisująca do M wykonywana pomiędzy nimi. Zależność tę ilustruje poniższy przykład m = a + x; b = m + c;

4 Zależności w programieZależność wyjściowa (ang. output dependence), występuje pomiędzy dwoma instrukcjami, jeżeli obie zapisują do tej samej komórki pamięci M oraz nie istnieje instrukcja zapisująca do M wykonywana pomiędzy nimi. Poniższe instrukcje ilustrują tę zależność m = a + x; m = b + x; Antyzależność (ang. anti-dependence), występuje pomiędzy dwoma instrukcjami, jeżeli pierwsza z nich odczytuje dane z komórki pamięci M, natomiast druga zapisuje dane do M oraz nie istnieje instrukcja zapisująca do M wykonywana pomiędzy nimi a = m + b; m = c + x;

5 Usuwanie antyzależnościAntyzależność występuje w programie, jeżeli pewna instrukcja zmienia wartość zmiennej, nie wykorzystując jej poprzedniej wartości. Usunięcie antyzależności polega na nadaniu jej nowej nazwy i wykorzystaniu w ten sposób nowego obszaru pamięci. Poniższy przykład prezentuje sposób usunięcia antyzależności względem zmiennej ”a”. b = a + c; b = a + c; a = x + y; aa = x + y; ...  ... d = a + z; d = aa + z; Napotykając dalsze odwołania do zmiennej ”a”, należy je wszystkie odpowiednio zmodyfikować,

6 Usuwanie zależności wyjściowejZależność wyjściową usuwa się podobnie jak antyzależność, stosując zamianę nazw zmiennych. Zależność wyjściowa występuje bowiem, gdy dwie kolejne instrukcje zmieniają wartość tej samej zmiennej, a dla wyliczenia drugiej z nich poprzednia wartość tej zmiennej nie jest istotna. a = b + c; a = b + c; a = x + y;  aa = x + y;

7 Usuwanie zależności właściwejZależność właściwa nie daje się usunąć całkowicie, dlatego stosowane transformacje programu mają na celu zmniejszenie liczby wystąpień takich zależności. W wielu przypadkach usuwanie zależności właściwej sprowadza się do redukcji wysokości grafu zależności (operacja ta jest znana pod nazwą redukcji wysokości drzewa). Graf zależności to graf skierowany, którego węzły reprezentują instrukcje programu, a łuki występujące pomiędzy nimi zależności. Umożliwia to częściowe zrównoleglenie obliczeń. Najczęściej stosowanymi w tym celu przekształceniami są: wprowadzenie dodatkowych zmiennych, zmiana nazw zmiennych oraz zamiana kolejności obliczeń.

8 Usuwanie zależności właściwej - przykłada = t[1]; b = t[1] + t[2]; b = a + t[2];  c = t[3] + t[4]; c = b + t[3]; d = b + c; d = c + t[4]; Kolejne instrukcje programu wejściowego są od siebie zależne. Dwie pierwsze instrukcje zmodyfikowanego programu mogą natomiast zostać wykonane równolegle, ponieważ nie istnieje między nimi zależność – została usunięta.

9 Eliminacja zależnościfor (i=1;i<=100;i=i+1) for (i=1;i<=100;i=i+1) { y[i]=x[i] / c; { t[i] =x[i] / c; x[i] = x[i] = c; x1[i] = x[i] = c; z[i] = y[i] + c; z[i] = t[i] + c; y[i] = c – y[i]; } y[i] = c – t[i]; } wyjściowa antyzależność

10 Usuwanie zależności - przykładRozważmy następujący przykład: Graf zależności: Mamy trzy rodzaje zależności: zależność właściwą, antyzależność oraz zależność wyjściową. St4 St1 St2 St3 dt,da,do S A1 + A2 + A3 + A

11 Usuwanie zależności - przykładW pierwszym kroku zmieniamy nazwy zmiennych w celu eliminacji antyzależności oraz zależności właściwej, pozostała zależność właściwa St1 St2 St3 St4 dt,do St0:S0  0 St1:S1  S0 + A1 St2:S2  S1 + A2 St3:S3  S2 + A3 St4:S4  S3 + A4

12 Usuwanie zależności - przykładPo prostych przekształceniach arytmetycznych otrzymujemy następujący „program” i graf zależności St1 St2 St3 t St1:S2  A1 + A2 St2:S3  A3 + A4 St3:S4  S2 + S3

13 Redukcja wysokości drzewaRozważmy następujący przykład: SUM := 0; DO 10 J := 1,8; 10: SUM := SUM + A(J);

14 Identyfikacja zależnościCzy istnieje zależność pomiędzy dwoma odwołaniami do macierzy wewnątrz pętli ? Załóżmy, że indeksy macierzy są afiniczne (jedno wymiarowa macierz jest afiniczna jeśli możemy się do niej odwołać wykorzystując wyrażenie a*i+b, gdzie a i b są stałymi oraz i jest indeksem pętli). Wynika stąd , że odpowiedź na nasze pytanie polega na sprawdzeniu czy dwie afiniczne funkcje mogą przyjmować tą sama wartość dla różnych indeksów wewnątrz zakresu pętli.

15 Identyfikacja zależnościRozważmy następujący prosty przykład Załóżmy, że zapisujemy pewną wartość w elemencie macierzy o indeksie a*i+b oraz odczytujemy z tej samej macierzy z elementu o indeksie c*i+d, gdzie i jest indeksem pętli z zakresu od m do n. Zależność będzie istniała jeśli: Istnieją dwa indeksy pętli j i k w jej zakresie, tzn. m<= j<= n, m<=k<= n, takie, że najpierw zapisywany jest element macierzy o indeksie a*j+b a następnie odczytywany jest z macierzy element o indeksie c*k+d i a*j+b = c*k+d.

16 Identyfikacja zależnościJak możemy rozwiązać równanie a*j+b = c*k+d ? W ogólnym przypadku nie można rozwiązać tego równania ponieważ w czasie kompilacji wartości a,b,c i d nie są znane W naszym przypadku istnieje jednak test umożliwiający sprawdzenie czy zależność istnieje czy nie. Jest to tak zwany GDE test – test największego wspólnego podzielnika Test ten bazuje na obserwacji, że tzw. loop-carried zależność istnieje jeśli GCD(c,a) dzieli (d-b) (to znaczy, że jeśli dzieli się jedną liczbę całkowitą przez drugą nie mamy reszty)

17 Identyfikacja zależnościZastosujmy test GDC to następującego prostego przykładu: for (I=1; I<=100; I=I+1) { X[2*I+3] = x[2*I]*5.0; } Wartości wynoszą odpowiednio a = 2, b=3, c = 2 i d = 0 Stąd GDC(2,2) = 2, i d-b = -3 2 nie dzieli –3 Więc nie ma zależności

18 Wektoryzacja Proces wektoryzacji polega na przekształceniu kodu sekwencyjnego na wektorowy. Oryginalna pętla for(I=1,I<=N,I++) { A(I) = B(I) * C(I) D(I) = B(I) * K } Zmodyfikowana pętla A(I:N) = B(I:N) * C(I:N) D(I:N) = K * B(I:N)

19 Rozwijanie pętli Realizowany jest podział pętli na wiele pętli, w szczególności możemy uzyskać pełne rozwinięcie pętli w kod „sekwencyjny” ORIGINAL LOOP UNROLLED LOOP for (i=0; i == 100; i = i + 1) for (i=0; i == 99; i = i + 2) a[i] = b[i+2] * c[i-1]; { a[i] = b[i+2] * c[i-1]; a[i+1] = b[i+3] * c[i] }