1. Funkcja afiniczna, dostępy afiniczne.

Funkcję jednej lub wielu zmiennych nazywamy afiniczną, jeżeli może być ona przedstawiona jako suma stałej i oraz stałej wielokrotności zmiennych.

Dostęp do elementów tablicy jest afiniczny jeżeli granice pętli i indeks każdego wymiaru tablicy jest określony wyrażeniem afinicznym, którego zmiennymi są indexami otaczających pętli i stałych symbolicznych.

2. Architektura UMA

Najpopularniejsza architektura systemu wieloprocesorowego o wspólnej przestrzeni adresowej pamięci. Komunikacja odbywa się za pomocą pamięci. Używa spójnego protokołu pamięci podręcznej aby ukryć obecność pamięci podręcznej przed programistą. Gdy procesor chce zapisać do linijki pamięci podręcznej , kopie z innych bloków pamięci są usuwane. Gdy danych nie ma w pamięci podręcznej są pobierane z pamięci operacyjnej lub z pamięci podręcznej innego procesora.

3. Architektura NUMA

Zamiast pamięci, która jest równie daleko dla każdego procesora, rozproszono bloki wspólnej pamięci operacyjnej tak, żeby każdy procesor mógł szybciej uzyskać dostęp do jego pamięci lokalnej. Architektura NUMA zapewnia wspólną przestrzeń adresową dla oprogramowania, dzięki czemu procesory komunikują się poprzez zapisywanie do/odczytywanie danych z pamięci współdzielonej.

4. Systemy z przesyłaniem komunikatów

W maszynach z przesyłaniem komunikatów procesory mają rozłączne przestrzenie adresowe, one komunikują się poprzez wysłanie wiadomości. Należy pamiętać, że mimo tego, że pisanie kodu dla maszyny z pamięcią dzieloną jest prostsze, oprogramowanie musi mieć dobrą lokalność, żeby uzyskać wysoką wydajność.

5. Stopień równoległości

Stopień rownoległości to miara jaką determinuje się jak wiele operacji może zostać wykonanych jednocześnie. Stopień rownoległości gniazda pętli odpowiada ilości zagnieżdżonych możliwych do zrownoleglenia pętli w tym gnieździe. Pętla ma `k' stopni równoległości, jeżeli zawiera wewnątrz gniazda ma `k' pętli możliwych do zrównoleglenia. Mówimy że pętla jest idealnie zagnieżdżona, jeżeli wszystkie instrukcje umieszczone są w najgłębszej (najbardziej zagnieżdżonej) pętli.

6. Prawo Amdahla

Rozmiar części sekwencyjnej algorytmu rownoległego ogranicza przyspieszenie obliczeń rownoległych, niezależnie od liczby procesorow użytych do przetwarzania.

Z prawa Amdahla wynika, iż bez względu na liczbę użytych procesorow, uzyskane przyśpieszenie będzie ograniczone do wartości 1/f s

7. Równoległość grubo- i drobno-ziarnista

W przetwarzaniu równoległym ziarnistość kodu wyznacza ilość obliczeń programu

pomiędzy zdarzeniami synchronizacji lub komunikacji. Ze względu na wielkość ziarna obliczeń w przetwarzaniu równoległym wyróżnia się podział grubo- i drobnoziarnisty.

*Grubo ziarnista - „relatywnie” dużo instrukcji do wykonania pomiędzy zdarzeniami synchronizacji/komunikacji. Zalecana w OpenMP ze względu na narzuty w tworzeniu i zarządzaniu wątkami.

*Drobno ziarnista - „relatywnie” mało instrukcji do wykonania pomiędzy zdarzeniami. Zalecany przy

wykorzystaniu GPU, ze względu na inną architekturę tych procesorów oraz ilość i rodzaje pamięci

Granulacja ma wpływ na bilansowanie obciążenia.

8. Kod SPMD

