Na poprzednim laboratorium poznaliśmy podstawy MPI, w szczególności elementarne funkcje używane do komunikacji, i nauczyliśmy się uruchamiać programy korzystające z MPI. Na dzisiejszym laboratorium zajmniemy się przykładem ilustrującym, jak można podzielić obliczenia pomiędzy procesy i jak zorganizować komunikację pomiędzy tymi procesami, aby całość umożliwiała efektywne obliczenia nawet w przypadku, gdy dane wejściowe przekraczają pamięć pojedynczej maszyny.
Algorytm Floyda-Warshalla oblicza najkrótsze ścieżki pomiędzy wszystkimi N2 parami wierzchołków w grafie ważonym o N wierzchołkach. Zakładając, że macierz M zawiera nieujemne i skończone bezpośrednie odległości między wierzchołkami (wagi), gdzie 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 k := 0 to N-1 do
for i := 0 to N-1 do
for j := 0 to N-1 do
if (M[i, j] > M[i, k] + M[k, j]) then
M[i, j] := M[i, k] + M[k, j];
Na dzisiejszym laboratorium zaimplementujemy ten algorytm w MPI jako case study dla rozpraszania obliczeń i organizowania komunikacji.
Jednym z podstawowych problemów w obliczeniach rozproszonych jest podział pracy pomiędzy procesy. Problem ten staje się jeszcze bardziej interesujący, gdy dane wejściowe przekraczają pamięć dostępną dla pojedynczego procesu.
W przypadku algorytmu Floyda-Warshalla danymi wejściowymi jest macierz sąsiedztwa grafu zawierająca wagi poszczególnych krawędzi. Chcielibyśmy podzielić ją tak, aby umożliwić efektywne wykonanie rozproszonej wersji algorytmu. Jednocześnie chcemy zapewnić, że w żadnym momencie nie będzie konieczności, aby pojedynczy proces przechowywał całą macierz lub znaczną jej część w pamięci.
W tym celu macierz podzielimy wierszami na rozłączne bloki obejmujące sąsiednie wiersze tak, aby każdy proces przechowywał jeden blok. Co ważne, w celu zrównoważenia obciążenia pomiędzy procesami, chcemy, aby różnica w rozmiarze bloków przechowywanych przez dwa dowolne procesy nie przekraczała jednego wiersza.
Zaimplementuj funkcje dokonujące podziału macierzy i wypisujące rozproszoną macierz na standardowe wyjście. Dokładniej, w pliku graph-utils-par.c zaimplementuj funkcje oznaczone FIXME. Jednoprocesowa wersja tych funkcji (do podejrzenia jako wzór) znajduje się w pliku graph-utils-seq.c, zaś ich deklaracje w pliku nagłówkowym graph-utils.h. Pliki generator-seq.c i generator-par.c, kompilujące się odpowiednio do generator-seq.exe i generator-par.exe, zawierają natomiast testy, które pozwolą sprawdzić poprawność Twojego rozwiązania — uruchomienie generator-par.exe na dowolnej liczbie procesów powinno dać taki sam wynik, jak uruchomienie pojedynczego procesu generator-seq.exe, niezależnie od liczby wierzchołków w grafie (rozmiaru macierzy).
Zgodnie z wcześniejszymi założeniami, nie jest dozwolone, aby w jakimkolwiek momencie pojedynczy proces przechowywał całą macierz lub taką jej część, która istotnie przekracza rozmiar bloku tego procesu (oczywiście w przypadku, gdy liczba procesów jest większa niż jeden). Zauważ także, że, zgodnie z wersją sekwencyjną, generowanie kolejnych wierszy macierzy może wymagać pewnego stanu. Dlatego też powinno odbywać się w jednym procesie. Analogicznie, wypisywanie macierzy powinno być wykonywane przez pojedynczy proces, aby uniknąć problemów, które poruszaliśmy na poprzednim laboratorium.
Przed przejściem do kolejnych zadań upewnij się, że Twoje rozwiązanie faktycznie działa w różnych konfiguracjach liczby wierszy i procesów.
Zgodnie z dotychczasowymi pomysłami, każdy proces posiada unikalny zbiór elementów macierzy sąsiedztwa. Jednocześnie, do obliczeń będzie potrzebował elementów posiadanych przez inne procesy. Procesy mogą więc chcieć rozgłosić w odpowiednim momencie część posiadanych przez siebie elementów macierzy do innych procesów.
Podstawowa komunikacja punkt do punktu pozwala budować dowolne wysokopoziomowe schematy komunikacji. Przykładowo, aby zaimplementować rozgłaszanie (zwane także 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-par.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(
<messagePtr>,
<messageLen>,
MPI_<TYPE>,
<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 i, co ważne, z taką samą długością (<messageLen>) i typem (MPI_<TYPE>) komunikatu. Semantyka MPI_Bcast dla nadawcy jest taka sama, jak MPI_Send, zaś dla odbiorcy taka sama, jak MPI_Recv.
Napisz równoległą implementację algorytmu Floyda-Warshalla korzystającą z MPI. Dokładniej, w pliku floyd-warshall-par.c napisz funkcję oznaczoną jako FIXME. Program sekwencyjny implementujący ten algorytm można znaleźć w pliku floyd-warshall-seq.c. Twoja implementacja, kompilująca się do floyd-warshall-par.exe, powinna, niezależnie od wielkości grafu i liczby procesów, dawać dokładnie takie same wyniki wyniki, jak wersja sekwencyjna, kompilująca się do floyd-warshall-seq.exe.
Policz speed-up'y uzyskiwane przez Twoją implementację dla różnych wielkości grafów, liczby procesów i mapowania tych procesów na fizyczne maszyny. Dla przypomnienia, speed-up algorytmu dla P procesów wynosi SP = T1 / TP, gdzie T1 to czas działania najlepszego algorytmu sekwencyjnego rozwiązującego ten sam problem (na nasze potrzeby — floyd-warshall-seq.exe) a TP to czas działania rozważanego algorytmu równoległego dla P procesów (czyli floyd-warshall-par.exe).
Zastanów się, jak poprawić osiągany speed-up (np. modyfikując instrukcje, sposób przechowywania macierzy, etc.).
Ostatnia modyfikacja: 04/05/2016