Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
X36PAR Paralelní systémy a algoritmy Rozsah výuky:3+3
Přednášející (garant):Tvrdík P. Typ předmětu:Z Zakončení:Z,ZK
Zodpovědná katedra:336 Kreditů:7 Semestr:Z

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

Osnovy 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

Osnovy 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

Literatura Č:
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

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

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

Rozsah výuky v kombinované formě studia: 19+6
Typ cvičení: s, c
Předmět je nabízen také v anglické verzi.

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
MVT01 Výpočetní technika Z 1
MVT04 Výpočetní technika Z 1
MVT05 Výpočetní technika Z 1
MVT03 Výpočetní technika Z 1
MVT02 Výpočetní technika Z 1


Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)