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

• Přednášky: Středa, 12:45 (KN:E-107)
• Cvičení: Středa 16:15, 18:00 ; Čtvrtek 9:15, 11:00, 16:15, 18:00
• Přednášející: Jakub Mareček, Michal Jakob
• Cvičící: David Fiedler, Jan Mrkos,Peter Macejko, David Milec, Matěj Kafka, Michal Slouka
• Konzultační hodiny: na vyžádání

• Fórum
• Odevzdávací systém BRUTE

• Standardní učebnice: The Art of Multiprocessor Programming (by Maurice Herlihy, Nir Shavit, Victor Luchangco, and Michael Spear). Vydání z roku 2012 je zdarma dostupné on-line po přihlášení přes ČVUT SSO,
• Příklady ze standardní dokumentace OpenMP v C i PDF,
• Velmi praktické rady: Using OpenMP (Portable Shared Memory Parallel Programming, by Barbara Chapman, Gabriele Jost and Ruud van der Pas), 2007,
• Neformální úvod: Programming on Parallel Machines (by Norm Matloff), 2012, k dispozici zdarma on-line

• 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

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 se získavají za aktivity v semestru (celkem maximálně 40b) a ze zkoušek (maximálně 60b).

Předmět se skládá ze dvou tématických bloků a body v semestru můžete získat za vypracování semestrálních úloh:

• Paralelní výpočty (max 22 bodů):
  • 5 malých programovacích úloh (max 10 bodů)
  • Semestrální práce (max 12 bodů)
• Distribuované výpočty (max 18 bodů):
  • 2 malé úlohy (max 4 body)
  • Semestrální práce (max 14 bodů)
• U všech úloh se pro hodnocení vždy uvažuje poslední odevzdané řešení
• Pro udělení zápočtu je je potřeba získat alespoň 50% bodů, tj. 20 bodů ze 40.

• 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 40 bodů, pro úspěšné složení nutno získat alespoň 20b). 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í iteoretickou zkoušku).

Při tvorbě úloh se řiďte pravidly samostatné práce.

Vzhledem k tomu, že zadání zkoušky bude naprogramování 2 menších jednodušších úkolů, které vycházejí z úkolů probíraných na přednášce a cvičení, nemůžete během zkoušky používat žádné vlastní připravené kódy ani materiály. K dispozici bude standardní linux desktop s vývojovým prostředím CLion. K dispozici bude přístup na tyto webové stránky s referencemi na C++ (en.cppreference.com) a vektorové instrukce (software.intel.com/sites/landingpage/IntrinsicsGuide/) a taky dokumentaci k OpenMP (z openmp.org).

K dispozici budete mít lokálně binární kód se vzorovým řešením pro porovnání škálovatelnosti, odevzdávání a automatická evaluace bude prostřednictvím systému (ne BRUTE) se stejnou HW konfigurací.

* 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 je možné stáhnout zde.

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 pralelní (15b.) i distribuované (25b.) čá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ů).

Pro úspěšné ukončení předmětu musíte splnit 3 na sobě nezávislé podmínky: