Parallel Algorithms and Systems

Lecturer:

Pavel Tvrdík (gar.)

Tutor:

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

Supervisor:

Department of Computer Systems

Synopsis:

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.

Requirements:

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

Syllabus of lectures:

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.

Syllabus of tutorials:

Study Objective:

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.

Study materials:

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.

Note:

Further information:

No time-table has been prepared for this course

The course is a part of the following study plans:

• Branch Software Engineering, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Master Branch Web Engineering - Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Computer Security, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Design of Digital Systems, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Computer Systems and Networks, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Branch System Programming, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Branch System Programming, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Knowledge Engineering, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Branch Web and Software Engineering, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)
• Master Informatics, Version for Students who Enrolled in 2010, Presented in Czech (compulsory course in the program)