Single Program Multiple Data. Oznacza to, że ten sam kod wykonywany jest dla wielu różnych danych przez różne procesory. Jest on sparametryzowany poprzez unikalny identyfikator przypisany do każdego z procesorów, tak, że każdy z nich może wykonywać inne akcje. Zwyczajowo kod SPMD jest wykonywany w modelu fork-join. Preferowane jest zrównoleglanie najbardziej zewnętrznej pętli w programie, gdyż implikuje to gruboziarnistą granulację.

9. Lokalność czasowa i lokalność przestrzenna

Wyróżniamy dwa rodzaje lokalności danych:

*Czasowa - kiedy te same dane są wykorzystywane w przeciągu niewielkiego odstępu czasu

*Przestrzenna - kiedy różne dane ulokowane są obok siebie w pamięci i używane w niewielkich odstępach czasu

10. Przestrzeń iteracji, przestrzeń danych i przestrzeń procesorów

W teorii transformacji afinicznych wyróżniamy 3 „przestrzenie”:

*Przestrzeń iteracji: jest to zbiór iteracji, których identyfikatory są definiowane przez wartości zmiennych indeksujących danej pętli. pętla o głębokości d ma d indekserów. Przestrzeń iteracji jest ograniczana przez górną i dolną granicę wartości, które przyjmuje zmienna indeksująca

*Przestrzeń danych jest to zbiór elementów zmiennej tablicowej do których odwołujemy się w danej pętli. Jest bezpośrednio definiowana przez deklarację tablicy.

*Przestrzeń procesorów jest to zbiór procesorów w systemie. Zazwyczaj mają one unikatowe identyfikatory

11.Lokalność sekwencyjnego kodu mnożenia macierzy

Z racji iż do wyprodukowania jednego elementu macierzy C potrzebujemy potrzebujemy oczytać jedną całą kolumnę macierzy B będzie występowało bardzo dużo nietrafień pamięci podręcznej gdy rozmiar macierzy będzie większy od ceche. Aby temu zapobiec należało zastosować blokowanie bądź macierz B trzymać w postaci kolumnowej.

12. Lokalność równoległego kodu mnożenia macierzy

Zrównoleglając wiersz po wierszu dochodzi nam problem wąskiego gardła związanego z wczytywaniem do pamięci podręcznej z pamięci operacyjnej gdyż musimy dostarczyć do pamięci podręcznej każdego procesora całą macierz B. Wzrost ilości procesorów może powodować spadek wydajności zamiast wzrostu.

13. Interferencja pamięci podręcznej

Interferencja zachodzi w sytuacji, gdy wiersz pamięci podręcznej zawierający dane, które można ponownie użyć w programie, zostaje nadpisany nowymi danymi pomimo, że w pamięci podręcznej jest wolne miejsce, w którym można byłoby ulokować nowo wprowadzane dane

14. Wielościan wypukły

Funkcja afiniczna zewnętrznej pętli i ograniczenia górne i dolne dzielą przestrzeń iteracja na 2 podprzestrzenie.

*Przestrzeń pozytywną (dodatnia) - iteracje znajdujące się w pętli

*Przestrzeń negatywną (ujemną) - iteracje poza pętlą

Logiczna koniunkcja tych ograniczeń (AND) tworzy w przestrzeni przecięcie pozytywnych przestrzeni które to tworzą wielościan wypukły będący graficzną reprezentacją przestrzeni iteracji danej pętli. Wielościan wypukły to taki wielościan, w którym połączenie prostą dwóch dowolnych punktów tego wielościanu nie przecina jego ściany. Iteracje pętli są reprezentowane jako wszystkie punkty o współrzędnych całkowitych wewnątrz takiego wielościanu określonego granicami, tym samym, wszystkie punkty wewnątrz tego wielościanu reprezentują pewną iterację pętli.

15. Kolejność leksykograficzna wykonywania iteracji pętli

