B4B36PDV – Paralelní a distribuované výpočty #
Rozvrh B4B36PDV
Upload systém BRUTE
Anketa hodnocení výuky 2024
Přednášející: Matěj Kafka 🞄 Michal Jakob
Cvičící:
Peter Macejko 🞄
Jakub Dupák 🞄
Max Hollmann 🞄
Jáchym Herynek 🞄
David Milec 🞄
Adéla Kubíková
Úvod #
PDV je bakalářský předmět pro studenty programu Otevřená informatika. Cílem předmětu je studenty seznámit se základy programování paraleních a distribuovaných systémů. U paralelních výpočtů, vyučovaných v první polovině semestru, je kladen důraz na efektivní využívání výkonu procesoru pro výpočetně náročné operace, v distribuované části se pak předmět věnuje zajištění dostupnosti a spolehlivosti služeb na nespolehlivé síti a strojích.
Komunikace s vyučujícími #
Pokud naleznete jakoukoliv chybu či nejasnost v prezentacích, poskytnutém kódu nebo BRUTE, otevřete prosím issue v GitLab repozitáři předmětu (podobně jako u předmětu OSY). Každá stránka na tomto webu má na konci odkaz “Dejte nám vědět”, který vás přesměruje na předvyplněný issue, případně můžete stránku rovnou upravit a otevřít pull request pomocí odkazu “Uprav tuto stránku”.
Pro neveřejnou komunikaci s vyučujícími preferujeme e-mail. Pro neformální komunikaci lze také využít kanál #pdv
na fakultním Discord serveru, kde se někteří z vyučujících také vyskytují.
Studijní materiály #
Paralelní výpočty #
-
The Deadlock Empire – online hra, kde je vaším cílem najít posloupnost instrukcí mezi vlákny, které způsobí “race condition”. Vhodné na začátek semestru jako opakování OSY.
-
What every systems programmer should know about concurrency – stručný, ale výživný text vysvětlující fungování synchronizačních primitiv na úrovní hardware. Není nutné znát ke zkoušce, ale pomůže objasnit mnoho jevů, se kterými se během semestru setkáte.
-
Příklady použití OpenMP v C i PDF. Může posloužit při přípravě na implementační zkoušku i během implementace domácích úloh – doporučuji využívat jako příručku a přes vyhledávání najít konstrukty, které vás zrovna zajímají.
-
Maurice Herlihy, Nir Shavit: The Art of Multiprocessor Programming – čtivá učebnice, která dobře předává přístup k přemýšlení nad paralelními výpočty i znalosti užitečné pro efektivní paralelizaci. Pokrývá výrazně více látky než projdeme v PDV, doporučuji přečíst úvodní kapitolu a další části používat jako “referenční příručku” při nejasnostech v přednáškách. Vydání z roku 2012 je zdarma dostupné (viz odkaz).
Distribuované výpočty #
- Standardní učebnice: Distributed Systems (by Maarten van Steen, Andrew S. Tanenbaum), 3.01 Edition, 2017, k dispozici on-line.
- Běžná učebnice: Distributed Systems: Concepts and Design (by George Coulouris Jean Dollimore Tim Kindberg Gordon Blair), 5th Edition), 2011
Hodnocení předmětu #
Celkově můžete získat maximálně 100 bodů z předmětu a získat známku A-F (<50b = F, 50-59 = E, …, 90-100 = A). Body lze získat za domácí úkoly v semestru (maximálně 50b) a ze zkoušek (maximálně 50b).
Zápočet: Aktivita v semestru (max 50b) #
Předmět se skládá ze dvou tématických bloků, body v semestru můžete získat za vypracování semestrálních úloh:
- Paralelní výpočty (max 29 bodů):
- 5 malých programovacích úloh (max 15 bodů)
- Semestrální práce (max 14 bodů)
- Distribuované výpočty (max 21 bodů):
- 2 malé úlohy (max 6 bodů)
- Semestrální práce (max 15 bodů)
- Pro udělení zápočtu je je potřeba získat alespoň 50% bodů, tj. 25 bodů z 50.
Zkouška (max 50b) #
- Programovací část zkoušky z paralelní části předmětu (max 20 bodů, pro úspěšné složení nutno získat alespoň 10b, započítává se poslední pokus).
- Teoretická část zkoušky (max 30 bodů, pro úspěšné složení nutno získat alespoň 15b). Při absolvování více úspěšných pokusů se uvažuje maximální dosažený počet bodů.
- Pro úspěšné složení zkoušky je nutné úspěšně složit obě části zkoušky (tj. programovací i teoretickou zkoušku).
Implementační zkouška #
Implementační zkouška se skládá na školních počítačích, prostředí je Ubuntu s nainstalovaným editorem CLion a VS Code. Na počítači bude připravené zadání a sekvenční implementace dvou malých úloh, vaším úkolem bude řešení paralelizovat. Během zkoušky nesmíte používat žádné vlastní materiály. Počítače nemají přístup k internetu, je na nich ale k dispozici offline verze referenční příručky C++, dokumentace OpenMP a dokumentace vektorových instrukcí.
Příklad zadání #
* Upozornění *
Váš kód musí být korektní z hlediska vícevláknového přístupu ke sdíleným proměnným.
Pokud nezabezpečíte synchronizaci, budeme Vaše řešení ručně penalizovat.
Úloha 1:
Vaším úkolem je v daném poli std::vector<std::string> vector projít slova a zjistit,
jaká je Levenshteinho vzdálenost každých dvou slov v tomto poli obsažených. Zároveň
musíte najít i nejnižší index dvojice slov takový, že vzdálenost mezi těmito slovy
je největší.
Zparalelizujte metodu distances (pouze tuto metodu, zadnou jinou) v souboru
levenshtein.cpp, která vrátí sumu vzdáleností slov ve vector každého s každým.
Index s maximální vzdáleností uložte do proměnné maxIdx.
Úloha 2:
Vaším úkolem je paralelizovat aplikaci lokálního filtru ve čtvercové matici čísel
na základě čtyř-okolí prvku. Filtr se aplikuje v iteracích, přičemž v každé iteraci
se pro každý prvek table(i,j) aplikuje výpočet:
table(i,j) = sqrt( (table(i,j)^2 + table(i-1,j)^2 + table(i+1,j)^2 + table(i,j-1)^2 + table(i,j+1)^2)/3 )
sekvenčně od prvku 0,0 po řádcích (pokud prvky v okolí přesahují index matice, použije se hodnota 0).
Zparalelizujte metodu filtering v souboru filter.cpp, která tento výpočet provádí.
Balíček se zadáním je možné stáhnout zde.
Teoretická zkouška #
Na teoretický termín se můžete zapisovat klasicky pomocí KOSu, písemka bude trvat 90 minut, bude se skládat z otázek z paralelní (10b.) i distribuované (20b.) části. Bude mít formu testu sestávajícího z uzavřených otázek vesměs typu multiple choice, tj. správně libovolný počet možností.
V rámci jedné multiple-choice otázky v testu můžete získat mínusové body za špatné odpovědi, ale za jednu otázku je minimální počet bodů 0 (tzn. z testu jako celku není možné dostat záporný počet bodů).
Průběh ukončení předmětu #
Pro úspěšné ukončení předmětu musíte splnit 3 na sobě nezávislé podmínky: