Pokročilé paralelní algoritmy

Přednášející:

Pavel Tvrdík (gar.)

Cvičící:

Pavel Tvrdík (gar.)

Předmět zajišťuje:

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

Anotace:

Studenti se naučí složité paralelní algoritmy a techniky pro vyhodnocování jejich správnosti, efektivity a optimality.

Požadavky:

MI-PAR

Osnova přednášek:

1. PRAM algoritmy pro zobecněný prefixový součet nad poli a jejich aplikace.

2. PRAM deterministické algoritmy pro prefixové výpočty nad seznamy.

3. PRAM algoritmy pro kontrakci stromů a vyhodnocování výrazů.

4. PRAM deterministické algoritmy pro výpočet souvislých komponent grafu.

5. PRAM randomizované algoritmy pro výpočet souvislých komponent grafu.

6. PRAM deterministické optimální řazení.

7. Optimální řazení na mřížkách.

8. Paralelní algoritmy pro výpočetní geometrii.

9. Paralelní algebraické algoritmy.

10. Paralelní složitost a třídy složitosti P a NC.

Osnova cvičení:

Cíle studia:

Seznámit s pokročilými technikami, na kterých jsou založeny základní paralelní algoritmy a které tudíž dovolují efektivní paralelizaci řešení problémů. Tyto techniky jdou nad obvyklý rámec datového paralelismu kombinovaného s redukcemi či prefixovými výpočty. Kromě vysvětlení myšlenek těchto netriviálních algoritmů se studenti seznámí s propracovanými postupy pro analýzu těchto časově a cenově efektivních nebo optimálních paralelních algoritmů na PRAM modelech a mřížkách.

Studijní materiály:

J. H. Reif, ed. Synthesis of Parallel Algorithms, Morgan Kaufmann Publ., 1993, ISBN 1-55860-135-X.

J. Ja'Ja'. An Introduction to Parallel Algorithms. Addison-Wesley. 1992.

Poznámka:

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Informatika (VO)