Paralelní systémy a algoritmy

Předmět je náhradou za:

Paralelní systémy a algoritmy (D36PAR)

Přednášející:

Pavel Tvrdík, Neurčen (gar.), 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, izoefektivnosti a škálovatelnosti algoritmů. Budou probrány paralelní algoritmy pro prefixový součet, řazení, lineární algebru, kombinarorické prohledávání a teorii grafů.

Požadavky:

Bodové hodnocení za semestrální práci (odladění paralelního algoritmu na paralelním svazku), písemná a ústní zkouška.

Osnova přednášek:

1. Výkonnostní měřítka složitosti paralelních algoritmů

2. Modely PRAM a APRAM

3. Technologie a topologie propojovacích sítí

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

5. Prefixový součet a technika Eulerovy cesty

6. Paralelní řazení

7. Směrovací algoritmy a permutační směrování

8. Kolektivní komunikační algoritmy

9. Paralelní algoritmy pro lineární algebru - husté matice

10. Paralelní algoritmy pro lineární algebru - řídké matice

11. Paralelní algoritmy pro kombinatorické prohledávání

12. Paralelní grafové algoritmy

13. Výpočty na rychlých svazcích stanic

14. Metapočítače a výpočty na Internetu

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. Návrh cenově a časově optimálních APRAM algoritmů

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

5. Návrh algoritmů pro vnořování

6. Simulace sítí

7. Izoefektivnost a škálovatelnost paralelního řazení

8. Důkaz korektnosti algoritmů pro permutační směrování

9. Navrhování efektivních kolektivních komunikačních algoritmů

10. Izoefektivnost a škálovatelnost paralelních algoritmů pro lineární algebru

11. Izoefektivnost a škálovatelnost paralelních algoritmů pro kombinatorické problémy

12. Izoefektivnost a škálovatelnost paralelních grafových algoritmů

13. Případová studie rychlého svazku stanic

14. Případová studie metapočítače

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:

Rozvrh na zimní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po	místnost Neurčen . 17:00–18:45 (přednášková par. 1)
Út
St
Čt
Pá

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

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