XD36PAR | Paralelní systémy a algoritmy | Rozsah výuky: | 19+6 | ||
---|---|---|---|---|---|
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 |
Požadavky:
Bodové hodnocení za semestrální práci (odladění paralelního algoritmu na paralelním svazku), písemná a ústní zkouška.
Předmět je zahrnut do těchto studijních plánů:
|
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) |