9600-1006/01 – Paralelní algoritmy (PAL)

Garantující katedraIT4InnovationsKredity4
Garant předmětuRNDr. Ondřej Jakl, CSc.Garant verze předmětuRNDr. Ondřej Jakl, CSc.
Úroveň studiapregraduální nebo graduálníPovinnostpovinný
Ročník1Semestrletní
Jazyk výukyčeština
Rok zavedení2016/2017Rok zrušení
Určeno pro fakultyUSPUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
JAK58 RNDr. Ondřej Jakl, CSc.
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

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.

Způsob průběžné kontroly znalostí během semestru

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

Prezenční forma (platnost od: 2016/2017 letní semestr, platnost do: 2017/2018 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (100) 51
        Zápočet Zápočet 45  20
        Zkouška Zkouška 55  25
Rozsah povinné účasti: Aktivní účast

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramOborSpec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2018/2019 (N2658) Výpočetní vědy (2612T078) Výpočetní vědy P čeština Ostrava 1 povinný stu. plán
2017/2018 (N2658) Výpočetní vědy (2612T078) Výpočetní vědy P čeština Ostrava 1 povinný stu. plán
2016/2017 (N2658) Výpočetní vědy (2612T078) Výpočetní vědy P čeština Ostrava 1 povinný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku