Paralelní algoritmy a systémy

Předmět nesmí být zapsán současně s:

Paralelní algoritmy a systémy (MI-PAR)

Předmět je náhradou za:

Paralelní algoritmy a systémy (MI-PAR)

Přednášející:

Pavel Tvrdík (gar.)

Cvičící:

Pavel Tvrdík (gar.), Ivan Šimeček, Michal Šoch

Předmět zajišťuje:

katedra počítačových systémů

Anotace:

Studenti se seznámí s metodami, které umožňují rozumět výkonnostním charakteristikám paralelních algoritmů, s důrazem na zrychlení, efektivnost a škálovatelnost. Mají pochopit, jaké teoretické i praktické aspekty má navrhování, provádění a analýza paralelních algoritmů a jak při této analýze složitosti zohlednit architekturu a technologické parametry paralelního či distribuovaného počítačového systému. Naučí se přenášet zkušenosti ze standardní algoritmizace na systémy s více procesory. Dílčí přínos předmětu je zvládnutí metod asymptoticky přesného řešení rovnic, které nejsou algebraicky přesně řešitelné a zvládnutí některých technik odhadu spodních mezí složitosti paralelních řešení problémů.

Požadavky:

Základy asymptotické aritmetiky, základní programovací techniky a datové struktury, sekvenční algoritmizace, základní teorie grafů.

Osnova přednášek:

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

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

3. Propojovací sítě paralelních počítačů.

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

5. Modely meziprocesorové komunikace a směrování.

6. Algoritmy pro kolektivní komunikaci.

7. Základní paralelní algoritmizace.

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

9. Paralelní algoritmy pro lineární algebru.

10. Paralelní algoritmy pro prohledávání kombinatorického stavového prostoru.

Osnova cvičení:

Cíle studia:

Cílem předmětu je poskytnout základní teoretickou průpravu paralelní algoritmizace, která studentovi umožní navrhovat a implementovat algoritmy pro paralelní systémy, počínaje multicore systémy a systémy na čipu, až po klastry, rozumět jejich chování a analyzovat výkonnostní charakteristiky.

Studijní materiály:

Tvrdík, P. ''Paralelní systémy a algoritmy''. Praha: ČVUT, 2000. ISBN 80-01-02267-6.

Duato, J., Yalamanchili, S., Ni, L. M. ''Interconnection Networks: An Engineering Approach''. IEEE, 1997. ISBN 0818678003.

Greenlaw, R., Hoover, J. H., Ruzzo, W. L. ''Limits to Parallel Computation: P-Completeness Theory''. Oxford University Press, 1995. ISBN 0195085914.

Jaja, J. ''An Introduction to Parallel Algorithms''. Addison-Wesley Professional, 1992. ISBN 0201548569.

Kumar, V., Grama, A., Gupta, A., Karpis, G. ''Introduction to Parallel Computing: Design and Analysis of Parallel Algorithms''. Benjamin-Cummings, 1994. ISBN 0805331700.

Miller, R., Boxer, L. ''Algorithms Sequential and Parallel: A Unified Approach''. Pearson Education, 1999. ISBN 0130863734.

Wilkinson, B., Allen, M. ''Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers''. Prentice Hall, 1998. ISBN 0136717101.

Poznámka:

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

Rozvrh není připraven

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

• Společný plán před přiřazením do oboru, verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Zaměření Informační systémy a management - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Zaměření Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Zaměření Webové inženýrství - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Znalostní inženýrství - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Počítačová bezpečnost - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Projektování číslicových systémů - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Počítačové systémy a sítě - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Zaměření Systémové programování - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 (povinný předmět programu)
• Společný plán před přiřazením do oboru, verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Počítačová bezpečnost - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Projektování číslicových systémů - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Zaměření Systémové programování - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Zaměření Teoretická informatika - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Zaměření Informační systémy a management - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Zaměření Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Zaměření Webové inženýrství - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Znalostní inženýrství - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)
• Počítačové systémy a sítě - verze pro ty, kteří se zapsali v roce 2012 (povinný předmět programu)