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ą.
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 -- -- --
Dodatkowo, dość częstym mechanizmem synchronizacyjnym w aplikacjach równoległych jest tzw. bariera. Bariera to miejsce w kodzie aplikacji równoległej, do którego muszą dojść wszystkie procesy wykonujące tę aplikację, aby którykolwiek z procesów mógł przejść dalej. MPI udostępnia własną barierę, której używa się przy pomocy funkcji:
MPI_Barrier
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 wiadomo z matematyki, wartość liczby π można wyznaczyć przez całkowanie funkcji 4 / (x2 + 1) na przedziale 0...1 (dla zapominalskich wyjaśnienie np. tutaj). Napisz program wyznaczający liczbę π poprzez sumowanie metodą trapezów. Przedział 0...1 dzielimy na P podprzedziałów numerowanych od 0 do P - 1. Każdy i-ty z N procesów (gdzie i = 0,1,...,N-1 a N <= P) wylicza sumę pól trapezów wyznaczonych przez podprzedziały i + j * N, dla kolejnych j=0,1,2,... takich że i + j * N < P. Następnie używając odpowiedniego wariantu funkcji MPI_Reduce proces zerowy sumuje częściowe wyniki z każdego procesu i wypisuje wartość liczby π na standardowe wyjście.
Uruchom program na klastrze, dla P = 1000000 oraz N = 10. Wypisz π z precyzją co najmniej 10 cyfr po przecinku.
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.
Używając nieblokującej komunikacji MPI, zaimplementuj następujący rozproszony algorytm obliczający maksimum. Procesy są zorganizowane w logiczny pierścień. Następnikiem procesu i jest proces (i + 1) mod N, gdzie N to liczba procesów. Analogicznie definiujemy poprzednika. Każdy proces i przechowuje parę (liczba Li, ranga Ri). Algortym działa w rundach. W każdej rundzie każdy proces losuje liczbę l, zapisuje ją i swoją rangę i jako parę (Li, Ri) i przekazuje tę parę do następnika. Jeśli proces i dostanie parę (L(i - 1) mod N, R(i - 1) mod N) od poprzednika, to:
Jeśli para wróci do jakiegoś procesu j (co można sprawdzić po randze) to proces j wypisuje skojarzoną liczbę na standardowe wyjście jako obliczone maksimum, przekazuje parę do następnika i czeka na barierze. Jeśli dowolny proces k (różny od j) dostanie parę z maksimum, to wypisuje skojarzoną liczbę na standardowe wyjście jako wynik maksimum, przekazuje do następnego procesu (o ile nie jest to j) i czeka na barierze. Po przejściu bariery, algorytm rozpoczyna kolejną rundę.
Wskazówka: Zastanów się, jak sprawić, aby algorytm się zakończył.
Osoby zainteresowane komunikacją, odpornością na błędy i synchronizacją w środowiskach rozproszonych zapraszam na przedmiot systemy rozproszone.
Ostatnia modyfikacja: 16/03/2014