Zadání projektů do předmětu Paralelní a Distribuované algoritmy (2013)

Podmínky zápočtu jsou: Pro získání zápočtu a úspěšné ukončení předmětu je nutné za každý z hodnocených úkolů získat minimálně jeden bod (tedy oba projekty odevzdat v řádném termínu), za celý semestr (projekty a půlsemestrální zkoušku) pak celkem alespoň polovinu bodů !!!

Projekty z loňska: Projekty z loňského roku se neuznávají a je třeba je vypracovat znovu.

1. Projekt- slouží pro seznámení s knihovnou pro paralelní výpočty- Open MPI. Není hodnocen, nic se neodevzdává.

V rámci prvního projektu je vhodné, abyste si zkusili nainstalovat knihovnu Open MPI a rozběhali klasický Hello world v paralelním prostředí. Pokud nechcete knihovnu instalovat, zkuste si Hello world přeložit a prozkoumat alespoň na merlinovi, kde budou projekty testovány. Merlin tedy slouží jako referenční prostředí a funkčnost projektů na něm bude rozhodující.
Povolené jazyky pro všechny projekty jsou C/C++. Open MPI je pouze knihovna a proto programování s její pomocí se téměř neliší od programovaní s pomocí jakékoli jiné knihovny. Obsahem dotazů k projektům by proto nemělo být zpracování parametrů příkazové řádky a podobné.

Ubuntu (9.04, 9.10, 10.04, 10.10)

Instalace
Protože Open MPI je vyvíjeno pro posixové systémy, je velmi problematické rozchodit ho na platformě Windows. Tento návod proto bude pokrývat pouze instalaci na linux, konkrétně na distribuci Ubuntu. Instalaci lze provést přímo z balíčků. Jména balíčků odpovídají verzi karmic koala (9.10) a dále verzím lucid lynx (10.04) a maverick meerkat (10.10). V jaunty jackalope (9.04) se libopenmpi1.3 jmenuje libopenmpi1. Verzi svého ubuntu zjistíte (v anglické verzi) přes:

System->About Ubuntu

Instalaci následně provedete otevřením terminálu:

Applications->Accessories->Terminal

Do kterého pak vepíšete (zkopírujete):

sudo apt-get install libopenmpi-dev libopenmpi-dbg libopenmpi1.3 openmpi-bin openmpi-common openmpi-doc

Kvůli sudo se vás ještě instalátor zeptá na heslo pro root a po jeho úspěšném zadání by se mělo vše bez problémů nainstalovat. Obsahem výše nainstalovaných balíčků pak je:

libopenmpi-dev: hlavičkové soubory
libopenmpi1.3: sdílené knihovny
libopenmpi-dbg: debugovací symboly
openmpi-common: platformně nezávislé soubory
openmpi-doc: man stránky
openmpi-bin: binární soubory

Je samozřejmě i nutný překladač jazyka C/C++. Překladač jazyka C by měl být obsažen standardně v každé nové verzi Ubuntu. Pokud budete postrádat překladač C++ (například pro zkoušku ukázkového kódu "odd-even transposition sort"), můžete ho nainstalovat pomocí:

sudo apt-get install g++

V ostatních distribucích je třeba nalézt odpovídající balíčky. Skalní příznivci kompilování vlastních verzí mohou zkusit http://www.open-mpi.org/software/ompi/v1.6/, kde najdete nejnovější (stable) verzi Open MPI. Novější verze Ubuntu jsme netestovali, ale pokud zjistíte, že byly některé balíčky opět přejmenovány, napište prosím na izakjakub@fit.vutbr.cz.

Ukázkový překlad

```
mpicc -o hello hello.c      #jazyk c
```
```
mpic++ -o hello hello.cpp   #jazyk c++
```

V obou případech bude výstupem binární soubor hello přeložený překladačem jazyka C resp. C++. Výstupní soubor si můžeme samozřejmě pojmenovat dle libosti s libovolnou koncovkou. Nyní se můžeme pokusit soubor spustit.

Spuštění

mpirun -np 10 hello         #np- number of procesors

Jak vidíte, překlad a spuštění je otázkou dvou jednoduchých instrukcí.

Merlin

Instalace
Instalace na merlinovi je velmi jednoduchá a to až tak jednoduchá, že se nic neistaluje, merlin je totiž pro vaše projekty již připraven.

Překlad
Překlad je analogický překladu na Ubuntu s jednou drobnou odchylkou. Merlinovi totiž musíte sdělit, kde má hledat sdílené knihovny pro překlad. Toto se provede použitím jednoduchého parametru, konkrétní kód překladu na merlinovi pak je:

mpicc --prefix /usr/local/share/OpenMPI -o hello hello.c      #jazyk c

mpic++ --prefix /usr/local/share/OpenMPI -o hello hello.cpp   #jazyk c++

