B4B36PDV – Paralelní a distribuované výpočty #

Ú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.

• SIMD for C++ Developers – výborný přehled užitečných SIMD instrukcí pro x86 a jak je využít.

• 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 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).

Teoretická zkouška #

Ukázkové zadání teoretické zkoušky

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.

Většina testu budou uzavřené otázky typu multiple choice (správně jedna nebo více možností) nebo s číselnou odpovědí, část budou krátké otevřené otázky (zpravidla lze odpovědět v několika jednoduchých větách). 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ů).

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í #

Ukázkové zadání implementační zkoušky

Úloha 1:
Ve funkci `quicksort_seq` je implementovany quicksort.
Vasim ukolem je algoritmus paralelizovat ve funkci `quicksort_par`.

Úloha 2:
Funkce `find_longest_palindrome_seq` hleda nejdelsi palindrom v predanem vektoru (palindrom je slovo, ktere je stejne
pri cteni od zacatku i od konce). Vasim ukolem je hledani paralelizovat ve funkci `find_longest_palindrome_par`.

Průběh ukončení předmětu #

Pro úspěšné ukončení předmětu musíte získat alespoň polovinu bodů z každé ze 3 částí (viz také diagram níže):

• Alespoň 25 bodů ze semestru (lze vylepšovat i po absolvování zkoušky).
• Alespoň 10 bodů z implementační zkoušky (maximalně 3 pokusy)
• Alespoň 15 bodů z teoretické zkoušky (maximálně 3 pokusy, poslední je opravný).

Pokud máte dostatek bodů, již neplánujete žádnou část vylepšovat a chcete zapsat známku, napište z fakultní adresy e-mail jednomu z přednášejících, a do těla uveďte, kolik bodů máte z každé ze 3 částí a jakou známku očekáváte (smyslem je zkontrolovat, že se shodujeme na tom, jakou známku máte dostat). Přednášející vám známku po kontrole obratem zapíše do KOSu. Preferujeme následující formát (není třeba rozširovat o pozdrav, podpis,…):

[PDV] Žádost o zápis známky

Jméno: 

Body ze semestru: 
Body z implementačky: 
Body z teoretické zkoušky: 

Celkem bodů: 
Očekávaná známka: