Lectures on

Parallel and Distributed Algorithms
Hartmut Klauck

Winter 2007/08

Dates:

Lectures: 4 SWS, Mo 16-18 c.t., Wed 12-14 c.t., SR 11

Tutorial: 2 SWS, Wed, 8-10 c.t., SR11, starting 24.10.

Announcement: The part of the lectures that belongs the computational science masters program ends on Dec.12. Examination dates can be arranges via email.

Content:

Distributed and shared memory: shared memory models, MPI and its communication functions, performance analysis,
communication patterns such as trees, meshes and hypercube architectures.
Parallel linear algebra: solving linear systems, finite difference methods, the fast Fourier transform.
Search and optimization: Monte Carlo methods, backtracking, branch & bound, alpha-beta pruning.
Load balancing and termination detection.
Parallel random access machines: algorithms for lists and graphs.
P-Completeness.

Requirements:

Successful participation in the tutorials (regular and active attendance, 60% of the maximal score has to be obtained in the exercises) is required to obtain a certificate for the course in the computer science curriculum. The master’s degree students can obtain 3 credit points by doing an oral exam about the first half of the course. For them the tutorial is optional

Lecture notes

Lectures:

Lectures 1-4
Lecture 5
Lectures 6-7
Lectures 8-11 and Gaussian Elimination
Lectures 12-14
Lectures 14-16
Lecture 17
Lecture 18
Lectures 19-20
Lectures 21-22
Lecture 23
Lecture 24
Lecture 25

Problem Sets:

Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 10

Literature:

A. Grama, A. Gupta, G. Karypis und V. Kumar, Introduction to Parallel Computing, second edition, Addison-Wesley 2003

M. J. Quinn, Parallel Computing in C with MPI and OpenMP, McGraw-Hill, 2004

Links:

---

1.3.2008,   Hartmut Klauck