====== B4B36PDV – Paralelní a distribuované výpočty ====== ===== Obecné informace ===== * Přednášky: Středa, 12:45 (KN:E-107),online přednášky na MS Teams (přistupujte přes AD účet na ČVUT). Jako záložní variantu zvažujeme [[https://meet.google.com/eax-dyef-zur|Google Meet]], který by byl přístupný jen přes Google účet na FEL ČVUT. * Cvičení: Středa 16:15, 18:00 ; Čtvrtek 9:15, 11:00, 14:30, 16:15, 18:00 * Přednášející: [[http://cs.felk.cvut.cz/en/people/marecjak|Jakub Mareček]], [[http://cs.felk.cvut.cz/en/people/jakobmic|Michal Jakob]] * Cvičící: [[http://cs.felk.cvut.cz/en/people/tomaspe7|Petr Tomášek]], [[https://dsn.felk.cvut.cz/wiki/lide/macejko|Peter Macejko]], [[http://cs.felk.cvut.cz/en/people/mrkosja1|Jan Mrkos]], [[http://cs.felk.cvut.cz/en/people/fiedlda1|David Fiedler]], [[http://cs.felk.cvut.cz/en/people/vanapet1|Petr Váňa]], [[http://cs.felk.cvut.cz/en/people/milecdav|David Milec]] * Konzultační hodiny: na vyžádání ===== Důležité odkazy ===== * Fórum: [[https://cw.felk.cvut.cz/forum/forum-1704.html]] * Odevzdávací systém: [[https://cw.felk.cvut.cz/brute/]] * Link na kvízy: [[https://goo.gl/a6BEMb]] * Finální anketa cvičení: TBA ===== Zdroje k paralelnímu počítání ===== * 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é [[https://dl.acm.org/doi/book/10.5555/2385452|on-line]] po přihlášení přes ČVUT SSO, * Příklady ze standardní dokumentace OpenMP v [[https://github.com/OpenMP/Examples/tree/master/sources|C]] i [[https://www.openmp.org/wp-content/uploads/openmp-examples-5-0-1.pdf|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 [[http://heather.cs.ucdavis.edu/parprocbook|on-line]] ===== Zdroje k distribuovanému počítání ===== * Standardní učebnice: Distributed Systems (by Maarten van Steen, Andrew S. Tanenbaum), 3.01 Edition, 2017, k dispozici [[https://www.distributed-systems.net/index.php/books/ds3/|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). Předmět se skládá ze dvou tématických bloků a body můžete získat za vypracování semestrálních úloh a za zkoušku: * 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í * Ze semestru je potřeba získat alespoň 50% bodů, tj. 20 bodů ze 40. * Programovací zkouška (max 20 bodů, pro složení předmětu nutno získat alespoň 10b) * Teoretická zkouška (max 40 bodů, pro složení předmětu nutno získat alespoň 20b) ===== Zkoušky ===== === Pravidla zkoušky : === 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í. \\ == Příklad zkoušky z minulého roku == * 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 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 {{ :courses:b4b36pdv:zk_05.zip |zde}}. \\ \\ === Teoretický termín === 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. Zkouška proběhne on-line v systému BRUTE a bude během ní povinnost mít zapnutou kameru. 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í.