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

Garantující katedraKatedra informatikyKredity4
Garant předmětuprof. Ing. Pavel Krömer, Ph.D.Garant verze předmětuprof. Ing. Pavel Krömer, Ph.D.
Úroveň studiapregraduální nebo graduálníPovinnostvolitelný odborný
Ročník1Semestrzimní
Jazyk výukyčeština
Rok zavedení2015/2016Rok zrušení2022/2023
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
KRO080 prof. Ing. Pavel Krömer, Ph.D.
UHE080 Ing. Vojtěch Uher, Ph.D.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Klasifikovaný zápočet 2+2
kombinovaná Klasifikovaný zápočet 18+0

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 vypracují tři domácí úkoly na přidělená témata z oblasti paralelních algoritmů. Nabízená témata bude zahrnovat paralelní řešení komplexních problémů a použití různých metod a technik paralelních algoritmů. 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 nejsou kladeny.

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 programování paralelních aplikací. 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í. Uváznutí (definice, vlastnosti, podmínky, detekce, eliminace). 3. Paralelní vs. distribuované aplikace. Klasifikace paralelních platforem. Systémy se sdílenou a distribuovanou pamětí. Flynnova taxonomie. 4. Programování systémů se sdílenou pamětí. Programování s pomocí vláken. Knihovna pthreads. Vlákna v jazycích Java a C#. Synchronizace a vyloučení, uváznutí. 5. Rozhraní OpenMP. Podpora OpenMP v překladačích. Direktivy a funkce OpenMP. Redukce v OpenMP. 6. Model Fork-Join. Programovací jazyky Cilk a Cilk++. Paralelní Matlab. Paralelní programování v Pythonu, knihovna NumPy. 7. Programování systémů s distribuovanou pamětí. Komunikace pomocí zasílání zpráv. Posix fronty, sockety. Rozhraní MPI, základní funkce MPI. MPI knihovny. 8. Model Partitioned Global Address Space (PGAS). Programovací jazyk Unified Parallel C (UPC). 9. Dávkové (neinteraktivní) spouštění distribuovaných úloh. Plánovače PBSPro a Torque. 10. Programování v prostředí gridu a cloudu. Webové služby, distribuované aplikace s využitím webových služeb. Paradigma Map-Reduce, framework Hadoop. 11. Úvod do programování akcelerátorů. Architektura GPGPU (organizace programu, organizace paměti). Datový paralelismus. Prostředí CUDA a jazyk CUDA-C. 12. Další rozhraní pro programování akcelerátorú: OpenCL, OpenACC, OpenMP 4. 13. Architektura Intel MIC. Způsoby programování MIC a Xeon Phi. Nové a vznikající platformy. 14. Hybridní paralelní aplikace. Programování pomocí MPI-OpenMP, hybridní CPU-GPU architektury. Cvičení: ======== Obsah cvičení a procvičované úlohy budou korespondovat s látkou probíranou na přednáškách: 1. Přehled prostředí pro tvorbu paralelních aplikací. SIMD instrukce. 2. Implementace jednoduchého programu s více vlákny. 3. Implementace jednoduchého programu ve více procesech. Komunikace pomocí socketů a front. 4. Debugging a profilování paralelních programů. 5. Implementace jednoduchého programu za pomoci OpenMP. Paralelizace sekvenčního programu pomocí OpenMP. 6. Implementace jednoduchého programu v jazyce Cilk++. Příklad paralelního programování v Matlabu. 7. Implementace jednoduchého programu pomocí rozhraní MPI. 8. Implementace jednoduchého programu v jazyce UPC. 9. Použití plánovačů PBS, PBSPro a Torque, příkaz qsub a QSUB direktivy. 10. Implementace jednoduchého map-reduce programu ve frameworku Hadoop. 11. Implementace jednoduchého data-paralelního programu v CUDA-C. 12. Příklady použití OpenCL, OpenACC a OpenMP 4. 13. Programování Intel MIC. Implementace jednoduchého programu pro Intel MIC. 14. Implementace jednoduchého hybridního programu pomocí MPI a OpenMP.

Podmínky absolvování předmětu

Kombinovaná forma (platnost od: 2015/2016 zimní semestr, platnost do: 2022/2023 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodůMax. počet pokusů
Klasifikovaný zápočet Klasifikovaný zápočet 100  51 3
Rozsah povinné účasti:

Zobrazit historii

Podmínky absolvování předmětu a účast na cvičeních v rámci ISP:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2021/2022 (N0688A140014) Průmysl 4.0 P čeština Ostrava 2 povinně volitelný typu B stu. plán
2021/2022 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika P čeština Ostrava 1 volitelný odborný stu. plán
2021/2022 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC K čeština Ostrava 1 volitelný odborný stu. plán
2021/2022 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC P čeština Ostrava 1 volitelný odborný stu. plán
2021/2022 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika K čeština Ostrava 1 volitelný odborný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava povinně volitelný stu. plán
2020/2021 (N0688A140014) Průmysl 4.0 P čeština Ostrava 2 povinně volitelný typu B stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava povinně volitelný stu. plán
2020/2021 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika K čeština Ostrava 1 volitelný odborný stu. plán
2020/2021 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC P čeština Ostrava 1 volitelný odborný stu. plán
2020/2021 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika P čeština Ostrava 1 volitelný odborný stu. plán
2020/2021 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC K čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava povinně volitelný stu. plán
2019/2020 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika P čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC P čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N0541A170007) Výpočetní a aplikovaná matematika (S01) Aplikovaná matematika K čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N0541A170007) Výpočetní a aplikovaná matematika (S02) Výpočetní metody a HPC K čeština Ostrava 1 volitelný odborný stu. plán
2019/2020 (N0688A140014) Průmysl 4.0 P čeština Ostrava 2 povinně volitelný typu B stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K češ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

Hodnocení Výuky



2021/2022 zimní
2020/2021 zimní
2019/2020 zimní
2018/2019 zimní
2017/2018 zimní
2016/2017 zimní
2015/2016 zimní