| Termín odevzdání: | 7. října 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| Zadání: |
Třída RWlock reprezentuje sdílený zámek, který umožní přístup ke
sdílené paměti vícero vláknům v režimu čtení, ale exkluzivní přístup
vláknu, které chce do sdílené paměti zapisovat. Implementujte poskytnuté rozhraní třídy RWlock za použití funkcí, které vám poskytuje standardní knihovna jazyka C++ verze 11. Je zakázáno použít při implementaci přímo funkce z POSIX Thread Library. Algoritmy pro RWLOCK se můžete inspirovat například na wikipedii. Dle standardu musí být zámek uvolněn stejným vláknem, které zámek zamklo, jinak dojde k nedefinovanému chování. Ačkoliv implementace STD knihovny na Linuxu je benevolentní, STD knihovna poskytnutá spolu s programem Visual Studio 2013 kontroluje vlastnictví zámku při odemykání. Projekt můžete řešit na serveru aisa. V takové případě je nutné přidat si modul gcc-4.8.2 abyste získali překladač s podporou C++11. Projekt:rwlock_student.zip |
| Termín odevzdání: | 14. října 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| Zadání: |
Napište paralelní aplikaci, která spustí vícero vláken nebo procesů
tak, že každé vlákno/proces vygeneruje náhodné číslo v rozmezí
1--100. Poté aplikace spočítá, které vlákno/proces vygenerovalo
největší číslo a ustanoví toto vláno/proces jako vedoucí
vlákno/proces. Aplikace musí řešit problém volby shodného čísla
různými vlákny/procesy. Aplikace o volbě vedoucího informuje
participující vlákna/procesy a volbu vypíše na výstup. Tuto aplikaci
realizujte pomocí standardů POSIX Threads, a MPI. Dobrovolně je též možné vypracovat tutéž aplikaci s využitím rozhraní UNIX SYS V a OpenMP. Projekt můžete řešit na strojích nymfe50-nymfe55. V takovém případě je možné přidat si modul gcc-4.8.2 abyste získali překladač s podporou C++11. Navíc pro účely distribuovaného počítání, doporučuji zařídit si přihlašování mezi stanicemi bez nutnosti zadávání hesla, a stejně tak si i zařídit přidání modulu s gcc-4.8.2 automaticky po přihlášení. Projekt:leader_student.zip |
| Termín odevzdání: | 21. října 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| 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 bude ve
stejném pořadí vybírat.
Jako součást zadání jsou k dispozici soubory Makefile, driver.cpp, pomocné hlavičkové soubory tools.h a compatibilityHeader.h a dvě "vzorové" implementace, naive.hpp a ring.hpp. Vašim ú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) konzistentně výrazně vyšší než výkon dodaných příkladů (naive a ring) - alespoň 100 000 položek/ms, je ovšem možné dosáhnout výkonu přes 250 000 položek/ms. Minimální dosažitelná propustnost na stroji nymfe80 je 5000 položek/ms v případě naive.hpp a cca 55000 položek/ms pro ring.hpp. 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:fifo_student.zip |
| Termín odevzdání: | 28. října 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| Zadání: |
V přiloženém archivu máte zdrojové soubory k programu, který umí na
základě vstupních parametrů vygenerovat detail Mandelbrotova fraktálu
do souboru typu BMP. Vaším úkolem je program analyzovat a vhodně
paralelizovat. K paralelizaci můžete využít libovolný z nástrojů:
POSIX Thread Library, C++11 thread, OpenMP, MPI. Odevzdávejte pouze
zdrojové soubory a Makefile, nikoliv soubory *.bmp. Program umí načíst konfigurační soubor config.txt, ve kterém jsou informace o detailu fraktálu, který se má vykreslit. Odevzdávejte i zajímavé vlastní konfigurace config.txt. Projekt:fraktal_student.zip |
| Termín odevzdání: | 4. listopadu 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| 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:
Překrytí standardního alokátoru lze realizovat pomocí proměnné prostředí:
Odevzdávaný tarball/zip bude obsahovat
Navrhované alokátory (možno vybrat i jiné)
|
| Termín odevzdání: | 11. listopadu 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| 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.
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(log n) 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:
|
| Termín odevzdání: | 18. listopadu 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| 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,
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/zip bude obsahovat:
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. Projekt:mmx_student.zip |
| Termín odevzdání: | 25. listopadu 2015, 18:00 |
| Forma odevzdání: | Odevzdárna v ISu. |
| Zadání: |
Vaším úkolem je implementovat detekci ukončení v distribuované
paměti. Vycházejte z algoritmu známého jako Safrův algoritmus
(Safra's algorithm). K dispozici máte dva soubory - main.cpp a communication.h. V souboru communication.h je k dispozici třída Communication, která zastřešuje funkce z knihovny MPI a poskytuje wrappery pro asynchronní bufferované operace poslání a přijímání zpráv. Není povinné tuto třídu použít. V souboru main.cpp je třída Worker, která náhodně generuje čísla, která posílá náhodným příjemcům v systému. Aby bylo zaručeno, že algoritmus skončí, je postupně snižována pravděpodobnost, že bude vygenerováno další číslo. Po určitém čase se tedy činnost v systému zastaví a jednotlivé procesy budou čekat. Vaším úkolem je implementovat detekci této situace a korektně algoritmus ukončit. Pro splnění tohoto úkolu potřebujete implementovat metodu `bool finish()` a trochu upravit metody `void receive()`, `void next( double )`, konstruktor a destruktor. Dále bude nutné rozšířit třídu Worker o další atributy, případně definice další třídy/struktury. K implementaci a testování použijte stanice nymfe*, kde je předinstalováno prostředí MPI. Detaily Safrova algorimu pro dynamickou detekci ukončení načtěte třeba zde: cdp-8-mpi-2-4up.pdf. Projekt:safra_student.zip |