Parallel Algorithms and Systems

During a review of study plans, the course MI-PDP.16 can be substituted for the course MI-PAR.2.

Garant předmětu:

Lecturer:

Tutor:

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:

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.

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: