Z powodu kłopotów z klastrem notos wystarczy przetestować 15 konfiguracji z e-mail'a.
Tematem zadania zaliczeniowego z MPI w tym roku jest efektywny równoległy program rozwiązujący problem tzw. maksymalnej podtablicy (ang. the maximum subarray problem) z tym że w dwóch wymiarach. Problem taki pojawia się w grafice komputerowej czy w eksploracji danych. Naiwny algorytm sekwencyjny rozwiązujący ten problem można znaleźć w programie msp-seq-naive.c (do pobrania tutaj). Zaprojektuj efektywny równoległy algorytm i zaimplementuj go w postaci programu w MPI. Przeprowadź eksperymenty ze swoim rozwiązaniem na klastrze notos ICM. W szczególności, policz speed-up'y dla różnych rozmiarów tablic (M x N) i liczby procesów (P). Zaprezentuj rozwiązanie i wyniki w formie raportu.
Dana jest dwuwymiarowa tablica liczb całkowitych o M wierszach i N kolumnach (A : array [1..M, 1..N] of integer). Zadaniem jest znalezienie takich i, j, k oraz l, gdzie 1 ≤ i ≤ k ≤ M oraz 1 ≤ j ≤ l ≤ N, że suma elementów w podtablicy A[i..k, j..l], to jest, S[i..k,j..l], jest maksymalna. Innymi słowy, że dla dowolnych i', j', k' oraz l' takich, że 1 ≤ i' ≤ k' ≤ M oraz 1 ≤ j' ≤ l' ≤ N, mamy S[i..k,j..l] ≥ S[i'..k',j'..l']. Przykładowo, dla poniższej tablicy A[1..4, 1..8]:
| -1 | 2 | -3 | 5 | -4 | -8 | 3 | -3 |
| 2 | -4 | -6 | -8 | 2 | -5 | 4 | 1 |
| 3 | -2 | 9 | -9 | 3 | 6 | -5 | 2 |
| 1 | -3 | 5 | -7 | 8 | -2 | 2 | -6 |
szukana podtablica to zaznaczone kolorem szarym A[3..4, 5..6], ponieważ S[3..4, 5..6] = 15 jest maksymalne.
W przypadku, gdy tablica ma wiele podtablic maksymalnych, wystarczy znaleźć dowolną z nich.
Implementacja bardzo sekwencyjnego algorytmu znajduje się w załączonym pliku msp-seq-naive.c. Zaprojektuj efektywny algorytm równoległy i zaimplementuj go w postaci programu używającego MPI a także przetestuj jego poprawność i wydajność. Dla ułatwienia, poniżej znajdują się trzy pozycje literatury, od których warto zacząć prace nad rozwiązaniem:
Rozwiązanie powinno składać się z co najmniej następujących plików:
Uwaga: Nie wolno używać bibliotek czy plików nagłówkowych, które nie są zainstalowane na klastrze notos ICM.
Państwa rozwiązanie, msp-par.exe, musi przyjmować dokładnie te same argumenty co sekwencyjne rozwiązanie naiwne, msp-seq-naive.exe. Podobnie, wyniki działania i komunikaty muszą być wypisywane identycznie, jak w rozwiązaniu sekwencyjnym — niezależnie od tego w ilu procesach program równoległy zostanie uruchomiony. Jedyne co należy zmienić zarówno w programie sekwencyjnym, jak i równoległym to wstawić w wypisywanym komunikacie Państa imię, nazwisko i numer indeksu (zamiast Jana Kowalskiego).
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ą znacznie karane (patrz niżej).
Mierzenie czasu wykonania powinno pozostać niezmienione. Innymi słowy, pomiar czasu w algorytmie równoległym nie powinien uwzględniać czasu generowania/rozsyłania do wszystkich procesów tablicy wejściowej.
Dla ułatwienia i odciążenia klastra, jako bazę sekwencyjną, względem której liczone są speed-up'y należy użyć średnich wyników z naszych (niezbyt zoptymalizowanych) programów sekwencyjnych (dostępnych tutaj). Podczas raportowania czasów wykonania proszę podać średnią, minimum i maksimum z co najmniej trzech wykonań każdej konfiguracji. Speed-up'y liczymy jedynie wg średniej. Jeśli Państwa implementacja równoległa osiąga lepsze wyniki w konfiguracji jednoprocesowej niż nasze wyniki, to w raporcie speed-up'y powinny być liczone względem dwóch baz wyników: naszych i otrzymanych przez Państwa równoległą implementację w konfiguracji jednoprocesowej.
Testowanie powinno odbywać się na klastrze notos. Eksperymenty powinny uwzględniać od 1 do 16 węzłów oraz od 1 do 4 procesów na węzeł. Im bardziej przekonujące testy skalowalności — więcej maszyn, większe dane, większa liczba konfiguracji, itd. — tym lepsza ocena.
Raport powinien zawierać:
Opis rozwiązania powinien uwzględniać zarys pomysłu, jak również dokładny opis algorytmu, to jest założenia, struktury danych, podział zadań na procesy, 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. Rozdział o testach powinien zawierać:
Wyniki powinny być prezentowane jako tabele oraz wykresy, stąd wymaganie o formacie raportu (PDF).
Celem zadania jest zachęcenie Państwa do zabawy i eksperymentów z MPI. Dlatego też istotną częścią rozwiązania będzie raport (koniecznie w formacie PDF). Dokładniej, punkty rozkładają się następująco:
Jeśli program będzie działał niepoprawnie w naszych testach, będziemy odejmować do 7 pkt. (a w przypadkach skrajnych — do 10 pkt.).
Z zrównoleglenie algorytmu naiwnego można otrzymać maksymalnie 2 punkty (plus do 2 punktów za raport).
Za każde rozpoczęte 12 godzin spóźnienia odejmujemy 1 punkt.
Wszelkie pytania proszę kierować do Konrada Iwanickiego.
Ostatnia modyfikacja: 10/05/2014