Wektor i = [i0, il , . . . , in] jest leksykograficznie mniejszy niż wektor i' = [i0', il' , . . . , in'], co zapisujemy jako: i @symbol{-<}}i' , wtedy i tylko wtedy gdy istnieje m < min(n, n') takie, że [i0, il , . . . , im,] = [i0', i1' , . . . , im'] oraz i(m+l) < i(m'+1). Należy zauważyć, że m = 0 jest możliwe.

Wykonywanie sekwencyjne iteracji gniazda pętli jest to wykonywanie iteracji w przestrzeni iteracji w rosnącej kolejności leksykograficznej, czyli każda kolejna iteracja jest leksykograficznie większa od poprzedniej. [1 2 0 1] @symbol{-<} [1 2 0 2], m=3

16.Zapis matematyczny przestrzeni iteracji pętli

Dla pętli o głębokości d, przestrzeń iteracji może być zapisana w postaci: {i in Z I B i + b ≥ 0 }, gdzie 1. Z reprezentuje zbiór wszystkich liczb całkowitych - dodatnich, ujemnych oraz zero. 2. B jest to macierz liczb całkowitych o wymiarze d x d, 3. b jest to wektor liczb całkowitych o długości d, 4. 0 jest to wektor, którego wszystkie d elementów są zerami.

17. Co to jest projekcja?

Projekcja - zwana też rzutem/cieniem, geometrycznie jest przedstawieniem danej figury za pomocą figury o N wymiarów mniejszej. Rzutowanie wielościanu przestrzeni iteracji oznacza eliminację jednej z jego pętli. Dzięki temu możemy znaleźć granice zewnętrznej pętli poprzez rzutowanie przestrzeni iteracji na zewnętrzny wymiar tej przestrzeni. Do obliczania projekcji używa się najczęściej algorytmu eliminacji Fouriera-Motzkina.

18. Eliminacja Fouriera-Motzkina

Metoda Fouriera-Motzkina pozwala na wyznaczanie projekcji. Redukuje ona wymiarowość poprzez eliminację zadanych wymiarów z danego wielościanu. Załóżmy, że C zawiera wszystkie nierówności zmiennej xm (do eliminacji). Dla każdej pary ograniczeń dolnych i górnych zmiennej xm w C:

L ≤ c1*xm

c2*xm ≤ U

utwórz nowe nierówności postaci:

c2*L ≤ c1*U, gdzie c1 oraz c2 to liczby całkowite, natomiast L oraz U mogą być dowolnymi wyrażeniami zawierającymi zmienne inne niż xm.

Jeżeli c1 oraz c2 mają wspólny dzielnik, podziel obie strony przez ten dzielnik. Jeżeli nierówności nie są spełnione, to oznacza że nie ma rozwiązania. Na wyjściu dostajemy wielościan ubogi o nierówności wyeliminowanej zmiennej, ale za to z nierównościami utworzonymi wcześniej.

19. Algorytm obliczania granic dla danej kolejności indeksów pętli.

Algorytm generuje granice dla zmiennych iterujących pętli począwszy od najbardziej wewnętrznej pętli. Wyznaczamy dolne i górne granice dla indeksu ostatniej pętli, a następnie dokonujemy eliminacji (projekcja eliminacją Fouriera-Motzkina) usuwając ten wymiar i traktując następny jako najbardziej zagnieżdżony. Powtarzamy aż do wyznaczenia wszystkich granic. W kolejnym kroku dokonujemy w pętli usunięcia wszystkich nadmiarowych ograniczeń.

20. Dostęp do tablicy przez krotkę: (F, f, B, b)

