460-4117/01 – 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ě volitelný
RočníkSemestrzimní
Jazyk výukyčeština
Rok zavedení2015/2016Rok 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í
BAT0014 Ing. Tarek Batiha
KRO080 doc. Ing. Pavel Krömer, 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 10+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 (2nd Edition). Ananth Grama, George Karypis, Vipin Kumar, Anshul Gupta, Addison-Wesley, 2003 3. Using OpenMP: Portable Shared Memory Parallel Programming, Volume 10, Barbara Chapman, Gabriele Jost, Ruud van der Pas, MIT Press, 2008

Doporučená literatura:

1. Distributed Computing Principles, Algorithms, and Systems, Ajay D. Kshemkalyani, Mukesh Singhal, Cambridge, 2008 2. Distributed Systems: Principles and Paradigms, Andrew S. Tanenbaum, Maarten van Steen, Pearson Prentice Hall, 2007 3. Patterns for parallel programming. Timothy Mattson, Beverly Sanders, Berna Massingill, Addison-Wesley, 2004

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

Prezenční forma (platnost od: 2015/2016 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:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
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