Paralelní a distribuované programování

Přednášející:

Pavel Tvrdík (gar.)

Cvičící:

Pavel Tvrdík (gar.), Ivan Šimeček, Michal Šoch

Předmět zajišťuje:

katedra počítačových systémů

Anotace:

21. století v architekturách počítačů je dominantně ovlivněno posunem Moorova zákona do paralelizace CPU na úrovni výpočetních jader. Paralelní výpočetní systémy se tak stávají na této úrovni počítačových architektur běžně dostupnou komoditou. Paralelní programování se tak stává základním paradigmatem vývoje efektivních aplikací na těchto platformách. Díky virtualizačním technologiím a následnému rozvoji cloudových technologií, díky rozmachu technologií webu a frameworků na zpracování velkých dat jsou dnes zase klíčové znalosti a dovednosti pro vývoj distribuovaných výpočtů.

Studenti se v tomto předmětu seznámí s architekturami paralelních a distribuovaných výpočetních systémů a s jejich modely a s dvěma hlavními nástroji pro jejich programování: jazykem OpenMP a knihovnou MPI. Pochopí fundamentální paralelní algoritmy a možnosti paralelizace řešení vybraných problémů. Součástí výuky je i projekt praktického programování v OpenMP a MPI pro řešení zadaného problému. Předmět se dotkne i moderních nástrojů na distribuované zpracování velkých objemů dat.

Požadavky:

Základy sekvenční algoritmizace, programování, znalost jazyka C/C++, teorie složitosti, architektur počítačů a teorie grafů.

Osnova přednášek:

1. Modely a architektury paralelních a distribuovaných počítačových systémů a výpočtů.

2. Paralelní programování nad sdílenou pamětí (OpenMP).

3. Paralelní algoritmy pro prohledávání stavového prostoru.

4. Efektivní paralelní programování ve sdílené paměti.

5. Paralelní řazení ve sdílené paměti.

6. Paralelní programování nad distribuovanou pamětí (MPI).

7. Propojovací sítě paralelních počítačů.

8. Kolektivní komunikační algoritmy.

9. Paralelní redukce a sken.

10. Paralelní distribuované algoritmy v OpenMP/MPI.

11. Paralelní V/V.

12. .MapReduce frameworky, principy, modely, algoritmy.

Osnova cvičení:

1. Návrh a implementace sekvenčního algoritmu pro řešení semestrální úlohy.

2. Návrh a implementace paralelního algoritmu pro vícejádrový systém s použitím OpenMP - verze s task paralelismem.

3. Návrh a implementace paralelního algoritmu pro vícejádrový systém s použitím OpenMP - verze s datovým paralelismem.

4. Návrh a implementace paralelního algoritmu pro distribuovaný klastr s použitím MPI.

5. Teoretická a praktická analýza chování paralelního programu a vypracování technické zprávy.

Cíle studia:

Diky rozvoji cloudových, webových a komunikačních technologií a přesunu Moorova zákona do úrovně paralelizace CPU se paralelní a distribuované aplikace stávají dominantními.

Studenti se seznámí s architekturami paralelních a distribuovaných výpočetních systémů a s jejich modely a s jazyky a prostředími pro jejich programování. Naučí se důležité paralelní algoritmy a návrhové vzory pro paralelní a distribuované programování.

Studijní materiály:

[1] Mattson, T.G. - Sanders, B.A. - Massingill, B.L.: Patterns for Parallel Programming. Addison-Wesley Professional. 2004. 978-0321940780.

[2] Kumar, V. - Grama, A. - Gupta, A. - Karpis, G.: Introduction to Parallel Computing: Design and Analysis of Parallel Algorithms. Benjamin-Cummings. 1994. 0805331700.

[3] Miller, R. - Boxer, L.: Algorithms Sequential and Parallel: A Unified Approach. Pearson Education. 1999. 0130863734.

[4] Wilkinson, B. - Allen, M.: Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Prentice Hall. 1998. 0136717101.

[5] Jaja, J.: An Introduction to Parallel Algorithms. Addison-Wesley. 1992. 0201548569.

Poznámka:

Tento předmět obsahově navazuje na bakalářský předmět Algoritmy a grafy 1

https://courses.fit.cvut.cz/MI-PDP/

Další informace:

https://courses.fit.cvut.cz/MI-PDP/

Rozvrh na zimní semestr 2020/2021:

Rozvrh není připraven

Rozvrh na letní semestr 2020/2021:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost TH:A-942 Tvrdík P. 14:30–16:00 (přednášková par. 1) Thákurova 7 (FSv-budova A) místnost TK:BS Tvrdík P. 14:30–16:00 (přednášková par. 1) Dejvice NTK Ballingův sál
Út
St	místnost T9:350 Šimeček I. 09:15–10:45 (přednášková par. 1 paralelka 101) Dejvice NBFIT PC ucebnamístnost T9:350 Šimeček I. 11:00–12:30 (přednášková par. 1 paralelka 102) Dejvice NBFIT PC ucebnamístnost T9:350 Šimeček I. 12:45–14:15 (přednášková par. 1 paralelka 103) Dejvice NBFIT PC ucebnamístnost T9:350 Šoch M. 16:15–17:45 (přednášková par. 1 paralelka 104) Dejvice NBFIT PC ucebnamístnost T9:350 Šoch M. 18:00–19:30 (přednášková par. 1 paralelka 105) Dejvice NBFIT PC ucebna
Čt	místnost T9:351 Šoch M. 07:30–09:00 (přednášková par. 1 paralelka 106) Dejvice NBFIT PC ucebnamístnost T9:351 Šoch M. 09:15–10:45 (přednášková par. 1 paralelka 107) Dejvice NBFIT PC ucebnamístnost T9:351 Šoch M. 11:00–12:30 (přednášková par. 1 paralelka 108) Dejvice NBFIT PC ucebnamístnost T9:351 Šoch M. 14:30–16:00 (přednášková par. 1 paralelka 109) Dejvice NBFIT PC ucebnamístnost T9:351 Šoch M. 16:15–17:45 (přednášková par. 1 paralelka 110) Dejvice NBFIT PC ucebnamístnost T9:351 Šoch M. 18:00–19:30 (přednášková par. 1 paralelka 111) Dejvice NBFIT PC ucebna
Pá

Předmět je součástí následujících studijních plánů:

• Počítačová bezpečnost, verze 2020 (povinný předmět programu)
• Návrh a programování vestavných systémů, verze 2020 (povinný předmět programu)
• Počítačové systémy a sítě, verze 2020 (povinný předmět programu)
• Manažerská informatika, verze 2020 (povinný předmět programu)
• Softwarové inženýrství, verze 2020 (povinný předmět programu)
• Systémové programování, verze 2020 (povinný předmět programu)
• Webové inženýrství, verze 2020 (povinný předmět programu)
• Znalostní inženýrství, verze 2020 (povinný předmět programu)
• Specializace Teoretická informatika, verze 2020 (povinný předmět programu)
• Magisterský program Informatika, plán pro studenty bez specializace, verze 2020 (povinný předmět programu)