Każdy afiniczny dostęp może być opisany za pomocą dwoch macierzy oraz dwoch wektorow. Pierwsza para macierz-wektor [B, b] opisuje przestrzeń iteracji dostępu. Druga para [F, f] reprezentuje zależność pętla-zmienna indeksująca tworzącą indeks tablicowy używany w rożnych wymiarach dostępu afinicznego do zmiennych tablicowych. Formalnie, możemy reprezentować dostęp do tablicy w gnieździe pętli przez krotkę: (F, f, B, b), która odwzorowuje wektor i w granicach przestrzeni iteracji: B*i+b>=0 na lokalizację elementu tablicy F*i+f

21. Ponowne użycie danych: samo-użycie, grupowe

Wielokrotne użycie tych samych danych. Z funkcji dostępu do tablicy możemy wyciągnąć informacje przydatne dla optymalizacji lokalności i zrównoleglenia. Możemy zidentyfikować zbiory iteracji, które odwołują się do tych samych danych i znaleźć wszystkie zależności.

Dostęp statyczny: Jeśli instrukcja odwołuje się do danych w tej samej iteracji.

Dostęp dynamiczny: Jeśli instrukcja odwołuje się do danych w różnych iteracjach.

Ponowne samo-użycie - ponowne użycie pochodzi ze statycznego dostępu

Ponowne użycie grupowe: ponowne użycie pochodzi z innego niż statycznego dostępu

Ponowne użycie czasowe: odwołanie następuje do tej samej komórki

Ponowne użycie przestrzenne: ponowne użycie danych z tej samej linijki cache

Ponowne samo-użycie danych może znacząco zwiększyć lokalność kodu.

22. Rząd macierzy, przestrzeń zerowa macierzy, nicość przestrzeni zerowej

Rząd macierzy - największa ilość wierszy lub kolumn, które są liniowo niezależne, tj nie można ich

przedstawić za pomocą kombinacji pozostałych wierszy/kolumn

- Przestrzeń zerowa - zbiór wszystkich rozwiązań równania:

