Zadanie zaliczeniowe z MPI (2011)

Algorytm Floyda-Warshalla oblicza najkrótsze ścieżki pomiędzy wszystkimi N² parami wierzchołków w grafie o N wierzchołkach. Program na maszyny jednoprocesorowe implementujący ten algorytm można znaleźć w pliku floyd-warshall-seq.c (do pobrania tutaj). Napisz równoległą wersję tego programu w MPI. Zastanów się jak podzielić zadania pomiędzy procesy oraz jak każdy z procesów ma obliczać swoje zadania. Podobnie zastanów się, jak zbierać wyniki do wypisania na ekran. Policz speed-up'y dla różnych wielkości grafów i liczby dostępnych procesorów. Zaprezentuj rozwiązanie i wyniki w formie raportu.

Uwaga dla leniwych: Zadania nie da się zrobić w ostatniej chwili.

Kryteria oceniania

Celem zadania jest zachęcenie Państwa do zabawy i eksperymentów z MPI. Dlatego też najważniejszą częścią rozwiązania będzie raport (koniecznie w formacie PDF, patrz niżej). Brak raportu (lub kiepski, na przykład, pisany w ostatniej chwili) oznacza zero punktów za zadanie. Program będzie potrzebny jedynie do zweryfikowania wydajności rozwiązania, sprawdzenia, czy rozwiązanie nie zawiera istotnych błędów (np. blokad) oraz czy informacje zawarte w raporcie są zgodne z rzeczywistością.

Zakładając, że raport jest w miarę sensowny, nadesłane rozwiązania będą oceniane pod względem efektywności: rozwiązania, które osiągną speed-up najbardziej zbliżony do liniowego będą oceniane najwyżej. Dlatego też bardzo ważne jest zastosowanie się do poniższych wymagań dotyczących testowania oraz struktury programu.

Kara za spóźnienie rośnie wykładniczo (przy czym "dosłanie poprawki lub jednej brakującej rzeczy" jest traktowane jako spóźnienie):

do 1 dnia = -1 punkt
do 2 dni = -2 punkty
do 3 dni = -4 punkty
do 4 dni = -8 punktów
do 5 dni = -16 punktów
powyżej 5 dni nie ma co wysyłać

Szczegółowe wymagania

Struktura rozwiązania

Rozwiązanie powinno składać się z 4 plików:

report.pdf: Państwa raport.
floyd-warshall-seq.c: Oryginalny sekwencyjny program implementujący sekwencyjny algorytm z zadania.
floyd-warshall-par.c: Państwa wersja równoległego algorytmu z zadania.
Makefile: Zmodyfikowany plik makefile uwzględniający Państwa rozwiązanie. Program sekwencyjny powinien kompilować się do floyd-warshall-seq.exe. Państwa program równoległy powinien kompilować się do floyd-warshall-par.exe.

Uwaga: Nie wolno używać bibliotek czy plików nagłówkowych, które nie są zainstalowane na maszynie students i komputerach w Państwa laboratorium PWIR. Programy muszą się kompilować na maszynie students i na komputerach w Państwa laboratorium.

Program

Państwa rozwiązanie, floyd-warshall-par.exe, musi przyjmować dokładnie te same argumenty co rozwiązanie sekwencyjne, floyd-warshall-seq.exe, oraz musi identycznie wspierać flagi preprocesora USE_RANDOM_GRAPH i USE_RANDOM_SEED. Podobnie, wyniki działania i wypisywane komunikaty muszą być identyczne, jak w rozwiązaniu sekwencyjnym — niezależnie od tego na ilu procesorach program równoległy zostanie uruchomiony.

Uwaga: Rozwiązania będą automatycznie testowane. Wobec tego programy, które będą nieprawidłowe lub będą nieprawidłowo wypisywać wyniki będą automatycznie odrzucane bez dalszego sprawdzania.

Implementację algorytmu, jak i struktury danych do przechowywania grafu można dowolnie modyfikować (oczywiście pod warunkiem, że Państwa rozwiązanie pozostanie implementacją algorytmu Floyda-Warshalla). Mierzenie czasu wykonania do obliczania speed-up'ów powinno jednak pozostać nie zmienione. Innymi słowy, pomiar czasu w algorytmie równoległym nie musi uwzględniać czasu rozsyłania inicjalnego grafu do wszystkich procesorów, ani ewentualnego zbierania wyników. Jeśli Państwa implementacja algorytmu Floyd-Warshall'a osiągna inne wyniki na jednym procesorze niż dostarczona implementacja sekwencyjna, to w raporcie speed-up'y powinny być liczone względem dwóch implementacji: wzorcowej sekwencyjnej i Państwa równoległej na jednym procesorze.

Testowanie

Niestety, jeszcze nie dorobiliśmy się klastra na wydziale. Dlatego też testowanie powinno odbywać się na maszynach w sali, w której macie Państwo laboratorium z PWIR (w raporcie należy wymienić maszyny, na których rozwiązanie było testowane). Eksperymenty powinny uwzględniać od 1 do przynajmniej 4 (a najlepiej 8) maszyn. Ponieważ maszyny w niektórych labach są wielordzeniowe, oprócz testowania wydajności jednej instancji programu per maszyna, należy przetestować również wiele instancji (do liczby rdzeni). Minimalne wymaganie co do maksymalnej konfiguracji na komputerach wielordzeniowych to 4 maszyny po dwa procesy na maszynę. Wielkości grafu, na których rozwiązanie będzie testowane powinny być sensownie wybrane z przedziału od 1 do 5000 węzłów. Oczywiście można testować też większe grafy, ale nie należy przesadzać, żeby nie zabierać kolegom czasu maszyn.

