9600-1006/01 – Paralelní algoritmy (PAL)
| Garantující katedra | IT4Innovations | Kredity | 4 |
| Garant předmětu | RNDr. Ondřej Jakl, CSc. | Garant verze předmětu | RNDr. Ondřej Jakl, CSc. |
| Úroveň studia | pregraduální nebo graduální | Povinnost | povinný |
| Ročník | 1 | Semestr | letní |
| | Jazyk výuky | čeština |
| Rok zavedení | 2016/2017 | Rok zrušení | |
| Určeno pro fakulty | USP | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Po absolvování předmětu bude student schopen aktivně využívat nové pojmy z oblasti paralelních algoritmů.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Kurz poskytne přehled o problematice tvorby paralelních aplikací, zahrnující modely paralelního zpracování v závislosti na cílové paralelní architektuře, metodologii tvorby paralelních aplikací, implementační techniky či hodnocení paralelních kódů. Látka bude demonstrována na konkrétních praktických algoritmech.
Povinná literatura:
1. Principles of Parallel Algorithm Design, http://www.parallel-algorithms-book.com/
2. Xavier, S. S. Iyengar, Introduction to Parallel Algorithms, John Wiley & Sons, 1998, pages: 365.
Doporučená literatura:
další vhodné zdroje z internetu.
Forma způsobu ověření studijních výsledků a další požadavky na studenta
E-learning
Další požadavky na studenta
Znalost algoritmizace a C/C++.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
1. Úvod do problematiky.
Paralelní zpracování a High Performance Computing (HPC). Paralelní versus distribuované zpracování. Paralelní architektury, klasifikace a důsledky na paralelní zpracování.
2. Uvedení do programování paralelních aplikací.
Programové modely: předávání zpráv, sdílení proměnných, datově paralelní přístup. Příklady nasazení, výhody a nevýhody. Přehled implementačních prostředí a programovacích nástrojů.
3. Model předávání zpráv.
Principy a charakteristiky modelu předávání zpráv. Druhy komunikace, základní pojmy. Implementační předpoklady. Systémy předávání zpráv jakožto realizace modelu. Message Passing Interface (MPI).
4. Metodologie tvorby paralelních aplikací.
Fosterova metodologie. Dekompozice datová, funkční. Komunikační analýza, perfektně paralelní úlohy. Aglomerace a granularita, mapovaní na procesory.
5. Analýza paralelních algoritmů.
Výkonnostní modely, metriky. Kvantifikace doby provádění paralelních kódů. Zrychlení, účinnost a cena. Superlineární zrychlení a jeho příčiny. Amdahlův a Gustafsonův zákon.
6. Analýza paralelních algoritmů (pokračování).
Škálovatelnost, pevná a proměnná velikost problému. Asymptotická analýza. Experimenty, benchmarking.
7. Perfektně paralelní výpočty
Ideální paralelizace. Metody Monte Carlo. Další příklady
8. Dekompozice a metoda „rozděl a panuj“
Dekompoziční strategie. Numerická integrace. Další příklady
9. Proudové zpracování (pipelining)
Princip proudového zpracování. Generování prvočísel. Další příklady
10. Synchronizované výpočty
Synchronizační konstrukty. Datově paralelní výpočty. Problém vedení tepla. Další příklady
11. Vyvažování zátěže a detekce ukončení
Centralizovaná a decentralizovaná schémata. Mapování pro vyvažování zátěže. Problém nejkratší cesty. Další příklady
12. Programování se sdílenou pamětí.
Model sdílených proměnných. Technické předpoklady. Vlákna a nízkoúrovňové synchronizační prostředky. Standard OpenMP. Automatická paralelizace.
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
Předmět neobsahuje žádné hodnocení.