460-4117/03 – Paralelní algoritmy I (PA I)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | prof. Ing. Pavel Krömer, Ph.D. | Garant verze předmětu | prof. Ing. Pavel Krömer, Ph.D. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 1 | Semestr | zimní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2022/2023 | Rok zrušení | |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Přehled v oblasti návrhu, realizace a hodnocení paralelních algoritmů. Praktické osvojení paralelních programovacích technik pro vybrané paralelní architektury. Pracovní znalosti v oblasti paralelních systémů a jejich programování, zejména: samostatný návrh paralelních algoritmů, resp. paralelizace sekvenčních algoritmů. Praktická realizace paralelního algoritmu na bázi modelu předávání zpráv. Analýza algoritmu a vyhodnocení implementace. Optimalizace a zvyšování efektivity.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Kurz poskytne posluchačům základy pro aktivní práci v oblasti paralelních systémů, algoritmů a programování. Zaměřuje se na praktickou tvorbu programů, aby byli s to využít dnešní výkonnou výpočetní techniku, od paralelních superpočítačů s distribuovanou pamětí přes vícejádrové procesory až po výpočetní akcelerátory a univerzální grafické karty, pro řešení výpočetně náročných úloh z různých aplikačních oblastí.
Důraz je kladen jak na seznámení se se standardními paralelními paradigmaty, rozhraními, jazyky a knihovnami, tak na reflexi aktuálního vývoje v této oblast prostřednictvím představení nejnovějších paralelních platforem a prostředí. Posluchač bude seznámen s tvorbou paralelních aplikací prostřednictvím modelu předávání zpráv (multipočítačů), s programování systémů se sdílenou pamětí (symetrických multiprocesorů) a programováním výpočetních akcelerátorů. Diskutovány však budou také cloudové platformy, model map-reduce nebo paralelní Matlab.
Cvičení budou věnována praktickému návrhu paralelních algoritmů a jejich implementaci v prostředí MPI, OpenMP, UPC, CUDA-C nebo v paralelním Matlabu.
Povinná literatura:
1. Sylaby k předmětu Paralelní algoritmy I.
2. Introduction to Parallel Computing: From Algorithms to Programming on State-of-the-Art Platforms. Roman Trobec, Boštjan Slivnik, Patricio Bulić, Borut Robič. Springer Nature Switzerland, 2018
3. Parallel Programming for Multicore and Cluster Systems. Thomas Rauber, Gudula Rünger. Springer-Verlag Berlin Heidelberg, 2013
4. Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering. Ian Foster, Addison Wesley, 1995
Doporučená literatura:
1. The OpenMP Common Core: Making OpenMP Simple Again, Timothy G. Mattson, Yun He, Alice E. Koniges. MIT Press, 2019
2. Using OpenMP-The Next Step: Affinity, Accelerators, Tasking, and SIMD. Ruud van der Pas, Eric Stotzer, and Christian Terboven. MIT Press, 2017
3. Distributed Systems (3rd ed.), Andrew S. Tanenbaum, Maarten van Steen, 2017
4. Distributed Computing Principles, Algorithms, and Systems, Ajay D. Kshemkalyani, Mukesh Singhal, Cambridge, 2008
5. Patterns for parallel programming. Timothy Mattson, Beverly Sanders, Berna Massingill, Addison-Wesley, 2004
6. Introduction to Parallel Computing (2nd Edition). Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, Addison-Wesley, 2003
Další studijní materiály
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Posluchači během semestru písemnou formou vypracují tři domácí úkoly na přidělená témata z oblasti paralelních algoritmů. Témata bude zahrnovat paralelní řešení komplexních problémů a použití vhodných různých paralelních technik a metod. Na domácích úkolech budou studenti pracovat během semestru průběžně. Řešení bude možno konzultovat s vyučujícím během přednášek, cvičení, během osobních konzultací nebo e-mailem.
E-learning
Další požadavky na studenta
Další požadavky na studenta nejsou.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
Přednášky:
1. Úvod do problematiky paralelního programování. Konkurence, pseudoparalelismus, paralelismus. Procesy a vlákna. Procesy a vlákna z pohledu operačního systému. SIMD a FMA instrukce moderních procesorů.
2. Sekvenční vs. paralelní programování. Úskalí paralelního programování. Typické problémy a jejich řešení. Synchronizace a vyloučení, uváznutí (definice, vlastnosti, podmínky, detekce, eliminace).
3. Rozdělení paralelních platforem. Systémy se sdílenou a distribuovanou pamětí. Data paralelní a task paralelní úlohy.
4. Programování systémů se sdílenou pamětí. Vlákna v jazycích Java, C#, C++11, Python. Model fork-join a rozhraní OpenMP.
5. Programování systémů s distribuovanou pamětí. Komunikace pomocí zasílání zpráv. Posix fronty, sockety. Rozhraní MPI, základní MPI operace.
6. Další možnosti v systémech s distribuovanu pamětí: modely bulk synchronous parallel a partitioned global address space.
7. Úvod do programování akcelerátorů a koprocesorů. Koncept offloadování výpočtů. Architektura GPGPU (organizace programu, paměti). Datový paralelismus na GPU. Prostředí CUDA a jazyk CUDA-C, OpenACC.
8. Metodika návrhu paralelních algoritmů. Task/channel model paralelního výpočtu. Fosterova návrhová metodologie (rozdělení, komunikace, aglomerace, mapování) a její použití.
9. Návrhové vzory v paralelním programování. Hledání konkurence (doménová a datová dekompozice), struktura algoritmu, implementace. Řešení typických scénářů: nezávislé úlohy, replikace a redukce, rozděl a panuj, pipeline.
10. Reprezentace a analýza paralelního algoritmu (parallel random access machine, bulk synchronous parallel, informal work depth atp.). Výkon a efektivita paralelního algoritmu.
11. Datové struktury pro paralelní algoritmy: zásobník, fronta, pool, spojovaný seznam, hašovací tabulka, stromy, priority. Hlavní rozdíly oproti sekvenčním verzím.
12. Algoritmy pro řešení vybraných problémů: prefix-sum, merging, vyhledávání (orthogonal trees, sorting networks). Rozdíl mezi sekvenčním, naivně paralelním a efektivním paralelním řešením.
13. Datové struktury a algoritmy pro paralelní vyhledávání. 2-3 strom, pipelining. Paralelní vyhledávání, vkládání, mazání.
14. Paralelní algoritmy a datové struktury pro grafové úlohy. Průchody grafy, hledání nejkratších cest, konektivita, nezávislé komponenty, atd.
Cvičení:
Na cvičení se řeší praktické úlohy, ilustrující probírané koncepty. Studenti budou postupně pracovat na následujících zadáních:
1. Řešení výpočetně náročné úlohy za pomoci paralelismu a bez něj. Problém obchodního cestujícího - od triviálně paralelního řešení (brute-force algoritmus) k řešení s použitím IPC (jednoduchá paralelní verze branch-and-bound algoritmu).
2. Datový paralelismus nad velkými daty. Datová dekompozice, data paralelní přístup, vektorizace. Paralelní maticové operaca a shlukování.
3. Zpracování obrazových dat, vliv lokálních závislostí na paralelní algoritmy (konvoluce). Seam carving.
4. Paralelní algoritmy pro grafové úlohy, grafy a nelinerání datové stuktury. Paralelní implementace iterativní verze algoritmu PageRank.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky