Zadanie zaliczeniowe z MPI (2012)

Mnożenie dużych liczb, w których liczba cyfr sięga kilu-kilkuset tysięcy, nie jest trywialne i wymaga intensywnych obliczeń. Obliczenia te można zrównoleglić. Napisz sekwencyjny program obliczający iloczyn dwóch dużych liczb. Napisz następnie równoległą wersję tego programu w MPI. Zastanów się jakiego algorytmu użyć, w szczególności, jak podzielić zadania pomiędzy procesy, jak każdy z procesów ma obliczać swoje zadania oraz jak procesy powinny się komunikować. Policz speed-up'y dla różnych wielkości danych wejściowych i liczby dostępnych procesorów. Zaprezentuj rozwiązanie i wyniki w formie raportu.

Finalne wyjaśnienia:
Jako że część z Państwa chciałaby używać GMP w rozwiązaniu równoległym, postanowiliśmy przychylić się to tych próśb. Ostatecznie reguły są następujące.

Każde rozwiązanie równoległe powinno zawierać co najmniej jeden algorytm, który w ogóle nie używa GMP. Program równoległy powinien jednak standardowo kompilować się do najlepszego zaimplementowanego algorytmu. Czyli w przypadku osób, które zdecydują się na GMP (patrz niżej) do najlepszego algorytmu z wykorzystaniem GMP.
Następnie można wybrać jedną z dwóch ścieżek:
1. NO-GMP: Żadne rozwiązanie równoległe nie będzie w ogóle używać GMP.
2. GMP: Co najmniej jedno rozwiązanie równoległe będzie zbudowane w oparciu o GMP.
Pierwsze zdanie w raporcie powinno wskazywać, którą ścieżkę Państwo wybraliście. W przypadku braku wyjaśnienia zakładamy GMP.
Rozwiązania zostaną podzielone na grupy NO-GMP i GMP. Efektywność rozwiązania jest oceniana jedynie w ramach jego grupy.
Punkty bonusowe za rozwiązania równoległe są proporcjonalnie podzielone na grupy. Przykładowo, jeśli grupa NO-GMP to 40 rozwiązań a grupa GMP to 10 rozwiązań, to 8 najlepszych rozwiązań z grupy NO-GMP i 2 z grupy GMP dostanie punkty bonusowe.
Punkty bonusowe za rozwiązanie sekwencyjne dostaje najlepsze rozwiązanie sekwencyjne, które nie używa GMP.

Kryteria oceniania

Celem zadania jest zachęcenie Państwa do zabawy i eksperymentów z algorytmami i MPI. Dlatego też przyjęliśmy poniższy sytem oceniania.

Zadanie jest warte 10 punktów. Aby zaliczyć zadanie, należy zdobyć co najmniej połowę dostępnych punktów.

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 poprawności i wydajności rozwiązania, sprawdzenia, czy rozwiązanie nie zawiera istotnych błędów jeśli chodzi o programowanie rozproszone (np. blokad), czy informacje zawarte w raporcie są zgodne z rzeczywistością oraz czy programy były pisane samodzielnie. Raport wart jest 50% punktów.

Zakładając, że raport jest w miarę sensowny, nadesłane rozwiązania będą w pierwszej kolejności weryfikowane pod względem poprawności. Niepoprawne rozwiązanie (żaden zaimplementowany algorytm — patrz niżej — nie mnoży liczb poprawnie) automatycznie oznacza zero punktów za zadanie. Jeśli co najmniej jeden zaimplementowany algorytm będzie poprawny, to zadanie zostanie ocenione pod względem efektywności: rozwiązania, które osiągną największy speed-up będą oceniane najwyżej. Dlatego też bardzo ważne jest zastosowanie się do poniższych wymagań dotyczących testowania oraz struktury rozwiązania. Efektywność warta jest 50% punktów.

Dodatkową zachętą do eksperymentów będą punkty bonusowe:

10 osób z najlepszymi speed-up'ami (dla największych danych i liczby procesorów) otrzyma +2 punkty.
1 osoba z najlepszym programem sekwencyjnym (dla największych danych) otrzyma +2 punkty (względem tego programu będziemy wszystkim liczyć speed-up'y).
Za każdy dodatkowy zaimplementowany, przetestowany i opisany w raporcie algorytm równoległy, który jest nietrywialny i istotnie różny od głównego, każdy może otrzymać do +1 punkt (wedle uznania prowadzącego laboratorium). Sumarycznie za dodatkowe algorytmy można otrzymać do +3 punkty.

Punkty bonusowe nie zmieniają jednak maksymalnej liczby punktów, które można otrzymać za zadanie.

Zadania oddane po terminie, tj. po 07 maja 2012 23:59, nie będą oceniane.

Szczegółowe wymagania

Struktura rozwiązania

Rozwiązanie powinno składać się z co najmniej 6 plików (szablon do pobrania tutaj):

report.pdf: Państwa raport.
multiply-seq.c: Program implementujący sekwencyjny algorytm mnożenia.
multiply-par.c: Program implementujący równoległy algorytm mnożenia.
rlib.h: Plik nagłówkowy z biblioteką liczb losowych.
rlib.c: Plik źródłowy z biblioteką liczb losowych.
Makefile: Plik budujący Państwa rozwiązanie. Program sekwencyjny powinien kompilować się do multiply-seq.exe. Program równoległy natomiast do multiply-par.exe.

Jeśli w ramach bonus'a napiszecie Państwo więcej niż jeden algorytm równoległy bądź sekwencyjny, standardowo plik Makefile powinien budować najlepsze z algorytmów. Wybór innego algorytmu powinien być możliwy przez zmianę jednej flagi w pliku Makefile. Cała procedura powinna być opisana w raporcie.

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.

Programy

Państwa rozwiązanie, multiply-seq.exe oraz multiply-par.exe, musi dać się uruchomić w dwóch trybach:

Z jednym argumentem: <plik_wejsciowy>: W tym trybie program oczekuje, że tekstowy <plik_wejsciowy> będzie istniał i będzie można go odczytać. Jedynymi danymi w pliku wejściowym są dwie duże liczby, każda zakończona znakiem końca linii ('\n'). Liczby zapisane są w formacie szesnastkowym, przy czym litery 'A'-'F' są zawsze wielkie.
Z trzema argumentami (64-bitowymi liczbami bez znaku): <dl_liczby_1> <dl_liczby_2> <rand_seed>: W tym trybie program generuje liczby na podstawie argumentów. Generowanie ma działać następująco. Dostarczony generator pseudolosowy inicjalizowany jest wartością parametru <rand_seed>. Następnie <dl_liczby_1> razy generowane są losowe wartości, które podzielone modulo przez 16 stanowią kolejne cyfry pierwszej liczby wejściowej: od najstarszej do najmłodszej. Po wygenerowaniu <dl_liczby_1> cyfr dla pierwszej liczby, generowanych jest <dl_liczby_2> cyfr dla drugiej liczby, przy czym generator liczb losowych nie jest reinicjalizowany. W programie równoległym generowanie liczb można zrównoleglać, ale nie jest to konieczne (nie ma dodatkowych punktów). Można też generować liczby tylko na jednej maszynie i rozsyłać je do pozostałych. Niezależnie od metody ważne jest tylko, aby liczby generowane dla algorytmu równoległego były takie same, jak dla sekwencyjnego.

Dodatkowo program powinien przyjmować opcjonalny parametr -v (jeśli występuje, to tylko przed argumentami). Rezultatem tego parametru jest wypisanie wynikowej liczby na standardowe wyjście (jedna linia zakończona '\n', format szesnastkowy, bez wiodących zer) przez proces o numerze zero. W normalnym przypadku na standardowe wyjście nie powinno być wypisywane nic.

W przypadku błędnych parametrów, zamiast wynikowej liczby na standardowe wyjście powinna być wypisana dokładnie jedna linia: ERROR: <opis bledu>. Znowu robi to tylko proces zero. Program zaś powinien w wyniku zwrócić wartość różną od zera.

Używając funkcji MPI_Wtime w każdym wariancie programu muszą być mierzone dwa czasy: sumaryczny, TS, i obliczeń równoległych, TP. Każdy proces powinien mierzyć oba czasy indywidualnie. Mierzenie TS rozpoczyna się tuż po starcie programu (pierwsza linia funkcji main) i kończy się, gdy wynikowa liczba zostaje dostarczona do procesu zero (i ewentualnie wypisana na standardowe wyjście). Mierzenie TP rozpoczyna się po wygenerowaniu lub rozdrystrybuowaniu liczb (tuż przed rozpoczęciem mnożenia) i kończy tuż po zakończeniu mnożenia. Jeśli algorytm ma jeszcze osobną fazę zbierania podwyników, to nie jest ona uwzględniana w TP. Przed mierzeniem TP należy należy zsynchronizować procesy za pomocą bariery. Następnie każdy proces wysyła swoje TS i TP do procesu zero, który oblicza TSmax i TPmax. Na koniec, proces zero wypisuje TSmax i TPmax (oddzielone pojedynczą spacją i zakończone znakiem '\n') na standardowe wyjście diagnostyczne (stderr). Oprócz tych dwóch czasów wypisanych przez proces zero, żaden proces nie wypisuje nic więcej na standardowe wyjście diagnostyczne.

Przykładowo, wywołanie programu z parametrami:

  mpirun -np 8 ./multiply-par.exe -v dane.in

gdzie plik dane.in ma następującą treść:

A12F0287478346B12983192837129FE3289472CA298347BBB0293423C
230AAC94832942CA32432E84AE239847E00ABCF928734FC5

spowoduje wypisanie na standardowe wyjście liczby:

161025D7AF8520EC95A36D56E1EDC7FED7BC2EDA8DB530476E8A0D721A5D4A186E73FACE82D5269EC1935BA22DC3293908DB67C2C

zaś na standardowe wyjście diagnostyczne dwóch czasów, np.:

0.0 0.0

Natomiast wywołanie programu z parametrami:

  mpirun -np 8 ./multiply-par.exe -v 25 51 356123729121233

spowoduje wypisanie na standardowe wyjście liczby:

B33B1B0E377219D1DA0B24B103336B845D3D1D0517CA6936EA72825BC8A135B6B541ECE400

zaś na standardowe wyjście diagnostyczne dwóch czasów, np.:

0.0 0.0

W tym przypadku losowo wygenerowanymi liczbami są: 00C487FB6041CE048264B5300 oraz E976FADC10B9ECCCED261314FD106A7B017445D1439AB38670C.

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

Celem zadania jest maksymalizacja speed-up'ów osiąganych przez Państwa programy równoległe. Jak wiadomo, speed-up'y powinny być liczone względem najszybszej istniejącej implementacji sekwencyjnej. Jako że macie Państwo wolność implementacji algorytmu sekwencyjnego, powinniście zaimplementować go jak najwydajniej się da. W ten sposób mierzone przez Państwa speed-up'y będą bardziej miarodajne i łatwiej będzie Państwu oszacować, jak dobry macie algorytm równoległy. My będziemy mierzyć speed-up'y względem najlepszego programu sekwencyjnego (bądź naszej implementacji, jeśli Państwa implementacje sekwencyjne okażą się kiepskie).

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 co najmniej 8 maszyn. Ponieważ w labach MPI działa nieoptymalnie, gdy więcej niż jeden proces jest uruchomiony na jednej maszynie, testy należy przeprowadzać w konfiguracjach 1 maszyna = 1 proces. Długości liczb, dla których rozwiązanie będzie testowane powinny być sensownie wybrane tak, aby najwolniejszy test (sekwencyjny) kończył się w nie więcej niż 10-15 minut. Oczywiście można testować też większe liczby, ale nie należy przesadzać, żeby nie zabierać kolegom czasu maszyn.

W testach wydajnościowych należy użyć losowego generowania liczb wejściowych a nie wczytywania liczb z plików.

Podczas raportowania czasów wykonania proszę podać minimalny, średni i maksymalny czas sumaryczny TSmax, czas mnożenia TPmax oraz 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.

Raport

Raport powinien zawierać:

Opis rozwiązania (zarówno algorytm(y) jak i optymalizacje).
Testy i ich wyniki.

Opis rozwiązania powinien uwzględniać generalny pomysł, założenia, algorytmy i struktury danych (złożoność czasową i pamięciową), podział zadań na procesory, komunikację, optymalizacje, itp. Powinien być on opatrzony rysunkami tam gdzie one pomagają zrozumieć Państwa pomysły. Opisane mają być Państwa algorytmy równoległe, jak i algorytm sekwencyjny, względem którego liczyliście Państwo speed-up'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 długości liczb, 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).

Prawa autorskie i udostępnianie

Ogólnie, jeśli wykorzystacie Państwo istniejące algorytmy, to informacja ta powinna znaleźć się w raporcie i kodzie programu.

W szczególności, implementacja algorytmu sekwencyjnego może pochodzić z Internet'u, ale w raporcie i kodzie należy to zaznaczyć, kto jest autorem implementacji i upewnić się, że licencja pozwala na jej wykorzystanie w programie zaliczeniowym.

Programy równoległe natomiast mają być w całości napisane przez Państwa. Można wykorzystywać istniejące algorytmy, ale nie cudzy kod. Nie można także używać pomysłów i kodu innych studentów.

Poza tym można wymieniać się na przykład wynikami wydajnościowymi, czy plikami testowymi (z liczbami).

FAQ

Wszelkie pytania proszę kierować do Konrada Iwanickiego.

Czy można założyć, że liczby wejściowe i wyjściowe mieszczą się pamięci pojedynczego komputera?: Tak.
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 komputerów. W szczególności, w ramach sprawdzania prowadzący mogą używać większej liczby komputerów 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. Proszę tylko zauważyć, że programy w C++ są często wolniejsze niż programy w C (zwłasza te pisane przez osoby, które słabo znają C++). Dlatego pisanie w C++ odbywa się na własną odpowiedzialność i nie może być później użyte jako argument za tym, że program działa słabiej niż kolegi, mimo że oba mają podobne algorytmy.
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 procesów jest nie więcej niż długość liczby?: Nie. Rozwiązanie ma działać poprawnie nawet jeśli procesów P jest więcej niż cyfr w liczbach wejściowych N. W tym przypadku, można użyć tylko N procesów. Wydajność powinna być optymalizowana dla przypadku, w którym P << N (P jest wielokrotnie mniejsze niż N).
Co oznacza: “Jeśli algorytm ma jeszcze osobną fazę zbierania podwyników, to nie jest ona uwzględniana w TP”?: Oznacza to, że jeśli ta faza zawiera cokolwiek więcej niż wypisywanie wyników, np. obliczenia, to musi być uwzględniana w TP.
Czy można używać GMP?: W rozwiązaniu sekwencyjnym tak. W rozwiązaniu równoległym nie. Ideą rozwiązania równoległego jest, abyście Państwo trochę pomyśleli, jak zrównoleglić algorytmy a następnie sprawdzili, czy to coś daje. W ramach testów oczywiście można porównać swoje rozwiązania z jakimiś dodatkowymi rozwiązaniami opartymi na GMP.

Ostatnia modyfikacja: 14/04/2012