IV112 - Projekt z programování paralelních aplikací

IV112 - Projekt z programování paralelních aplikací (podzim 2012)

Obsah kurzu

Účelem projektu je hlubší seznámení se s problematikou návrhu a implementace paralelních systémů. Student by měl získat praktickou zkušenost s programováním vícevláknových či jinak paralelních aplikací a s řešením problémů souvisejících s paralelizací algoritmů. V rámci kurzu studenti vypracují individuálně několik menších projektů, jejichž zadání bude shodné pro všechny studenty a bude postupně zveřejněno.

Ukončení a hodnocení

Pro udělení zápočtu je nutné úspěšně vypracovat v požadované kvalitě všechny projekty zadané během semestru. Každý projekt má stanoven pevný termín odevzdání, zadání každého projektu je zveřejněno vždy minimálně 14 dní před jeho termínem odevzdání. Způsob odevzdání je součást zadání projeku. Pro každý projekt může student jednou požádat vyučujícího o kontrolu kvality vypracování projektu. Tuto žadost však může provést nejpozději týden před termínem odevzdání daného projektu. Pokud vyučující neuzná vypracování v termínu odevzdaného projektu za odpovídající nebo pokud student neodevzdá projekt v termínu, má možnost projekt odevzdat ještě jednou v termínu stanoveném vyučujícím během prvních 14 dnů výuky (zpravidla k 12.týdnu semestru). Této možnosti však student může využít maximálně u dvou projektů.

Termín pro opožděné odevzdání v semestru podzim 2012: 3. prosince 2012

Projekty řešené v semestru podzim 2012:

Projekt číslo 1 -- Kompilace a spuštění MPI knihovny a MPI programu

Termín odevzdání:	15. října 2012, 19:00
Forma odevzdání:	Osobní demonstrace vyučujícímu.
Zadání:	Cílem projektu je přeložit a instalovat do svého domovského adresáře knihovnu OpenMPI, a poté s touto knihovnou přeložit a spustit (distribuovaně) na počítačích `nymfe*` paralelní program DiVinE pro vybrané vstupní modely, jež jsou součástí instalačního balíčku DiVinE. (Poslední vývojové verze nástroje DiVinE zde.)

Projekt číslo 2 -- Parallelismus ve sdílené paměti

Termín odevzdání:	22. října 2012, 19:00
Forma odevzdání:	Odevzdává se soubor IV112_02_UCO.tar.gz, který obsahuje sbalený stejnojmenný adresář se zdrojovými kódy a souborem Makefile tak, aby po provedením příkazu `make` v daném adresáři na stroji `nymfe*` se aplikace přeložily a spustily. Výpisy na obrazovku by měly být samovysvětlující a dokumentující probíhající úkony.
Zadání:	Napište paralelní aplikaci, která spustí 12 vláken nebo procesů. Každé vlákno/proces vygeneruje náhodné číslo v rozmezí 1--100, aplikace potom spočítá, které vlákno/proces vygenerovalo největší číslo, které vlákno/proces nejmenší číslo, a jaký je průměr všech vygenerovaných čísel. Tuto aplikaci realizujte pomocí standardů POSIX Threads, OpenMP a MPI. Dobrovolně je též možné vypracovat tutéž aplikaci využivající rozhraní UNIX SYS V.

Projekt číslo 3 -- Výpočetní bariéra ve sdílené paměti (podmínkové proměnné POSIX Threads)

Termín odevzdání: 29. října 2012, 19:00

Forma odevzdání: Odevzdává se soubor IV112_03_UCO.tar.gz, který obsahuje sbalený stejnojmenný adresář se zdrojovými kódy a souborem Makefile tak, aby po provedením příkazu make v daném adresáři na stroji nymfe* se aplikace přeložily a spustily. Výpisy na obrazovku by měly být samovysvětlující a dokumentující probíhající úkony.

Zadání:

V tomto projektu je vaším úkolem implementovat bariéru pracující ve sdílené paměti a využívající POSIX Thread Library. Bariéra je základní synchronizační primitivum, které zaručuje, že každé vlákno bude pokračovat v provádění příkazů za bariérou až v případě, že všechna ostatní vlákna tuto bariéru dosáhnou.

Abyste splnili tento projekt, je potřeba implementovat tyto 4 druhy (mode) bariéry:

