Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Parallel Algorithms and Systems

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
MIE-PAR.2 ZK 6 2P+3C
Předmět je náhradou za:
Parallel and Distributed Programming (MIE-PDP.16)
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra počítačových systémů
Anotace:

Students are introduced to methods that enable them to understand performance characteristics of parallel algorithms, with emphasis on speedup, efficiency, and scalability. Students will understand theoretical and practical aspects of designing, executing, and analyzing parallel algorithms. They learn to take into account the architectural and technical parameters of the parallel or distributed computer system in question. They learn to apply standard knowledge of algorithms to multiprocessor systems. As an implicit outcome, students learn the methods of asymptotically correct solving of equations that cannot be solved with algebraic means, as well as certain techniques to estimate lower bounds of parallel algorithm complexity.

Požadavky:

Competence in asymptotic arithmetics, basic sequential algorithmics techniques, basic graph theory.

Osnova přednášek:

1. Performance characteristics of parallel computations.

2. Models of parallel systems with shared memory.

3. Interconnection networks of parallel computers.

4. Embeddings and simulations of interconnection networks.

5. Models for interprocessor communication and routing.

6. Collective communication algorithms.

7. Fundamental parallel algorithmics.

8. Parallel sorting algorithms.

9. Parallel algorithms for linear algebra.

10. Parallel combinatorial space search.

Osnova cvičení:

1. Performance characteristics of parallel computations.

2. Models of parallel systems with shared memory.

3. Interconnection networks of parallel computers.

4. Embeddings and simulations of interconnection networks.

5. Models for interprocessor communication and routing.

6. Collective communication algorithms.

7. Fundamental parallel algorithmics.

8. Parallel sorting algorithms.

9. Parallel algorithms for linear algebra.

10. Parallel combinatorial space search.

Cíle studia:

The aim of the course is to provide students with the theoretical background for parallel algorithmization that lets them design and implement algorithms for parallel systems, from multicore systems and systems-on-chip to clusters, understand their behavior and estimate performance characteristics.

Studijní materiály:

1. Tvrdík, P. ''Parallel algorithms and computing''. Praha: ČVUT, 2009. ISBN 80-01-02267-6.

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

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

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

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

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

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

Poznámka:

Opozdilcům: student, kterému chybí PAR, si zapíše PDP a po úspěšném absolvování se podrobí rozdilové zkoušce.

Opakující student s uznatelnou zkouskou z PAR ma uznanou zkousku pro PDP.

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ů:
Platnost dat k 23. 2. 2020
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet2823106.html