460-4117/04 – Paralelní algoritmy I (PA I)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. Ing. Pavel Krömer, Ph.D.Garant verze předmětudoc. Ing. Pavel Krömer, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník1Semestrzimní
Jazyk výukyangličtina
Rok zavedení2022/2023Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KRO080 doc. Ing. Pavel Krömer, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 28+28

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

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

Prezenční forma (platnost od: 2022/2023 zimní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Klasifikovaný zápočet Klasifikovaný zápočet 100  51
Rozsah povinné účasti: xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2022/2023 (N0613A140035) Informatika INF P angličtina Ostrava 1 povinný stu. plán
2022/2023 (N0688A140015) Průmysl 4.0 P angličtina Ostrava 2 povinně volitelný typu B stu. plán
2022/2023 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P angličtina Ostrava povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku