CourseWare Wiki
Switch Term
Summer 2023 / 2024
Summer 2022 / 2023
Summer 2021 / 2022
Summer 2020 / 2021
Summer 2019 / 2020
Summer 2018 / 2019
Summer 2017 / 2018
Search
Log In
b232
courses
b4b36pdv
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Both sides previous revision
Previous revision
2024/05/28 16:33 kafkamat
2024/05/28 16:18 kafkamat [Pravidla zkoušky:]
2024/05/28 16:18 kafkamat [Teoretický termín]
2024/05/28 16:18 kafkamat [Zkoušky]
2024/05/28 16:17 kafkamat [Pravidla samostatné práce]
2024/05/27 21:37 kafkamat [Pravidla zkoušky:]
2024/05/27 21:36 kafkamat [Pravidla zkoušky:]
2024/03/14 02:52 kafkamat [Zápočet: Aktivita v semestru (max 40b)]
2024/02/16 23:40 kafkamat
2024/02/16 23:37 kafkamat [Hodnocení předmětu]
2024/02/16 23:35 kafkamat [Hodnocení předmětu]
2024/02/16 23:35 kafkamat [Studijní materiály]
2024/02/16 12:25 kafkamat
2024/02/14 21:12 kafkamat [Zkoušky]
2024/02/14 21:11 kafkamat [Hodnocení předmětu]
2024/02/14 16:08 kafkamat [Obecné informace]
2023/05/26 18:57 external edit
Go
Previous revision
2024/05/28 16:33 kafkamat
2024/05/28 16:18 kafkamat [Pravidla zkoušky:]
2024/05/28 16:18 kafkamat [Teoretický termín]
2024/05/28 16:18 kafkamat [Zkoušky]
2024/05/28 16:17 kafkamat [Pravidla samostatné práce]
2024/05/27 21:37 kafkamat [Pravidla zkoušky:]
2024/05/27 21:36 kafkamat [Pravidla zkoušky:]
2024/03/14 02:52 kafkamat [Zápočet: Aktivita v semestru (max 40b)]
2024/02/16 23:40 kafkamat
2024/02/16 23:37 kafkamat [Hodnocení předmětu]
2024/02/16 23:35 kafkamat [Hodnocení předmětu]
2024/02/16 23:35 kafkamat [Studijní materiály]
2024/02/16 12:25 kafkamat
2024/02/14 21:12 kafkamat [Zkoušky]
2024/02/14 21:11 kafkamat [Hodnocení předmětu]
2024/02/14 16:08 kafkamat [Obecné informace]
2023/05/26 18:57 external edit
Go
courses:b4b36pdv:start [2018/06/14 21:28]
courses:b4b36pdv:start [2024/05/28 16:33]
(current)
kafkamat
Line 1:
Line 1:
+
====== B4B36PDV – Paralelní a distribuované výpočty ======
+
===== Obecné informace =====
+
* Rozvrh: [[https://intranet.fel.cvut.cz/cz/education/rozvrhy-ng.B232/public/html/predmety/47/02/p4702806.html|Rozvrh B4B36PDV]]
+
* 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í (paralelní část): [[https://dsn.felk.cvut.cz/wiki/lide/macejko|Peter Macejko]], [[kafkamat@fel.cvut.cz|Matěj Kafka]], [[sloukmic@fel.cvut.cz|Michal Slouka]], [[mikhada1@fel.cvut.cz|Daria Mikhaylovskaya]]
+
* Cvičící (distribuovaná část): [[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/milecdav|David Milec]]
+
* Odevzdávání domácích úloh: [[https://cw.felk.cvut.cz/brute/student/|BRUTE]]
+
* Konzultační hodiny: na vyžádání
+
* Komunikace: Oficiální komunikační kanál je e-mail, pro neformální komunikaci lze využít kanál ''#pdv'' na [[https://discord.com/invite/YZjJbkvfaS|fakultním Discord serveru]].
+
+
===== Studijní materiály =====
+
+
**Paralelní 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]]
+
+
**Distribuované 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).
+
Body lze získat za domácí úkoly v semestru (celkem maximálně 40b) a ze zkoušek (maximálně 60b).
+
+
==== Zápočet: Aktivita v semestru (max 40b) ====
+
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 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ů)
+
* Pro udělení zápočtu je je potřeba získat alespoň **50% bodů, tj. 20 bodů** ze 40.
+
+
==== Zkouška (max 60b) ====
+
* 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í 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++ ([[https://en.cppreference.com]]), dokumentace OpenMP ([[https://www.openmp.org/wp-content/uploads/OpenMPRefGuide-5.2-Web-2024.pdf]]) a dokumentace vektorových instrukcí ([[https://software.intel.com/sites/landingpage/IntrinsicsGuide/]]).
+
+
==== Příklad zkoušky ====
+
+
<code>
+
* 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í.
+
</code>
+
+
Balíček je možné stáhnout {{ :courses:b4b36pdv:zk_05.zip |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í (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ů).
+
+
===== 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:
+
{{ :courses:b4b36pdv:ukonceni_v1.3.png?nolink |}}