bariéru využívající busy waiting
bariéru využívající jedné podmínkové proměnné
bariéru využívající n podmínkových proměnných (n je počet vláken) s lineární hloubkou počtu signalizací
bariéru využívající n podmínkových proměnných (n je počet vláken) s logaritmickou hloubkou počtu signalizací

K implementaci využijte přiložené soubory (IV112_03_template.tgz) main.cc, main.h a barrier.h. Vaším úkolem je vytvořit soubor barrier.cc, který implementuje funkce definované v souboru barrier.h. Konkrétně se jedná o 4 funkce implementující požadované bariéry:

funkce void busy_wait(const int id, const int num) pro bariéru založenou na busy waiting
funkce void one_condition_variable(const int id, const int num) pro bariéru založenou na jedné podmínkové proměnné
funkce void n_condition_variables(const int id, const int num) pro bariéru založenou na n podmínkových proměnných (n je počet vláken) s lineárním počtem signalizací
funkce void n_condition_variables_log(const int id, const int num) pro bariéru založenou na n podmínkových proměnných (n je počet vláken) s logaritmickým počtem signalizací,

kde id je identifikace vlákna (0 až n-1) a num je celkový počet vláken. Dále implementujte dvě pomocné funkce:

void init(const int mode, const int num) sloužící k alokaci a inicializaci potřebných datových struktur pro jednotlivé bariéry
void finit(const int mode, const int num) sloužící k dealokaci potřebných datových struktur pro jednotlivé bariéry.

Tyto pomocné funkce jou volány pouze jedním vláknem a to vždy před/po vytvoření vláken, které realizují jednotlivé bariéry. Tyto funkce nejsou počítány do doby provádění jednotlivých bariér. Vaším úkolem je rovněž provést jednoduché experimety pro různé počty vláken. V ideálním případě by jste měli pozorovat vzrůstajíci efektivitu jednotlivých bariér pro synchronizaci velkého počtu (v řádu tisíců) vláken.

Projekt číslo 4 -- Tranzitivní uzávěr grafu zadaného maticí (OpenMP)

Termín odevzdání:	5. listopadu 2012, 19:00
Forma odevzdání:	Odevzdává se soubor IV112_04_UCO.tar.gz, který obsahuje sbalený stejnojmenný adresář se zdrojovými kódy a souborem Makefile tak, aby po provedením příkazu `make` v daném adresáři na stroji `nymfe*` se aplikace přeložily a spustily. Výpisy na obrazovku by měly být samovysvětlující a dokumentující probíhající úkony.
Zadání:	V tomto projektu je vaším úkolem implementovat paralelní výpočet tranzitivního uzávěru orientovaného grafu, zadaného jako matici sousednosti. Je nutné pro tuto paralelní implementaci použít systém OpenMP. Jako součást zadání jsou k dispozici soubory Makefile, main.cpp a common.h, zadani.txt a adresáře input/ a expected/ (IV112_04_template.tgz). Vaším úkolem je dodat soubory parallel.cpp a sequential.cpp (viz Makefile), které demonstrují rozdíl ve výpočtu sekvenčním a výpočtu paralelním, implementovaném pomocí primitiv OpenMP. Stačí implementovat metodu "Matrix::closure()" která z dané matice napočítá její tranzitivní uzávěr. Pro násobení dvojice matic použijte naivní O(n^3) algoritmus, pro výpočet tranzitivního uzávěru aplikujte algoritmus, který použije O(logn) násobení. Soubor common.h deklaruje a částečně implementuje datovou strukturu Matrix, soubor main.cpp obsahuje "ovladač" který spustí výpočet. Jako parametr lze použít název souboru, v takovém případě bude tento soubor načten, nebo dvojici čísel, které spustí program pro náhodnou matici velikosti dané prvním číslem a random seed daným druhým číslem (nepovinné). Krom implementace sequential.cpp a parallel.cpp je vašim úkolem doplnit Makefile o target "check" který zkontroluje, že binárky sequential a parallel dávají očekávané výsledky pro testovací data dostupné v input/ a expected/. (Tzn. že výstup ./sequential input/c by se měl shodovat s obsahem souboru expected/c.) Navíc cíl check bude kontrolovat, že implementace je idempotentní: ./sequential expected/c nesmí změnit vstupní matici. Poslední částí úkolu je textově popsat přínosy paralelizace tohoto problému, stručný návrh na další možné přístupy mimo vámi zvoleného (existují-li) a úvaha o efektivitě reprezentace matic použité v souboru common.h (včetně odhadu její paměťové náročnosti v závislosti na n, v bajtech; pomůcka: konzultujte dokumentaci, případně hlavičkové soubory STL). Součástí textové zprávy bude také výpis časů srovnávajících sekvenční a paralelní výpočet pro matice velikosti 500, 1000 a 1200. Výstupem tedy bude tarball, který obsahuje: main.cpp a common.h (součást zadání) adresáře input/ a expected/ (součást zadání) Makefile (s přidaným cílem check) sequential.cpp (sekvenční implementace) parallel.cpp (paralelní implementace postavená na OpenMP) případné pomocné soubory pro implementaci make check textovou zprávu v souboru zprava.txt Výstupní tarball nebude obsahovat další soubory (zejména ne binárky, zálohy textového editoru a pod.).