Spuštění
Spuštění je opět analogické s tím, že použijeme již známý parametr. Tentokráte bude merlin na této cestě hledat spustitelné binárky.

mpirun --prefix /usr/local/share/OpenMPI -np 10 hello         #np- number of procesors

Zkuste si pro začátek přeložit na merlinovi ukázkové zdrojové kódy. Ukázky obsahují 4 soubory. Dva z nich jsou zdrojové kódy pro "hello world" (hello.c) resp. "odd-even transposition sort" (odd-even.cpp) a druhé dva jsou shellové (konkrétně bash) skripty pro překlad a spuštění "hello world" (test-hello) resp. "odd-even transposition sort" (test-oe). Testovací programy otestujete ./test-hello resp. ./test-oe. V případě problémů konzultujte užitečné informace na této stránce.

2. Projekt (do 31.3.2013 - za 10 bodů)

Implementace algoritmu "Minimum extraction sort"

Pomocí knihovny Open MPI implementujte algoritmus Minimum extraction sort. Vstupem je posloupnost náhodných čísel uložená v souboru. Délka této posloupnosti nemusí nutně být 2^n, kde n je přirozené číslo!

Vstup
Soubor "numbers" obsahující čísla velikosti 1 byte, která jdou bez mezery za sebou. Pro příklad vytvoření takovéhoto souboru prostudujte soubor "test-oe", ve kterém je ukázáno vytvoření takovéto posloupnosti náhodných čísel a její uložení do souboru pomocí utility dd. Tato utilita generuje náhodná čísla v rozsahu určeném velikostí bloku. Při bloku 1B jsou hodnoty v rozsahu 0-255. Tato čísla jsou pak přesměrována do souboru. Vznikne tak soubor s náhodnými znaky jdoucími bez mezery za sebou. Po otevření v libovolném textovém editoru se hodnoty tváří jako náhodné ascii znaky, které by však měly být chápány jako celá čísla. Soubor je v tomto případě chápán jako binární.

Výstup
Na prvním řádku výstupu stdout (konzole/terminál) jsou to načtená (neřazená!) čísla oddělená mezerou. Na každém dalším řádku výstupu na stdout (konzole/terminál) jsou pak čísla seřazené posloupnosti (od nejmenšího po největší, jedna hodnota na řádek) s tím, že jednotlivé hodnoty budou odřádkovány.
Příklad:

Postup
Vytvořte testovací skript, který bude řídit testování. Tento skript přijímá dva parametry a to: pocet_hodnot a pocet_procesoru v tomto pořadí. Skript vytvoří podle velikosti parametru pocet_hodnot soubor "numbers" s náhodnými čísly a následně spustí program s počtem procesorů pocet_procesoru. Nakonec po sobě skript uklidí binárky a soubor "numbers" (inspirace například v test-oe).

