Advanced Parallel Algorithms

Lecturer:

Pavel Tvrdík (gar.)

Tutor:

Pavel Tvrdík (gar.)

Supervisor:

Department of Computer Systems

Synopsis:

The students learn complex parallel algorithms and techniques to assess their correctness efficiency and optimality.

Requirements:

MIE-PAR

Syllabus of lectures:

1. PRAM algorithms for generalized prefix sum on arrays and their applications.

2. PRAM deterministic algorithms for prefix computations on lists.

3. PRAM algorithms for tree contraction and expression evaluation.

4. PRAM deterministic algorithms for computation of connected graph components.

5. PRAM randomized algorithms for computation of connected graph components.

6. PRAM deterministic optimal sorting.

7. Optimal ordering on meshes.

8. Parallel algorithms for computational geometry.

9. Parallel algebraic algorithms.

10. Parallel complexity, P and NC complexity classes..

Syllabus of tutorials:

Study Objective:

To explain the advanced techniques that are extensively used for designing fundamental parallel efficient algorithms for solving problems. These techniques go beyond the usual paradigm of data parallelism combined with reductions and prefix sums. Besides explanations of the ideas behind these nontrivial techniques, students learn sophisticated procedures for complexity, efficiency, and optimality analysis of these algorithms. The algorithms are PRAM - or mesh-based.

Study materials:

J. H. Reif, ed. Synthesis of parallel algorithms, Morgan Kaufmann Publ., 1993, ISBN 1-55860-135-X

J. Ja'Ja'. An introduction to parallel algorithms. Addison-Wesley. 1992.

Note:

Time-table for winter semester 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

Time-table is not available yet

The course is a part of the following study plans:

• Informatics (VO)