F(i - i') = 0, gdzie i oraz i' - dwie iteracje.

Dwie iteracje odnoszą się do tego samego elementu tablicy jeżeli różnica pomiędzy wektorami indeksów pętli należy do przestrzeni zerowej macierzy F. Wektor zerowy spełnia równanie (czyli to jest ta sama iteracja).

- Nicość - różnica między wymiarem macierzy a jej rzędem. Jeżeli macierz F jest pełnego rzędu to przestrzeń zerowa macierzy F składa się jedynie z zerowego wektora. W takim wypadku wszystkie iteracje w gnieździe pętli odwołują się do rożnych danych.

23. Jak można oszacować w sposób matematyczny lokalność czasową?

24. Jak można oszacować w sposób matematyczny lokalność przestrzenną?

25. Pojęcie zależności, rodzaje zależności

Mówimy, że dwa odwołania są zależne, jeżeli odwołują się do tych samych danych (tego samego miejsca w pamięci) i przynajmniej jedno z nich jest operacją zapisu. Musimy zapewnić, że w równoległym programie wszystkie zależności są honorowane to znaczy porządek pomiędzy każdą parą wywołań operacji posiadających zależność danych jest taki sam jak w programie sekwencyjnym. Występują najczęściej 3 rodzaje zależności:

● Prawdziwa zależność -> zapis-odczyt tej samej lokacji

● Anyt-zależność -> odczyt- zapis tej samej lokacji

● Zależność po wyjściu - zapis-zapis tej samej lokacji

26. Układ matematyczny do wyznaczenia zależności

Rozważamy statyczny dostęp do tej samej tablicy w różnych iteracjach. Mając 2 instrukcje dostępu:

Ø = (F, f, B, b) dla pętli o głębokości d

Ø' = (F', f', B', b') dla pętli o głębokości d'

to te dostępy są zależne jeżeli:

● Co najmniej jeden z nich jest operacją zapisu

● Istnieją wektory i oraz i' w zbiorze liczb całkowitych (Z) takie że:

○ B*i >=0 (dla przestrzeni teracji i)

○ B'*i' >= 0 (dla przestrzeni teracji i')

○ F*i + f = F'*i'+f' (występuje zależność - wskazanie na ten sam element tablicy)

27. Ograniczenia Partycjonowania Przestrzeni

Program nie wymaga synchronizacji, jeżeli dla każdej pary czwórek

Ø = (F, f, B, b) zależność instrukcji s1 zagnieżdżonej w d1 gniazdach oraz

Ø' = (F', f', B', b') zależność instrukcji s2 zagnieżdżonej w d2 gniazdach

Partycje (C1, c1) oraz (C2, c2) spełniają zależności: Dla każdego wektora i oraz i' w zbiorze liczb całkowitych: i, i' - nieznane wektory iteracji

B1*i1 + b1 >=0 (wszystkie iteracje dla i1)

B2*i2 + b2 >=0 (wszystkie iteracje dla i2)

F1*i1 + f1 = F2*i2 +f2 (iteracje i1 oraz i2 są zależne - odwołanie do tej samej komórki pamięci)

C1*i1 + c1 = C2*i2 + c2 (szukamy takich C, c, że zależne iteracje zostaną przypisane do tego samego

procesora) Próbujemy znaleźć takie rozwiązanie, które da nam największy stopień równoległości.

Iteracje odwołują się do tej samej komórki pamięci:

F1*i1 + f1 = F2*i2 +f2

Więc należy je przydzielić do tego samego procesora:

C1*i1 + c1 = C2*i2 + c2

28. Jak korzystamy ze znalezionej transformacji afinicznej do partycjonowania przestrzeni?

29. Generacja kodu dla transformacji afinicznych partycjonowania przestrzeni

Zasadnicza idea jest następująca: Dane są granice dla indeksów gniazda pętli oraz partycje przestrzeni dla poszczególnych instrukcji pętli. Najpierw tworzymy pętlę zewnętrzną (równoległą), która iteruje identyfikatory procesorów. To jest każda iteracja tej pętli wykonuje operacje przydzielone do określonego procesora. Oryginalny program jest wstawiany jako ciało tej pętli; ponadto, instrukcja warunkowa dodaje się w taki sposób aby każdy procesor wykonywał tylko operacje przypisane do niego. W ten sposób możemy zagwarantować, że procesor wykonuje wszystkie instrukcje przypisane do niego, i czyni to w oryginalnej kolejności. Np. dla dwóch instrukcji s1 i s2: s1 jest mapowana do procesora p1, a s2 do p2. Generacja kodu zawiera trzy kroki:

1. Dla każdej instrukcji, należy znaleźć identyfikatory wszystkich procesorów, które dokonują obliczeń.

2. Znajdź identyfikatory wszystkich procesorów biorących udział w wykonaniu wszystkich instancji instrukcji (np. unia zestawu identyfikatorów z punktu 1).

3. Generuj kod sekwencyjny do wykonywania obliczeń w każdej partycji.

30. Transformacja podziału pętli

s1: i=p, s2: j=p

Transformacja dzieli pojedynczą pętlę na dwie o identycznych indeksach. Przydatna do:

- zastosowania transformacji wymiany pętli,

- zwiększenia lokalności przez zmniejszenie całkowitej ilości danych, do których odwołuje się każda pętla. Zwiększenie lokalności ma miejsce, kiedy wynik produkowany przez jedną instrukcję nie jest konsumowany przez inne w tej samej iteracji.

31. Transformacja scalenia pętli

s1:p=i , s2:p=j

Transformacja ta scala sąsiednie pętle o identycznych indeksach i granicach w jedną pętlę.

Transformacja ta jest przydatna do:

- zmniejszenia czasu wykonywania pętli -redukcja czasu obsługi wykonywania pętli,

- zwiększenia granulacji obliczeń pętli,

- poprawy lokalności poprzez odwołanie się do tej samej tablicy.

32. Transformacja wymiany pętli

i'=j, j'=i

Transformacja ta wymienia pętle miejscami. Często stosowana jest w celu zwiększenia lokalności przestrzennej - dopasowanie do sposobu przechowywania elementów tablic(wierszami lub kolumnami). Może zmniejszyć czas wykonywania pętli nawet do 10 razy.

33. Transformacja odwrócenia iteracji pętli

p=N-i

Odwrócenie wykonywania iteracji może zwiększyć lokalność

34. Transformacja przekoszenia iteracji pętli

p1=i-j, p2=j+1

Loop skewing pozwala na wymianę pętli

35. Transformacja blokowania

Jest to sposób zmiany kolejności iteracji pętli dzięki któremu można znacznie zwiększyć lokalność. Zamiast obliczać wynik w wierszu lub kolumnie, dzielimy całkowitą macierz iteracji na podmacierze albo bloki. Dzięki temu wykorzystujemy dane które przed chwilą wyprodukowaliśmy. Najczęściej bloki są kwadratami o boku długości B, oczywiście jeśli liczba iteracji nie dzieli się przez B, ostatni blok będzie krótszy. Zalety:

▪ zwiększenia lokalności danych - wszystkie dane potrzebne w bieżącym bloku będą w cache,

▪ zmniejszenie narzutu obliczeń potokowych,

▪ komunikacja wyłącznie pomiędzy kolejnymi blokami,

▪ poprawia lokalność kodu,

▪ użyteczne tylko gdy rozmiar wszystkich danych programu jest większy od rozmiaru pamięci podręcznej.

36. Graf zależności danych a znalezienie równoległości

Graf zależności programu jest to graficzna reprezentacja zależności. Węzły w takim grafie są instrukcjami przypisania, natomiast krawędzie wskazują na zależności danych, strzałki krawędzi wskazują kierunek zależności między danymi (węzeł od ktorego wychodzi strzałka produkuje dane i wskazuje na węzeł, ktory z tych danych korzysta). Graf zależności pozwala ocenić, czy możemy rozbić instrukcję wewnątrz pętli na osobne pętle.

37. Transformacje unimodularne

Transformacja reprezentowana jest jako unimodularna macierz wspołczynnikow oraz nie stały wektor. Macierz unimodularna jest macierzą kwadratową, ktorej wspołczynnik wynosi 1 lub -1. Transformacja unimodularna mapuje n-wymiarową przestrzeń iteracji w inny n-wymiarowy wielościan, przy zachowaniu relacji iteracji w skali 1:1.

38. Pętle całkowicie wymienne

Gniazda pętli są całkowicie zamienne gdy można dowolnie zmieniać ich kolejność bez potrzeby

wprowadzenia zmian w ciele pętli (wszystkie zależności są honorowane). Dzięki temu można wprowadzić mechanizm obliczeń potokowych dla k-1 pętli oraz zastosować transformacje blokowania w celu zwiększenia lokalności danych.

39. Ograniczenia partycjonowania czasu

Partycjonowanie czasu mówi, że w przypadku dwóch zależnych operacji, należy w wynikowej (zewnętrznej )pętli przydzielić operację zależną do późniejszej iteracji niż operację niezależną. Jeżeli występują one w tej samej iteracji zasada pozostaje taka sama. Partycjonowaniem czasu jest dozwolone tylko wtedy, gdy dla każdych dwóch dostępów zależnych:

Φ1 = (F1, f1, B1, b1) - wyrażenie s1 zawarte w pętli d1

Φ2 = (F2, f2, B2, b2) - wyrażenie s2 zawarte w pętli d2

jednowymiarowe mapowanie partycjonowania (C1, c1) i (C2,C2) odpowiednio dla wyrażeń s1 i s2 spełnia zasady partycjonowania czasu:

◦ i1 @symbol{-<} i2 , (i1 leksykograficznie mniejszy od i2)

◦ B1⋅i1⩾0 , (wektor i1 zawiera się w przestrzeni iteracji d1)

◦ B2⋅i2⩾0 , (wektor i2 zawiera się w przestrzeni iteracji d2)

◦ F1⋅i1+f 1=F2⋅i2+f 2 , (operacja na tym samym elemencie macierzy)

spełniona jest nierówność:

C1⋅i1+c1⩽C2⋅i2+c2 (s1 wykona się przed s2)

Jest to jednak złagodzenie wymogów partycjonowania przestrzeni. Jeżeli dwie iteracje odnoszą się do tej samej lokacji, to nie muszą one być mapowane do tej samej partycji. Jedynym wymogiem jest zapewnienie, że oryginalne wzajemne wykonanie dwóch iteracji jest zachowane. Oznacza to, że wymóg w przypadku partycjonowania czasu określony jest znakiem <=, podczas gdy w przypadku partycjonowania przestrzeni wymóg posiadał znak =.

40. Lemat Farkas'a

Niech A będzie macierzą liczb rzeczywistych o wymiarze m x n; niech c będzie niezerowym wektorem liczb rzeczywistych o wymiarze n. Lemat Farkas'a mówi, że pierwotny układ nierówności

Ax> = 0, c'x <0

lub dualny układ

A'y = c, y> = 0

gdzie „' ” jest operatorem transpozycji, ma rozwiązanie w liczbach rzeczywistych, ale nigdy oba.

41. Transformacje partycjonowania czasu a pętle całkowicie wymienne

Jeżeli istnieje k niezależnych rozwiązań dla ograniczeń partycjonowania czasu, to można przekształcić gniazdo pętli tak, żeby k najbardziej zewnętrznych pętli były w pełni wymienne. Możemy te pętle też przekształcić do przetwarzania potokowego o stopniu k-1 lub by k-1 wewnętrznych pętli było równoległych. Ponadto, możemy zastosować technikę blokowania do pętli w pełni wymiennych w celu poprawy lokalności kodu.

42. Transformacje partycjonowania czasu a przetwarzanie potokowe

Przetwarzanie potokowe to dekompozycja iteracji w pętli na „fazy” przetwarzania danych wykonywane przez rożne procesory ktore przekazują wyniki obliczeń do następnego procesora. Dla przykładu zadanie wykonywane przy pomocy pętli z i iteracjami można wykonać przy pomocy potoku z i procesorow kiedy jeden procesor kończy przekazuje wynik do kolejnego procesora w potoku.

Przetwarzanie potokowe może być zastosowane w pętli o zagnieżdżeniu minimum 2 gdzie iteracje pętli zewnętrznej będą traktowane jako zadania a pętle wewnętrzne jako „fazy” przetwarzania.

Zadania wykonywane w potoku mogą dzielić zależności ponieważ każde zadanie jest wykonywane tylko przez jeden procesor jednocześnie.

43. Transformacje partycjonowania czasu a transformacja blokowania

Jeśli istnieje k niezależnych rozwiązań ograniczenia partycjonowania czasu danego gniazda pętli, możliwa jest transformacja tego gniazda do postaci posiadającej k zewnętrznych w pełni zamiennych pętli, ktore mogą zostać przekształcone do k-1 stopni potokowości, lub k-1 wewnętrznych, możliwych do zrownoleglenia pętli. Co więcej, możemy zastosować blokowanie dla w pełni wymiennych pętli w celu zwiększenia lokalności danych procesora, jak rownież redukcji synchronizacji pomiędzy procesorami podczas przetwarzania rownoległego.

44. Fala frontowa

Dla k pętli w pełni wymiennych możemy wygenerować k-1 pętli równoległych. W tym celu tworzymy indeks i' będący kombinacją liniową wszystkich indeksów z k pętli. Tworzymy zewnętrzną pętlę sekwencyjną z indeksem i', która skanuje iteracje w porządku rosnącym. Obliczenia reprezentowane przez pętle wewnętrzne są wykonywane równolegle.

---