Podczas raportowania czasów wykonania proszę podać minimalny, średni i maksymalny speed-up, który udało się osiągnąć. Można odrzucić wyniki wykonań, w których ktoś wykonywał coś innego na jednej z maszyn podczas testowania naszego programu (niestety, nie mamy dedykowanego klastra, więc najlepiej testy robić w nocy).

Raport

Raport powinien zawierać:

Opis rozwiązania.
Testy i ich wyniki.

Opis rozwiązania powinien uwzględniać generalny pomysł, założenia, struktury danych, podział zadań na procesory, komunikację, optymalizacje, itp. Powinien być on opatrzony rysunkami tam gdzie one pomagają zrozumieć Państwa pomysły.

Jeśli chodzi o testy, to powinny być ich dwie grupy: poprawnościowe i wydajnościowe. Jeśli chodzi o pierwszą grupę, to wystarczy krótka notka. Druga grupa natomiast musi być dokładnie opisana.

Rozdział o testach powinien zawierać:

opis środowiska testowego,
czasy wykonania w zależności od liczby węzłów, N, i liczby procesorów, P,
odpowiadające im speed-up'y i efektywność (tj. jak bardzo nasz speed-up, f(P), odbiega od funkcji id(P) = P: f(P) / id(P)),
ewentualnie tzw. pefromance breakdown, czyli procent czasu poświęconego przez program równoległy na odpowiednio obliczenia i komunikację/synchronizację.

Wyniki powinny być prezentowane jako tabele oraz wykresy, stąd wymaganie o formacie raportu (PDF).

FAQ

Wszelkie pytania proszę kierować do Konrada Iwanickiego.

Czy można założyć, że graf mieści się w pamięci pojedynczego komputera?: Można założyć, że graf mieści się w sumarycznej pamięci wszystkich komputerów, ale niekoniecznie pojedynczego komputera (procesu). Dokładniej, można założyć, że w pamięci pojedynczego komputera mieści się O(N²/P) danych, gdzie N to liczba wierzchołków w grafie, zaś P to liczba procesów (o ile P <= N). Rozwiązania, które na jakimkolwiek etapie będą zakładały, że graf mieści się w całości w pamięci pojedynczego komputera będą oceniane odpowiednio niżej. Jeśli zaś P > N, każdy proces może zużyć O(N) pamięci.
Czy w optymalizacjach należy brać pod uwagę ograniczenie na maksymalną liczbę komputerów z jakim program będzie testowany?: Nie. Program powinien sensownie działać na dowolnie dużej liczbie węzłów. W szczególności, w ramach sprawdzania prowadzący mogą używać większej liczby węzłow i innych środowisk (faktyczne klastry).
Czy można pisać w C++?: Tak, pod warunkiem, że nazewnictwo plików będzie zachowane oraz programy będą się kompilować na maszynach testowych.
Czy można wykonywać testy na maszynach innych niż wydziałowe?: Tak, pod warunkiem, że program będzie przetestowany też na maszynach wydziałowych. Testy na maszynach wydziałowych pozwalają porównać rozwiązania różnych studentów więc są konieczne. Testy w innych środowiskach są opcjonalne.
Czy można założyć, że wagi w grafie są nieujemne?: Tak.
Czy można założyć, że dla rand() i srand() wszystkie maszyny mają ten sam algorytm losujący?: Tak.
Czy można założyć, że procesów jest nie więcej niż wierzchołków grafu?: Rozwiązanie ma działać poprawnie nawet jeśli procesów jest więcej niż wierzchołków grafu. W tym przypadku, program może po prostu wypisać komunikat o konieczności uruchomienia z mniejszą liczbą procesów. Performance powinien być optymalizowany dla przypadku, w którym P << N (P jest wielokrotnie mniejsze niz N).
Czy gdy P > N możemy nie używać P-N procesów do obliczeń?: Tak. W takim przypadku można użyć tylko N procesów.
Zrobiłem XXX i to działa wolno chociaż moim zdaniem nie powinno. Może coś jest nie tak z MPI-em w labach. Czy zadanie było rozwiązanie i czy było testowane w labach?: Tak było i działa całkiem nieźle.
Co jest rozumiane przez liniowy speed-up?: Załóżmy, że mamy odpowiednio duży problem, tj. odpowiednio duże N (np. 10000). Załóżmy, że czas wykonania naszego programu równoległego dla zadanego N na P procesorach wynosi T_P, a czas wykonania programu sekwencyjnego to T_S. Speed-up to funkcja s(P) = T_S / T_P. Jako liniowy rozumiemy speed-up taki, że s(P) ≈ P gdy sensownie zwiększamy P (powiedzmy do 32 procesorów).

Ostatnia modyfikacja: 07/06/2011