Přednášky:
1. Úvod do problematiky paralelního programování. Konkurence, pseudoparalelismus, paralelismus. 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í. Typické problémy a jejich řešení. Synchronizace a vyloučení, uváznutí (definice, vlastnosti, podmínky, detekce, eliminace).
3. Rozdělení paralelních platforem. Systémy se sdílenou a distribuovanou pamětí. Data paralelní a task paralelní úlohy.
4. Programování systémů se sdílenou pamětí. Vlákna v jazycích Java, C#, C++11, Python. Model fork-join a rozhraní OpenMP.
5. Programování systémů s distribuovanou pamětí. Komunikace pomocí zasílání zpráv. Posix fronty, sockety. Rozhraní MPI, základní MPI operace.
6. Další možnosti v systémech s distribuovanu pamětí: modely bulk synchronous parallel a partitioned global address space.
7. Úvod do programování akcelerátorů a koprocesorů. Koncept offloadování výpočtů. Architektura GPGPU (organizace programu, paměti). Datový paralelismus na GPU. Prostředí CUDA a jazyk CUDA-C, OpenACC.
8. 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í.
9. 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.
10. 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.
11. 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.
12. 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.
13. Datové struktury a algoritmy pro paralelní vyhledávání. 2-3 strom, pipelining. Paralelní vyhledávání, vkládání, mazání.
14. Paralelní algoritmy a datové struktury pro grafové úlohy. Průchody grafy, hledání nejkratších cest, konektivita, nezávislé komponenty, atd.
Cvičení:
Na cvičení se řeší praktické úlohy, ilustrující probírané koncepty. Studenti budou postupně pracovat na následujících zadáních:
1. Ř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).
2. Datový paralelismus nad velkými daty. Datová dekompozice, data paralelní přístup, vektorizace. Paralelní maticové operaca a shlukování.
3. Zpracování obrazových dat, vliv lokálních závislostí na paralelní algoritmy (konvoluce). Seam carving.
4. Paralelní algoritmy pro grafové úlohy, grafy a nelinerání datové stuktury. Paralelní implementace iterativní verze algoritmu PageRank.
1. Úvod do problematiky paralelního programování. Konkurence, pseudoparalelismus, paralelismus. 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í. Typické problémy a jejich řešení. Synchronizace a vyloučení, uváznutí (definice, vlastnosti, podmínky, detekce, eliminace).
3. Rozdělení paralelních platforem. Systémy se sdílenou a distribuovanou pamětí. Data paralelní a task paralelní úlohy.
4. Programování systémů se sdílenou pamětí. Vlákna v jazycích Java, C#, C++11, Python. Model fork-join a rozhraní OpenMP.
5. Programování systémů s distribuovanou pamětí. Komunikace pomocí zasílání zpráv. Posix fronty, sockety. Rozhraní MPI, základní MPI operace.
6. Další možnosti v systémech s distribuovanu pamětí: modely bulk synchronous parallel a partitioned global address space.
7. Úvod do programování akcelerátorů a koprocesorů. Koncept offloadování výpočtů. Architektura GPGPU (organizace programu, paměti). Datový paralelismus na GPU. Prostředí CUDA a jazyk CUDA-C, OpenACC.
8. 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í.
9. 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.
10. 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.
11. 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.
12. 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.
13. Datové struktury a algoritmy pro paralelní vyhledávání. 2-3 strom, pipelining. Paralelní vyhledávání, vkládání, mazání.
14. Paralelní algoritmy a datové struktury pro grafové úlohy. Průchody grafy, hledání nejkratších cest, konektivita, nezávislé komponenty, atd.
Cvičení:
Na cvičení se řeší praktické úlohy, ilustrující probírané koncepty. Studenti budou postupně pracovat na následujících zadáních:
1. Ř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).
2. Datový paralelismus nad velkými daty. Datová dekompozice, data paralelní přístup, vektorizace. Paralelní maticové operaca a shlukování.
3. Zpracování obrazových dat, vliv lokálních závislostí na paralelní algoritmy (konvoluce). Seam carving.
4. Paralelní algoritmy pro grafové úlohy, grafy a nelinerání datové stuktury. Paralelní implementace iterativní verze algoritmu PageRank.