Paralelní systémy a algoritmy

Předmět je náhradou za:

Paralelní systémy a algoritmy (XD36PAR)

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra počítačů

Anotace:

Obsahem předmětu jsou problémy architektury 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 výpočetní geometrii 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. Vvnořování PSP a emulace výpočtů na PSP

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

8. Algoritmy pro kolektivní komunikaci

9. Fundamentální NC algoritmy

10. Paralelní třídění

11. Algoritmy pro výpočetní geometrii

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

1. Úvod

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

3. Škálovatelnost a isoefektivnost algoritmů

4. NC a P-úplné algoritmy

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 fundamentalní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

Laboratorní cvičení: 2hod.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

Cíle studia:

Studijní materiály:

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

Poznámka:

Předmět má stejnou náplň jako předmět 36PAR.

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