Automatyczne zrównoleglanie kodu
W zależności od architektury komputera równoległego oraz sposobu, w jaki organizuje on dostępną pamięć operacyjną,
zależy też sposób jego oprogramowywania. Inaczej pisze się programy pod maszyny z pamięcią współdzieloną, a inaczej
z pamięcią rozproszoną. Jedną z najprostszych technik wykorzystywania mocy drzemiącej
w komputerach równoległych jest tzw. automatyczne zrównoleglanie kodu na poziomie kompilatora (realizowane za pomocą
odpowiednich flag i opcji). Kompilator analizuje program i wyszukuje zestawy niezależnych instrukcji, a także
niezależnych iteracji
w pętlach "for"1 podatnych na zrównoleglanie. Przy aplikacjach o nieskomplikowanej budowie, ta prosta metoda
zrównoleglania dobrze spełnia postawione przed nią zadanie. Jednak przy bardziej złożonych projektach programistycznych,
okazuje się praktycznie bezużyteczna. Wynika to z faktu, że kompilator nie jest w stanie automatycznie wychwycić
wszystkich operacji wymagających zrównoleglenia i z tego powodu stopień zrównoleglenia kodu (a co za tym idzie
przyśpieszenie skompilowanego programu) jest relatywnie na niskim poziomie.
Zrównoleglanie bloków instrukcji
Zrównoleglanie kodu za pomocą OpenMP nie odbywa się w sposób automatyczny. Służą do tego specjalne
dyrektywy kompilatora, których programista używa do określenia miejsc i obszarów w kodzie programu,
jakie mają ulec zrównolegleniu. Mamy więc do czynienia ze wspomnianym już wcześniej "zrównoleglaniem
przyrostowym". Inną zaletą stosowania dyrektyw kompilatora jest ich "przeźroczystość" dla kompilatora.
Jest to bardzo przydatne w sytuacjach, gdy w kompilatorze występują kłopoty z obsługą wielowątkowości.
Przypuśćmy, że chcemy skompilować program pod kompilatorem, który nie posiada biblioteki do obsługi
dyrektyw OpenMP. Okaże się, że program zostanie skompilowany prawidłowo. W tego typu sytuacjach dyrektywy
OpenMP są po prostu pomijane, a program kompiluje się bez użycia wielowątkowości.
Najistotniejszą i zarazem najbardziej podstawową konstrukcją OpenMP jest dyrektywa OMP PARALLEL. Służy
ona do wyznaczenia bloku instrukcji w kodzie programu, które mają zostać wykonane w sposób równoległy.
Części programu nie objęte dyrektywą OMP PARALLEL, będą wykonywane sekwencyjnie. Kiedy główny wątek
programu dotrze do obszaru zrównoleglania, natychmiast powołuje do życia nową grupę wątków, z którą
wspólnie rozpoczyna równoległe przetwarzanie danych3. Wątek, który odkrywa jako pierwszy istnienie
obszaru zrównoleglania, staje się liderem nowopowstałej grupy wątków. Jest to wątek typu master. Każdy
wątek posiada swój unikalny numer, służący do jego identyfikacji w grupie. Numeracja rozpoczyna się
od 0 (wątek typu master) do n-1, gdzie n to maksymalna ilość wątków, określana przez programistę w
trakcie uruchamiania programu.
#pragma omp parallel { // obszar zrównoleglania } // obszar kodu wykonywany sekwencyjnie
Zrównoleglanie pętli "for"
Wiedząc już jak łatwo możemy wprawić w ruch serię wątków i zaprząc je do równoczesnej pracy na określonym
bloku danych, warto przyjrzeć się kolejnej konstrukcji OpenMP, która znacznie rozszerza możliwości zrównoleglania
kodu. Chodzi o dyrektywę OMP FOR, która służy do równoległego przetwarzania danych w pętlach for. Jest to
najpopularniejsza konstrukcja z zestawu dyrektyw OpenMP. Za jej pomocą, możemy podzielić pracę związaną z
wykonywaniem kolejnych iteracji pętli for pomiędzy różne wątki. W efekcie, wykonywanie pętli odbywa się
znacznie szybciej. Jedynym ograniczeniem konstrukcji OMP FOR jest liczba iteracji, a dokładnie czy jest to
wartość znana przed wprawieniem w ruch pętli for. Aby wątki mogły przetwarzać dane równolegle, to wartość
ta musi być z góry ustalona. Poniżej znajduje się ciekawy przykład kodu ilustrującego sposób, w jaki iteracje
mogą być dystrybuowane między różnymi wątkami.
#pragma omp parallel { #pragma omp for for (i=0; i<9; i++) printf("Wątek %d przetwarza iterację numer: %d\n", omp_get_thread_num(),i); }
Zadaniem powyższej pętli for jest rozdzielenie pracy związanej z przetworzeniem dziewięciu iteracji pomiędzy grupę kilku wątków. Wynikiem działania pętli są informacje wyświetlane na ekranie. Dzięki nim dowiemy się, która iteracja była obsługiwana przez jaki wątek. Do określenia numeru aktualnie działającego wątku używać można funkcji omp_get_thread_num(). Po uruchomieniu programu dla 3 wątków (czyli grupy wątków o numerach 0,1,2), pętla for może zwrócić następujące wyniki:
Wątek 0 przetwarza iterację numer: 0 Wątek 0 przetwarza iterację numer: 1 Wątek 0 przetwarza iterację numer: 2 Wątek 1 przetwarza iterację numer: 3 Wątek 1 przetwarza iterację numer: 4 Wątek 1 przetwarza iterację numer: 5 Wątek 2 przetwarza iterację numer: 6 Wątek 2 przetwarza iterację numer: 7 Wątek 2 przetwarza iterację numer: 8
Jak widać, iteracje zostały równomiernie rozdzielone pomiędzy dostępne wątki. Aby mieć pełną kontrolę nad sposobem dystrybucji zadań (iteracji) między wątkami stosuje się klauzulę schedule. Dzięki niej, jesteśmy w stanie z góry określić ile iteracji przypadnie do przetworzenia na jeden wątek. Co więcej, możemy także wskazać sposób łączenia wątków z kolejnymi blokami iteracji. Standardowo wątki przypisywane są statycznie (static), zaczynając od wątku z numerem 0, który przetwarza pierwszy blok iteracji. Następne bloki przypisywane są kolejnym wątkom według ich numeru identyfikacyjnego. Jeżeli bloków iteracji jest więcej niż wątków, nadwyżka ta przydzielana jest po kolei wszystkim dostępnym wątkom (zaczynając od wątku 0). Aby lepiej zilustrować strategię statycznego przydzielania wątków do bloków iteracji, zmodyfikowano nieco kod pętli for z poprzedniego przykładu.
#pragma omp parallel { #pragma omp for schedule (static,2) for (i=0; i<9; i++) printf("Wątek %d przetwarza iterację numer: %d\n", omp_get_thread_num(),i); }
Założono, że każdemu wątkowi będą przydzielone po dwie iteracje do przetworzenia (liczbę tą określa dodatkowy
parametr w klauzuli schedule). Wynik działania tak zmodyfikowanej pętli dla trzech wątków może wyglądać
następująco:
Wątek 0 przetwarza iterację numer: 0 Wątek 0 przetwarza iterację numer: 1 Wątek 0 przetwarza iterację numer: 6 Wątek 0 przetwarza iterację numer: 7 Wątek 1 przetwarza iterację numer: 2 Wątek 1 przetwarza iterację numer: 3 Wątek 1 przetwarza iterację numer: 8 Wątek 2 przetwarza iterację numer: 4 Wątek 2 przetwarza iterację numer: 5
Wyniki nie są ułożone w poprawnej kolejności, wynika to z braku synchronizacji wyświetlania komunikatów za pomocą funkcji printf.
Nie jest to jednak ważne, sednem tych wyników są pary cyfr określające przynależność kolejnych iteracji do konkretnych wątków.
Każdy wątek otrzymał po kolei dwie iteracje do przeanalizowania. Z racji większej liczby bloków iteracji niż wątków, wątek 0
otrzymał dwa bloki (0-1 oraz 6-7), zaś ostatnią, ósmą iteracje wykonał następny w kolejności, wątek 1.
Statyczne przypisywanie iteracji to nie jedyna metoda zrównoleglania pętli for.
Wątki mogą dynamicznie pobierać określone partie iteracji i je przetwarzać. W takim przypadku nie można przewidzieć z góry
jakie iteracje zostaną przydzielone którym wątkom. W pętli for zrównoleglonej trybem dynamic, wątki nie otrzymują już ściśle
określonych iteracji do przetworzenia. Wiedzą jedynie jak duży blok iteracji pozwalamy im pobrać i przetworzyć. Kolejność
przydzielania wątkom bloków iteracji jest zależna tylko od tego, który wątek aktualnie jest wolny i gotowy do pracy. Każdy
wątek, po pomyślnym ukończeniu przetwarzania bloku iteracji zgłasza żądanie przydzielenia mu następnej porcji danych. Dzięki
dynamicznemu przydzielaniu pracy, wątki działają znacznie efektywniej. Nie ma przestojów w obliczeniach, ponieważ każdy wątek
po ukończeniu przydzielonej mu pracy pobiera i przetwarza kolejną porcję danych. Nie dochodzi też do sytuacji,
w której szybsze wątki kończą pracę i są bezczynne, czekając na wolniejszych "kolegów", którym statycznie przydzielono
trudniejszą porcję iteracji do przeanalizowania.
Pewną interesującą modyfikacją dynamicznego przetwarzania iteracji jest tryb guided. Zachowuje się on dokładnie tak samo
jak dynamic, z tą różnicą, że porcje danych przydzielane wątkom zmniejszają się wykładniczo. A więc z każdym kolejnym
przydziałem danych, wątki otrzymują mniej pracy.
Ostatnim trybem mającym wpływ na sposób przetwarzania pętli for jest klauzula runtime. Za jej pomocą możliwe jest
sprecyzowanie sposobu zrównoleglania pętli for dopiero w czasie uruchamiania programu. Odbywa się to za pomocą zmiennej
środowiskowej OMP_SCHEDULE. Zmienna ta może przyjmować wartości: static, dynamic lub guided. Ograniczeniem typu runtime
jest brak możliwości określenia jak duże bloki iteracji mają być przydzielane kolejno między wątki.
Wszystkie trzy główne metody równoległego przetwarzania pętli for zilustrowane zostały na poniższym wykresie (rys. 1).
Widać na nim, w jaki sposób może zachowywać się grupa czterech wątków w starciu z pętlą for wykonującą się 500 razy.
Pętla zrównoleglona jest po kolei w trybie guided, dynamic a na końcu static. Blok iteracji składa się z pięciu obrotów pętli.