Parallel (and Distributed) Algorithms (WS 2024/2025)

Lectures

Prof. Dr. Ulrich Meyer

Tue, 10:00 - 12:00, in SR 307
Thu, 10:00 - 12:00, in SR 307

Tutorials

Manuel Penschuck

Tue, 12:00 - 14:00, in SR 11

Language

The lecture is held in English. By mutual agreement, the primary language can be changed to German, too.

You can solve the assignments in German or in English.

Content

We shortly survey existing concepts of parallel computers (e.g., multicomputer clusters, shared-memory CPUs, and GPUs), and introduce theoretical abstractions of these machines. We start by analysing algorithms for multicomputers consisting of several independent compute nodes interconnected by a network. Based on the observation that practical algorithms for these machines typically seek to minimize communication costs, we discuss and quantify the impact of various network topologies. Subsequently, we develop and analyse distributed communication primitives and algorithms for classical problems, such as sorting.

We then switch to algorithms for multiprocessor architectures which are formally expressed by the PRAM model. This part emphasizes algorithms for linked lists and trees, search-, distribution-, and sorting problems and topics of graph theory. Throughout the lecture, we will analyze not only upper-bounds (leading to efficiency guarantees), but also consider lower-bounds: These include minimal costs for communication in certain topologies, the comparison of various PRAM variants, and the introduction of P-completeness to gain insight into the parallelizability of problems. 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.
  • J. JáJá: An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
  • R.M. Karp und V. Ramachandran, Parallel algorithms for shared memory machines, in J van Leeuven (Ed.): Handbook of Theoretical Computer Science A, Kapitel 17, pp. 869-941, ElsevierScience Publishers, 1990.
  • P-completeness: R. Greenlaw, H.J. Hoover und W.L. Ruzzo: Limits to Parallel Computation, Oxford University Press, 1995.

Materials

Lecture notes

Some resources which might be useful

Lectures

DateNotesTopics
15 Oct 2024VL 01Einführung, Oh-Notation, Pfade uÄ
17 Oct 2024VL 02Grapheigenschaften, Tournament Trees, Präfixsummen I
22 Oct 2024VL 03Prefix sums II
24 Oct 2024VL 04Meshes, OETS, 0-1 principle
31 Oct 2024VL 05ShearSort and intro to HyperCubes (only black board)
05 Nov 2024VL 06HyperCubes II + Simulation Tree Alg.
07 Nov 2024VL 07Simulation Gitter, Butterfly Networks
12 Nov 2024VL 08Routing I
14 Nov 2024VL 09Routing II
19 Nov 2024VL 10Derandomisierung Rounting / Anfang MPI
21 Nov 2024VL 11MPI
26 Nov 2024VL 12LogGP, collective MPI Comm. I
28 Nov 2024VL 13collective MPI Comm. II
03 Dec 2024VL 14Performance measures (Eff., Isoeff, Speedup)
05 Dec 2024VL 15PRam Intro
10 Dec 2024VL 16Simulation PRAM
12 Dec 2024  
17 Dec 2024  
19 Dec 2024  

Assignments

DownloadDueTopicsComments
Assignment 0130 Oct 24Prefix sums / Tournament Treessee registration infos!
Assignment 0204 Nov 24Meshes 
Assignment 0311 Nov 24Hypercubes 
Assignment 0418 Nov 24Simulation 
Assignment 0525 Nov 24MPImax.py oets.py
Assignment 0605 Dec 24Broadcast / LogGP 
Assignment 0709 Dec 24Speedup/Efficiency