Paralelní systémy a algoritmy

Prerekvizita:

Bezpečnost práce II VT (36BP2)

Předmět je náhradou za:

Paralelní systémy a algoritmy (X36PAR)

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

Anotace:

Obsahem předmětu jsou problémy architektur a efektivního využití paralelních výpočetních systémů. Cílem je vysvětlit základní problémy paralelizace algoritmů ve vztahu k architektuře paralelního systému. První teoretická část je věnována měření výkonnosti a teorii složitosti paralelních algoritmů a modelům počítačů se sdílenou pamětí. Druhá část se zabývá architekturami s distribuovanou pamětí, především problémy komunikace mezi výpočetními uzly propojenými komunikační sítí. Třetí část popisuje několik skupin důležitých paralelních algoritmů, především nejzákladnější algoritmy typu prefixový výpočet a paralelní algoritmy pro třídění a pro lineární algebru. Závěr je věnován prostředím a nástrojům pro paralelní programování.

Požadavky:

Osnova přednášek:

1. Architektury paralelních počítačů

2. Měřítka výkonnosti paralelních výpočtů

3. Modely paralelních systémů se sdílenou pamětí

4. Teorie paralelní složitosti

5. Propojovací sítě paralelních počítačů (PSP)

6. Vnořování PSP a emulace výpočtů na PSP

7. Komunikační algoritmy pro směrování

8. Algoritmy pro kolektivní komunikaci

9. Základní NC algoritmy

10. Paralelní třídící algoritmy

11. Paralelní třídící algoritmy

12. Paralelní algoritmy pro lineární algebru

13. Paralelní algoritmy pro lineární algebru

14. Systémové programové vybavení paralelních počítačů

Osnova cvičení:

Laboratoře: 2 hod týdně, 1.-2. Seznámení se s paralelním programovacím prostředím PVM, 3. Výběr semestrální úlohy, 4.-13. Řešení semestrální úlohy, 14. Odevzdání semestrální úlohy. Semináře: 1 hod týdně

1. Úvod

2. Výkonnostní měřítka paralelních výpočtů

3. Škálovatelnost a isoefektivnost algoritmů

4. NC a PRAM simulace

5. Topologické vlastnosti propojovacích sítí

6. Vnořovaní - případové studie

7. Simulace sítí - případové studie

8. Směrovací algoritmy a zablokování

9. Permutační směrování na hyperkubických sítích

10. Kolektivní komunikace na mřížkových sítích

11. Analýza složitosti základních NC algoritmů

12. Analýza složitosti paralelních třídících algoritmů

13. Analýza složitosti paralelních algoritmů nad maticemi

14. Analýza složitosti paralelních algoritmů pro řešení soustav rovnic

Cíle studia:

Studijní materiály:

[1] Tvrdík, P.: Parallel Systems and Algorithms. Skripta ČVUT, Praha 1997

Poznámka:

Rozsah výuky v kombinované formě studia: 21+6

Typ cvičení: s, c

Tento předmět je nabízen také v anglické verzi

Další informace:

Pro tento předmět se rozvrh nepřipravuje

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