Projekt číslo 5 -- Porovnání paralelních alokátorů

Termín odevzdání: 12. listopadu 2012, 19:00

Forma odevzdání: Odevzdává se soubor IV112_05_UCO.tar.gz, který obsahuje sbalený stejnojmenný adresář se zdrojovými kódy a souborem Makefile tak, aby po provedením příkazu make v daném adresáři na stroji nymfe* se aplikace přeložily a spustily. Výpisy na obrazovku by měly být samovysvětlující a dokumentující probíhající úkony.

Zadání:

Cílem tohoto projektu je seznámit se s problematikou alokace paměti v kontextu návrhu a implementace paralelních aplikací.

Vaším úkolem je v krátké zprávě zhodnotit kvalitu minimálně čtyř paměťových alokátorů v kontextu programování paralelních aplikací. Za tímto účelem budete implementovat sadu testovacích programů, které k vyhodnocení alokátorů použijete. Vaše testovací sada musí testovat alokátory minimálně na následující vlastnosti: (podrobnější popis vlastností je možné vyčíst v [1])

Rychlost: Paralelní alokátor musí být schopen provádět operace malloc a free stejně rychle jako dobrý sekvenční alokátor, aby byla zachována efektivita sekvenčních programů a paralelních programů běžících na jednoprocesorových architekturách.
Škálovatelnost: Výkonnost alokátoru by měla lineárně růst s počtem použitých procesorů/jader.
Eliminace aktivního false sharing: Aktivní false sharing nastává pokud vlákna mají svá privátně alokovaná data umístěna alokátorem na stejnou cache line. (Vlákna nepřistupují k datům jiných vláken na stejné cache line.)
Eliminace pasivního false sharing: Pasivní false sharing nastavá, pokud aplikace nejdříve v jednom vlákně alokuje blok paměti, který posléze uvolní, a poté dvě různá vlákna alokují bloky (poloviční velikosti) a alokátor použije pro uspokojení těchto požadavků paměť uvolněnou v předchozí dealokaci tak, že se bloky alokovaná pro různá vlákna vyskytnou na stejné cacheline.
Vámi zvolený nejhorší scénář : Test, který dle Vašeho názoru vede na nejhorší možný scénář použití paměťového alokátoru paralelním programem.

Odevzdávaný tarball bude obsahovat

Vámi implementované testovací programy.
Skript, který provede kompilaci a spuštění testovacích programů na 2 až 16 vláknech pro všechny zvolené alokátory.
Zprávu, která shrnuje vyhodnocuje alokátory na základě Vašich testů a prezentuje výsledky testů v čitelné a pochopitelné podobě.
Pokud vámi vybrané alokátory nejsou standardně systémově instalovány, budou jejich zdrojové soubory součástí tarballu a budou kompilovány v rámci překladu Vašich testovacích programů.

Navrhované alokátory (možno vybrat i jiné)

standardní libc malloc
Hoard [1]
Streamflow [5]
jemalloc [2]
...

Reference:

[1] Hoard: A Scalable Memory Allocator for Multithreaded Applications, by Emery D. Berger, Kathryn S. McKinley, Robert D. Blumofe, and Paul R. Wilson (článek, alokátor)
[2] jemalloc (Project homepage)
[3] Scalable Lock-free Dynamic Memory Allocation by Maged M. Michael (článek, alokátor (pouze ve verzi pro 32 bit OS) )
[5] Scalable Locality-Conscious Multithreaded Memory Allocation by Scott Schneider, Christos, D. Antonopoulos, and Dimitrios S. Nikolopoulos (článek, alokátor)

Projekt číslo 6 -- Sdílené datové struktury (FIFO)

Termín odevzdání:	19. listopadu 2012, 19:00
Forma odevzdání:	Odevzdává se soubor IV112_06_UCO.tar.gz, který obsahuje sbalený stejnojmenný adresář se zdrojovými kódy a souborem Makefile tak, aby po provedením příkazu `make` v daném adresáři na stroji `nymfe*` se aplikace přeložily a spustily. Výpisy na obrazovku by měly být samovysvětlující a dokumentující probíhající úkony.
Zadání:	V tomto projektu je vaším úkolem implementovat datovou strukturu (frontu) pro jednosměrnou komunikaci dvou vláken. Vlákno A bude do fronty vkládat hodnoty a vlákno B je z této fronty ve stejném pořadí vybírat. Jako součást zadání (fifos.tar.gz)jsou k dispozici soubory Makefile, driver.cpp, adresář wibble/ a dvě "vzorové" implementace, naive.hpp a ring.hpp. Vaším úkolem je dodat soubor student.hpp a modifikovat soubor driver.cpp, a to tak, aby na počítači nymfe* byla propustnost vaší implementace (měřená programem driver) alespoň 21000 položek/ms. Očekávaný výkon dodaných příkladů (naive a ring) je zhruba 8000 a 15000 položek/ms. (Dosažitelná propustnost na stroji nymfe* je kolem 42000 položek/ms.) V souboru student.hpp dodejte také textový popis implementace a stručné odůvodnění korektnosti (zejména použití nebo nepoužití klíčového slova volatile a/nebo paměťových bariér). Požadavky na rozhraní a chování vaší implementace odvoďte z dodaných příkladů. Kód který je vám k dispozici v driver.cpp krom měření propustnosti také kontroluje základní správnost implementace.

Projekt číslo 7 -- Multimediální rozšíření CPU

Termín odevzdání:	26. listopadu 2012, 19:00
Forma odevzdání:	Odevzdává se soubor IV112_07_UCO.tar.gz, který obsahuje sbalený stejnojmenný adresář se zdrojovými kódy a souborem Makefile tak, aby po provedením příkazu `make` v daném adresáři na stroji `nymfe*` se aplikace přeložily a spustily. Výpisy na obrazovku by měly být samovysvětlující a dokumentující probíhající úkony.
Zadání:	V tomto projektu je vaším úkolem aplikovat multimediální rozšíření procesoru (SIMD paralelizmus) na jednoduchý problém výpočtu průměrné hodnoty pole náhodných čísel. V zadání dostáváte soubor main.cpp (mmx.tar.gz), který není potřeba dále měnit. Dodejte soubory scalar.h a vector.h, které budou implementovat třídu Average s rozhraním požadovaným v main.cpp. Důležitá omezení: hodnoty předávané v poli jsou vždy menší než 4096. Použijte tedy vhodný datový typ (16b). Dávejte pozor na přetečení. Statická metoda "init" ve třídě Average vytvoří (alokuje) pole zadané velikosti (v případě vektorové implementace pozor na zarovnání). Metoda reset() vynuluje stav objektu a metoda process bude brát referenci na hodnotu typu Data který byl předem inicializovaný pomocí init (viz main.cpp). Metoda process může být (je) volaná opakovaně a výsledná hodnota average() musí odpovídat průměru všech hodnot jí předaných od posledního volání reset(). Celkově musí být třída Average schopna zpracovat aspoň 134217728 hodnot (ale pokud možno, i tomuto omezení se vyhněte). Při implementaci souboru vector.h použijte vestavěné funkce a datové typy pro SIMD z hlavičkového souboru emmintrin.h (součást GCC). Výstupní tarball bude obsahovat: main.cpp (součást zadání) Makefile (s případnými úpravami) scalar.h vector.h textovou zprávu v souboru zprava.txt. V defaultním Makfile se překládá také binárka "auto", která vznikne překladem vaší "skalární" verze kódu s automatickou vektorizací v GCC. Ve zprava.txt srovnejte chování všech tří přístupů (scalar, vector a auto) a rozdíly kvantifikujte.

Jiri Barnat's Homepage