Paralelní počítání

Přednášky:
- Úvod do problematiky paralelního programování. Konkurence, pseudoparalelismus, paralelismus. Procesy a vlákna. Rozšířené instrukční sady, SIMD instrukce.
- Sekvenční vs. paralelní programování. Typické problémy paralelního programování a jejich řešení: synchronizace a vzájemné vyloučení, uváznutí (definice, vlastnosti, podmínky, detekce, eliminace).
- Typy paralelních platforem. Systémy se sdílenou a distribuovanou pamětí. Datový a funkční paralelismus.
- Systémy se sdílenou pamětí. Model fork-join a rozhraní OpenMP. Paralelní konstrukce na různých úrovních abstrakce (promise, future, async, threadpooling, scheduling, load balancing).
- Systémy s distribuovanou pamětí. Modely message passing a bulk synchronous parallel. Posix fronty, sockety. Rozhraní MPI, základní MPI operace.
- Další možnosti v systémech s distribuovanou pamětí: modely bulk synchronous parallel a partitioned global address space.
- Lehký úvod do programování akcelerátorů a koprocesorů. Koncept offloadování výpočtů. Architektura GPGPU (organizace programu, paměti). Datový a funkční paralelismus na GPU. Prostředí CUDA a jazyk CUDA-C, podpora v dalších jazycích (OpenMP).
- 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í.
- 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.
- 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.
- 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. 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.
- Datové struktury a algoritmy pro paralelní vyhledávání. 2-3 strom, pipelining. Paralelní vyhledávání, vkládání, mazání.
- Paralelní algoritmy a datové struktury pro grafové úlohy. Průchody grafy, hledání nejkratších cest, konektivita, nezávislé komponenty, atd.

Cvičení:
- Ř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).
- Datový paralelismus nad velkými daty. Datová dekompozice, data paralelní přístup, vektorizace. Paralelní maticové operace a shlukování.
- Paralelní vyhledávání.
- Paralelní algoritmy pro grafové úlohy, grafy a nelinerání datové stuktury. Paralelní implementace iterativní verze algoritmu PageRank.