Dokumentace
Součástí řešení je dokumentace, která bude o objemu maximálně 3 strany funkčního textu (tzn. bez případné úvodní strany, obsahu...). V dokumentaci popište zadání, rozbor a analýzu algoritmu, jeho teoretickou složitost a výsledky naměřené při experimentování s posloupnostmi různých délek. Dále znázorněte komunikační protokol, jak si "procesory" zasílají zprávy. Pro vizualizaci použijte sekvenční diagram (http://en.wikipedia.org/wiki/Sequence_diagram). Pozor, hodnotí se i to, jak dokumentace působí! (zejména vzhled, správná čeština/slovenština/angličtina). Knihovna Open MPI je navržena na praktické použití, proto neobsahuje žádné implicitní metody pro měření složitosti algoritmů. Je tedy třeba vymyslet nějaký explicitní způsob jejího měření a tento zdůvodnit v dokumentaci!

Odevzdání
Do wisu se odevzdává jeden archiv xlogin00.{tar|tgz|zip}, který bude velký do 1MB, a který obsahuje:

zdrojový kód- mes.{c|cpp}
hlavička- mes.h (pokud ji využijete)
testovací shellový skript- {test|test.sh}
dokumentaci- xlogin00.pdf
nic jiného (binárky, obrázky...)

Platí, že za nedodržení těchto požadavků budou strhávány body. Počítejte s tím, že veškerá uvedená jména souborů jsou case sensitive.

Doplňkové informace
Pokud délka posloupnosti NENÍ 2^n, je třeba ji doplnit na nejbližší vyšší hodnotu 2^n (např. dostaneme 5 hodnot, je tedy třeba tento počet rozšířit na 8). Je třeba doplnit hodnotami, které nemohou být v řazené posloupnosti. Pokud budete vytvářet náhodné hodnoty pomocí utilitky dd, můžete za neutrální hodnotu považovat např. -1 (dd při velikosti bloku 1B vytváří hodnoty v rozsahu 0-255). Při opravování bude pocet_hodnot a pocet_procesoru zadáván korektně (tedy např. 5 hodnot, ale 15 procesorů. Pokud n=5, je třeba rozšířit na nejbližší mocninu 2, tedy n=8. Pak p(n)=2n-1 => p(8)=16-1=15).

3. Projekt (do 28.4.2013 - za 10 bodů)

Implementace algoritmu "Mesh multiplication"

Pomocí knihovny Open MPI implementujte algoritmus Mesh Multiplication.

Vstup
Vstupem jsou dva soubory "mat1" a "mat2", které obsahují matice pro násobení. "mat1" bude na prvním řádku obsahovat počet řádků matice a "mat2" bude mít na prvním řádku počet sloupců (snadněji se pak bude počítat potřebný počet procesorů). Na dalších řádcích už budou řádky matice ve formátu:hodnota1 hodnota2 ... hodnotaN, kde "N" je počet sloupců matice a hodnoty jsou tedy odděleny mezerami. Toto platí pro "mat1" i "mat2". Matice budou celočíselné (i záporná čísla), např.:

Výstup
Výstupem je výsledná matice vzniklá násobením v pořadí mat1*mat2 na stdout. Na první řádek výstupu vypište:radku:sloupcu výsledné matice. Další řádky výstupu budou řádky výsledné matice ve tvaru:hodnota1 hodnota2 ... hodnotaM, kde M je počet sloupců výsledné matice.

Postup
Vytvořte testovací skript, který bude řídit testování. Skript přečte první řádky obou matic (najděte si příkaz/utilitu head) a podle nich spočte potřebný počet procesorů. Dále spustí program se spočítaným počtem procesorů, program z "mat1" a "mat2" načte matice, vynásobí je a vypíše výsledek. Nakonec po sobě uklidí.

Dokumentace
Pro dokumentaci platí stejná pravidla jako v projektu 2.

Odevzdání
Do wisu se odevzdává jeden archiv xlogin00.{tar|tgz|zip}, který bude velký do 1MB, a který obsahuje:

zdrojový kód- mm.{c|cpp}
hlavička- mm.h (pokud ji využijete)
testovací shellový skript- {test|test.sh}
dokumentaci- xlogin00.pdf
nic jiného (binárky, obrázky...)

Doplňkové informace
...

Užitečné informace

Knihovna mpi je určena zejména pro praktické použití, a autoři nedoporučují spouštět na jednom stroji více "procesorů". Jednak potom knihovna běží pomaleji, ale hlavně je problém v tom, že každý "procesor" je vytvořen jako samostatný proces v sytému a navíc mohou být za běhu vytvářeny další procesy. Toto může vyústit až v neschopnost spuštění programu, protože systém mu nedovolí vytvořit tolik synovských procesů. Doporučuji proto testovat algoritmy tak, abyste použili počet procesorů maximálně okolo 20. Pokud však uvidíte hlášku podobnou
```
[merlin.fit.vutbr.cz:24462] [[15882,0],0] ORTE_ERROR_LOG: The system limit on number of children a process can have was reached in file base/odls_base_default_fns.c at line 676
```
, nepropadejte panice! Zkušenost ukázala, že stačí nechat merlina pár chvil "odpočnout" (rozuměj nepřekládat znovu) a poté to zkusit s nižším počtem "procesorů". Pro zvídavé: některé limity si můžete zobrazit na svém oblíbeném linuxu pomocí
```
ulimit -a
```
a pomocí jednotlivých přepínačů je i měnit. Maximální hodnota je specifikována
```
ulimit -H -a
```
. Jsou to tzv. hard limity a pokud nejste administrátor, jejich hodnoty měnit nemůžete.
Naše programy budou psány ve stylu SPMD (same program, multiple data), všechny "procesory" tedy dostanou stejný kód, kde jediným rozpoznávacím znakem daného procesoru je jeho rank. Pokud chcete projekty úspěšně vytvořit, musíte tuto filosofii respektovat.
Openmpi neumí měnit po startu počet procesorů, proto je vhodné si vytvořit skript, který toto spočítá dopředu podle použitého algoritmu a počtu vstupních hodnot. Při vypracování projektů tedy můžete počítat s tím, že hodnoty budou při testování zadávány korektně.
Pokud budete na merlinovi vytvářet spustitelné skripty, je třeba jim přidat příznak spustitelnosti:
```
chmod +x file_name
```

Užitečné odkazy

Ukázky zdrojových kódů pro merlina

Komunikace

Dotazy k projektu zasílejte na izakjakub@fit.vutbr.cz. Případné konzultace jsou možné po dohodě emailem. Budu vděčný i za jakékoli připomínky ohledně fungování knihovny a práci s ní.

Poslední úprava: Jakub Žák, 06.02.2013 (specifikace zadání pro rok 2013)