Paralelní systémy a algoritmy

Předmět je náhradou za:

Paralelní systémy a algoritmy (36PAR)

Přednášející:

Pavel Tvrdík, Michal Šoch

Cvičící:

Pavel Tvrdík, Michal Šoch

Předmět zajišťuje:

katedra počítačů

Anotace:

Cílem předmětu je uvést studenty do umění navrhovat efektivní algoritmy pro paralelní počítače se sdílenou a s distribuovanou pamětí, kam budou zahrnuty jak masivně paralelní počítače s pravidelnou topologií tak svazky stanic s nepravidelnou topologií. Důraz bude kladen na analýzu složitosti, škálovatelnosti a izoefektivnosti algoritmů. Budou probrány paralelní algoritmy pro redukci, prefixový součet, řazení, lineární algebru, kombinatorické prohledávání. Významná část předmětu se bude zabývat teorii propojovacích sítí, jejich topologiemi a technologiemi a algoritmy pro směrování a pro kolektivní komunikační operace.

Požadavky:

https://service.felk.cvut.cz

Osnova přednášek:

1. Složitost a škálovatelnost paralelních algoritmů

2. Paralelní algoritmy pro prohledávání stavového prostoru

3. Paralelní architektury a modely

4. Propojovací sítě

5. Vnořování a simulace propojovacích sítí

6. Směrovací algoritmy, techniky přepínání a zablokování

7. Redukce, prefixový součet a technika Eulerovy cesty

8. Paralelní řazení

9. Permutační směrování

10. Algoritmy pro kolektivní komunikační operace I

11. Algoritmy pro kolektivní komunikační operace II

12. Paralelní algoritmy pro lineární algebru I

13. Paralelní algoritmy pro lineární algebru II

14. Teorie paralelní složitosti

Osnova cvičení:

1. Analýza složitosti jednoduchého paralelního algoritmu

2. Návrh cenově a časově optimálních PRAM algoritmů

3.-4. Návrh cenově a časově optimálních APRAM algoritmů

5. Výpočty základních charakteristik propojovacích sítí

6. Návrh algoritmů pro vnořování a výpočty parametrů vnoření

7. Příklady simulací sítí

8.-9. Izoefektivnost a škálovatelnost paralelního řazení

10.-11. Navrhování efektivních kolektivních komunikačních algoritmů

12.-13. Paralelní algoritmy pro lineární algebru

14. Zápočet

Cíle studia:

Studijní materiály:

1. P. Tvrdík: Paralelní systémy a algoritmy. Skripta ČVUT, Praha 2000

2. J.H. Reif: Synthesis of Parallel Algorithms. Morgan Kaufmann, USA, ISBN 1-5586-135-X

Poznámka:

Ekvivalent 36PAR pro studenty dobihajiciho magistra.

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ů:

• MVT01-Výpočetní technika - softwarové inženýrství- strukturované studium (povinný předmět)
• MVT02-Výpočetní technika - systémové programování- strukturované studium (povinný předmět)
• MVT03-Výpočetní technika - počítačová grafika- strukturované studium (povinný předmět)
• MVT04-Výpočetní technika - počítačové sítě a internet- strukturované studium (povinný předmět)
• MVT05-Výpočetní technika - projektování číslicových systémů- strukturované studium (povinný předmět)