Na poprzednich laboratoriach poznaliśmy podstawowe funkcje MPI do komunikacji punkt do punktu oraz do komunikacji grupowej. Na dzisiejszym laboratorium przećwiczymy pozostałe schematy komunikacji grupowej oraz komunikację nieblokującą. Dodatkowo, zobaczymy, jak można optymalizować programy współbieżne.
Komunikacja przez rozgłaszanie, którą poznaliśmy na ostatnich zajęciach, jest tylko jednym z przykładów komunikacji grupowej. Inne schematy komunikacji grupowej ujęte w funkcjach MPI to:
data data
P0: D1 D2 D3 D4 scatter P0: D1 -- -- --
P1: -- -- -- -- ------> P1: D2 -- -- --
P2: -- -- -- -- <------ P2: D3 -- -- --
P3: -- -- -- -- gather P3: D4 -- -- --
Więcej informacji o funkcjach można znaleźć w manualu. Przykład użycia schematu scatter-gather znajduje się w pliku scatter-gather-max.c.
Jak wspomnieliśmy na poprzednim laboratorium, semantyka operacji MPI_Send nie jest ściśle sprecyzowana. Nie ma żadnych gwarancji co do tego, że po opuszczeniu funkcji MPI_Send, wysyłany komunikat został odebrany (i przetworzony przez obiorcę). Nie ma nawet gwarancji, że odbiorca zaczął odbierać komunikat. MPI gwarantuje jedynie, że po powrocie z funkcji, obszar pamięci zajmowany przez komunikat może zacząć zostać modyfikowany oraz wspomina, że operacja MPI_Send może się zablokować. Ta ostatnia cecha sprawia w szczególności, że poniższy kod jest niepoprawny.
// Proces A: ... MPI_Send(..., processB, msgTagA, ...); MPI_Recv(..., processB, msgTagB, ...); ... // Proces B: ... MPI_Send(..., processA, msgTagB, ...); MPI_Recv(..., processA, msgTagA, ...); ...
Powodem jest fakt, że każdy z procesów A i B może się zablokować na swojej funkcji MPI_Send i w rezultacie żaden z nich nie będzie mógł zacząć odbierać komunikatu od drugiego procesu, co doprowadzi do zakleszczenia.
MPI udostępnia jednak operacje o bardziej sprecyzowanej semantyce (patrz odpowiednie strony manuala). Operacje te dzielą się na blokujące i nieblokujące. Przykłady operacji blokujących to:
Przykłady nieblokujących operacji natomiast to:
Przykład nieblokującej komunikacji znajduje się w pliku ring-nonblocking.c.
Więcej informacji o różnych semantykach komunikatów w MPI można znaleźć w podanej wyżej literaturze.
Równanie różniczkowe Laplace'a opisuje rozmaite ekwilibria w procesach fizycznych. Analiza takich procesów często sprowadza się do zdyskretyzowania równania wraz z warunkami brzegowymi i numerycznego rozwiązania powstałego układu równań. Jedną z używanych metod numerycznych jest metoda kolejnych nadrelaksacji. Program sekwencyjny realizujący wariant tej metody w dwóch wymiarach można znaleźć w pliku laplace-seq.c.
W programie tym zakładamy równanie Laplace'a w dwuwymiarowym układzie współrzędnych δ2(x, y)/δx2 + δ2(x, y)/δy2 = 0 wraz z pewnym warunkami brzegowymi. Równanie to jest zdyskretyzowane na siatce N x N równoodległych punktów.
Algorytm numeryczny przybliżający rozwiązanie równania działa następująco dla każdego punktu siatki (za wyjątkiem punktów brzegowych):
Aby zapewnić, że wartości punktów, z których liczona jest średnia (pkt. 2 powyższego algorytmu) pochodzą z tej samej iteracji, użyty jest algorytm szachownicowy. Punkty pokolorowane są na biało i czarno, jak szachownica. Każda iteracja składa się z dwóch faz: w pierwszej liczone są nowe wartości punktów białych (na podstawie starych wartości punktów czarnych), w drugiej — nowe wartości punktów czarnych (na podstawie nowych wartości punktów białych).
Mając dany szablon programu równoległego, spraw, aby program ten poprawnie rozwiązywał równanie Laplace'a na więcej niż jednym procesorze wykorzystując MPI do komunikacji pomiędzy procesami.
Po poprawnym zaimplementowaniu algorytmu, policz speed-up'y dla różnej liczby punktów i liczby procesów. Jakie są Twoje obserwacje?
Zoptymalizuj program równoległy tak, aby osiągał on lepsze wyniki. Zbadaj co jest wąskim gardłem. Postaraj się skrócić ścieżkę krytyczną oraz zrównoleglić obliczenia z komunikacją. (Szablon programu równoległego celowo zawiera pewne nieefektywności, aby było duże pole do optymalizacji.)
Ostatnia modyfikacja: 17/05/2016