Na poprzednim laboratorium poznaliśmy podstawy MPI i nauczyliśmy się uruchamiać programy korzystające z MPI na klastrze ICM. Na dzisiejszym laboratorium zapoznamy się dokładniej ze standardowymi funkcjami MPI do komunikacji punkt do punktu oraz do komunikacji grupowej.
Rozważmy program "Hello world!", który mieliśmy stworzyć w ramach zadania z poprzednich zajęć. Można go także znaleźć w pliku hello-world-p2p.c.
Dla przypomnienia, mamy N procesów, numerowanych od 0..N-1. Procesy o numerach i ∈ {1..N-1} wysyłają komunikaty zawierające napis "Hello world from MPI process <i>!" do procesu o numerze 0, gdzie <i> jest numerem procesu. Natomiast proces o numerze 0 wypisuje otrzymane komunikaty na standardowe wyjście w kolejności numeru procesu nadawcy. Wynikiem uruchomienia naszego programu na 4 procesach będzie następujący ciąg napisów na standardowym wyjściu:
A parallel MPI-based "Hello world!" application. Hello world from MPI process 1! Hello world from MPI process 2! Hello world from MPI process 3!
Skupmy się na początek na funkcji użytej do wysyłania napisu przez niezerowy proces do procesu zerowego:
MPI_Send(
message,
messageLen,
MPI_CHAR,
dstProcessNo,
MPI_MESSAGE_HELLO_WORLD_TAG,
MPI_COMM_WORLD
);
Powyższa funkcja (man MPI_Send) przesyła komunikaty punkt-do-punktu, tj. od aktualnego procesu do dokładnie jednego procesu docelowego. Identyfikatorem/adresem procesu docelowego jest jego ranga (w naszym programie dstProcessNo równe 0) w komunikatorze będącym ostatnim parametrem funkcji (w naszym programie MPI_COMM_WORLD).
Wysyłany komunikat jest przekazywany do funkcji MPI_Send przez nietypowany wskaźnik (message w naszym programie). Jednakże, mimo użycia nietypowanych wskaźników do wysyłania (i odbierania), każdy komunikat w MPI ma określony format. Dokładniej, pojedynczy komunikat MPI jest tablicą elementów pewnego ustalonego przez użytkownika typu. Typ elementów tablicy jest opisywany przez trzeci parametr funkcji MPI_Send (w naszym przypadku jest to typ znakowy — MPI_CHAR), zaś liczba elementów w tablicy — przez drugi parametr (w naszym przypadku messageLen). W powyższym przykładzie wysyłamy więc tablicę messageLen elementów typu MPI_CHAR (znaków). Innymi słowy, tablicę znaków tworzącą nasz napis "Hello world..." wraz z kończącym znakiem zera (konwencja języka C). Generalnie, MPI definiuje pewną liczbę typów prostych (np. MPI_LONG, MPI_FLOAT, MPI_DOUBLE) oraz umożliwia aplikacjom tworzenie własnych typów złożonych (patrz literatura).
Jako że komunikaty mają ustalone formaty, nadawca musi mieć możliwość przekazania odbiorcy, jakiego formatu komunikat do niego wysyła, tj. jakiego typu są elementy tablicy stanowiącej komunikat. Odbiorca zaś musi mieć możliwość selektywnego odbierania komunikatów, tj. komunikatów o określonym formacie lub też komunikatów, na które obecnie oczekuje. W tym celu komunikaty opatrywane są tzw. znacznikami (piąty parametr funkcji MPI_Send). Znaczniki to po prostu liczby całkowite unikalnie identyfikujące rodzaj komunikatu w aplikacji równoległej. W naszym przykładzie, wysyłany komunikat "Hello world..." jest opatrzony znacznikiem MPI_MESSAGE_HELLO_WORLD_TAG.
Kolejnym zagadnieniem, na którym zatrzymamy się przy okazji funkcji MPI_Send jest semantyka tej funkcji. Dokładniej, jakie gwarancje daje MPI_Send w momencie zakończenia jeśli chodzi dostarczenie wysyłanego komunikatu oraz o obszar pamięci zawierającej wysyłany komunikat. Otóż standard MPI tego nie precyzuje. Generalnie, MPI_Send gwarantuje, że komunikat zostanie kiedyś dostarczony oraz że w momencie zakończenia MPI_Send, obszar pamięci zajmowany przez komunikat może być bezpiecznie użyty. Jednakże 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 mówi tylko, że funkcja MPI_Send może się zablokować do momentu, gdy kontynuowanie działania będzie bezpieczne z punktu widzenia wysyłanego komunikatu (tj. pamięć z komunikatem będzie można zmieniać). Aby umożliwiać bardziej precyzyjną kontrolę nad tym, co dzieje się z wysyłanym komunikatem, MPI udostępnia całą gamę wariantów funkcji MPI_Send z różną semantyką, ale o tym za tydzień.
Rozważmy teraz funkcję odbierającą. Jako że w naszym programie (dokładniej w procesie o randze 0) chcemy odebrać napis "Hello world..." kolejno od wszystkich procesów od 1 do N-1, proces 0 iteruje po tych procesach, w każdej iteracji wywołując funkcję:
MPI_Recv(
message,
sizeof(message) / sizeof(char),
MPI_CHAR,
srcProcessNo,
MPI_MESSAGE_HELLO_WORLD_TAG,
MPI_COMM_WORLD,
&status
);
W funkcji odbierającej (man MPI_Recv) musimy określić znacznik komunikatu, który chcemy odebrać, czyli w powyższym przykładzie zdefiniowany przez nas wcześniej MPI_MESSAGE_HELLO_WORLD_TAG. Musimy także zdecydować, od którego procesu chcemy odebrać komunikat (proces o numerze srcProcessNo interpretowanym w komunikatorze zawierającym wszystkie procesy — MPI_COMM_WORLD).
Po drugie, przekazujemy bufor na tablicę elementów stanowiącą komunikat (message), maksymalną liczbe elementów tablicy mieszczących się w buforze (sizeof(message) / sizeof(char)) oraz typ pojedynczego elementu (MPI_CHAR). Jeśli liczba elementów w tablicy odpowiadającej wysłanemu komunikatowi (przekazana do MPI_Send) była mniejsza lub równa długości tablicy bufora odbiorczego (przekazanej do MPI_Recv) komunikat zostanie odebrany poprawnie. Jeśli natomiast wysłany komunikat był dłuższy niż rozmiar bufora do odbioru, nastąpi błąd (i zgodnie z semantyką "all errors are fatal" nasza aplikacja zostanie przerwana).
Wywołanie funkcji MPI_Recv jest blokowane do momentu, gdy komunikat, na który oczekujemy nadejdzie.
Jako ostatni parametr, funkcja MPI_Recv przyjmuje wskaźnik na strukturę status. W momencie odebrania komunikatu (powrotu z funkcji MPI_Recv) struktura ta będzie zawierać dodatkowe dane o komunikacie. Przykładowo, jeśli potrzebowalibyśmy znać dokładną liczbę elementów tablicy reprezentującej otrzymany komunikat (w naszym przykładzie — liczbę znaków tworzących napis "Hello world...") możemy uzyskać tę informację wywołując funkcję:
MPI_Get_count(&status, MPI_CHAR, &messageLen);
Pole status ma także inne zastosowania. Jeśli do MPI_Recv zamiast srcProcessNo przekazalibyśmy stałą MPI_ANY_SOURCE, oznaczałoby to, że chcemy odebrać komunikat od dowolnego procesu. Po odebraniu takiego komunikatu, możemy dowiedzieć się od jakiego procesu go właściwie odebraliśmy używając pola MPI_SOURCE struktury status. Podobnie, jeśli do MPI_Recv zamiast MPI_MESSAGE_HELLO_WORLD_TAG przekazalibyśmy MPI_ANY_TAG, oznaczałoby to, że chcemy odebrać komunikat dowolnego typu. Po odebraniu komunikatu, pole MPI_TAG struktury status zawierało będzie znacznik komunikatu. Uwaga! W tym ostatnim przypadku, ważne jest, aby poprawnie zinterpretować typ elementów tablicy stanowiącej komunikat.
Przerób program "Hello world!" na program "Echo", w którym proces 0 kilkakrotnie wysyła do każdego procesu tablicę liczb. Proces niezerowy natomiast odbiera taką tablicę i odsyła z powrotem do procesu 0. Proces 0 powinien odebrać każdą odesłaną tablicę od każdego z pozostałych procesów.
Uruchamiając program na klastrze, zbadaj jaka jest przepustowość (ang. throughput) oraz dwukierunkowe opóźnienie (ang. round-trip time) komunikacji w zależności od typu wysyłanych liczb oraz rozmiaru tablicy.
Wskazówka: Do pomiarów użyj funkcji MPI_Wtime poznanej w poprzednim tygodniu.
Podstawowa komunikacja punkt do punktu pozwala budować dowolne wysokopoziomowe schematy komunikacji. Przykładowo, aby zaimplementować rozgłaszanie (czyli komunikację jeden do wszystich), rozgłaszający — proces i — może bezpośredio wysłać komunikat punkt do punktu do każdego odbierającego procesu j (j różne od i). Takie podejście jednak jest nieefektywne. Jeśli założymy, że koszty komunikacji pomiędzy dowolną parą procesów są stałe i takie same, najefektywniejsze rozgłaszanie działa w rundach wg następującego algorytmu:
W ten sposób rozgłaszanie będzie skończone w log2(N) rundach a nie w N - 1, jak w naiwnym algorytmie.
MPI udostępnia komunikację przez rozgłaszanie, co zademonstrujemy na przykładzie naszego prostego programu "Hello world!" (plik hello-world-bcast.c). W nowej wersji programu, to proces 0 rozgłasza komunikat "Hello world from process 0!" do pozostałych procesów. Natomiast procesy te wypisują otrzymany komunikat na standardowe wyjście.
Rozgłaszanie odbywa się za pomocą funkcji MPI_Bcast (man MPI_Bcast):
MPI_Bcast(
message,
messageLen,
MPI_CHAR,
srcProcessNo,
MPI_COMM_WORLD
);
Parametry przekazywane do tej funkcji są w większości takie same, jak w przypadku komunikacji punkt do punktu z następującymi wyjątkami. Po pierwsze, nie ma podziału na nadawców i odbiorców — wszyscy wywołują tą samą funkcję. To MPI decyduje, kto jest nadawcą a kto odbiorcą na podstawie czwartego parametru, który specyfikuje rangę nadawcy (srcProcessNo w naszym przypadku). Po drugie, nie ma znacznika komunikatu. To oznacza, że komunikaty rozgłoszeniowe są nierozróżnialne. Faktycznie, MPI_Bcast wymaga, aby wszystkie procesy w komunikatorze wywołały tę funkcję z tą samą rangą nadawcy. Semantyka MPI_Bcast dla nadawcy jest taka sama, jak MPI_Send, zaś dla odbiorcy taka sama, jak MPI_Recv.
Algorytm Floyda-Warshalla oblicza najkrótsze ścieżki pomiędzy wszystkimi N2 parami wierzchołków w grafie o N wierzchołkach. Zakładając, że macierz M zawiera nieujemne i skończone bezpośrednie odległości między wierzchołkami (M[i, j] to odległość od wierzchołka o numerze i do wierzchołka o numerze j), algorytm wygląda następująco:
for i := 1 to N do
for j := 1 to N do
for k := 1 to N do
if (M[j, k] > M[j, i] + M[i, k]) then
M[j, k] := M[j, i] + M[i, k];
Program sekwencyjny implementujący ten algorytm można znaleźć w pliku floyd-warshall-seq.c. Napisz równoległą wersję tego programu korzystającą z MPI. Zastanów się jak podzielić zadania pomiędzy procesy oraz jak każdy z procesów ma obliczać swoje zadania. Załóż, że żaden proces w żadnym momencie nie może przechowywać całego grafu. Policz speed-up'y dla różnych wielkości grafów i liczby procesów.
Wskazówka: Rozsyłanie (fragmentów) grafu i zbieranie (pod)wyników można zrobić za pomocą komunikacji punkt do punktu. Obliczenia natomiast powinny wykorzystywać komunikację przez rozgłaszanie.
Ostatnia modyfikacja: 16/03/2014