Parallel Algorithms and Systems

Přednášející:

Pavel Tvrdík (gar.)

Cvičící:

Ivan Šimeček, Michal Šoch

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

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:

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:

Rozsah=prednasky+proseminare+cviceni2p+1r+1c, Prednasejici: prof. Ing. Pavel Tvrdík CSc.

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

• Computer Security, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Design of Digital Systems, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Computer Systems and Networks, Presented in English, for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• System Programming, in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Computer Science, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Information Systems and Management, in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Software Engineering, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Web Engineering, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Knowledge Engineering, Presented in English, Version for Students, who Enrolled in 2010 and 2011 (povinný předmět programu)
• Master Informatics, Presented in English - Version for Students who Enrolled in 2010 (povinný předmět programu)