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

Die Vorlesung am 24.01.2024 entfällt. Das Tutorium findet wie letzte Woche online statt.


Prof. Dr. Ulrich Meyer

Tue, 12:00 - 14:00, in SR11
Wed, 12:00 - 14:00, in SR11


Manuel Penschuck
Alexander Leonhardt

Wed, 14:30 - 16:00, in H3 (Hörsaaltrakt Bockenheim, Gräfstraße 50-54)


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

You can solve the assignments in German or in English.


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.


Lecture notes

Some resources which might be useful


117 Oct 2023Lecture 1-Intro, O-Notation
218 Oct 2023Lecture 2-Graph Basics
324 Oct 2023Lecture 3-Prefix problems
425 Oct 2023Lecture 4-Prefix problems continued, Meshes
531 Oct 2023Lecture 5-Odd-Even Transposition Sort, 0-1 Principle
601 Nov 2023Lecture 6-OETS continued, Shearsort
707 Nov 2023Lecture 7-Hypercubes
808 Nov 2023Lecture 8-Simulation of Tree and Mesh Algs on Hypercubes
914 Nov 2023Lecture 9-Butterfly Networks, Hypercube Routing
1015 Nov 2023Lecture 10-Analysis Randomized Hypercube Routing
1121 Nov 2023Lecture 11-2d Mesh Routing
1222 Nov 2023Lecture 12-Message Passing Interface (MPI)
1328 Nov 2023Lecture 13-LogGL Model
1429 Nov 2023Lecture 14-Implementations of collective MPI routines
1505 Dec 2023Lecture 15-Arbeit, Speedup, etc / PRam Modell
1606 Dec 2023Lecture 16-Sim PRAM <-> DMM, Stärken von PRam Varianten I
1712 Dec 2023Lecture 17-Stärken von PRam Varianten II, Pointer Jumping
1813 Dec 2023Lecture 18-Basic List-Ranking Approaches
1919 Dec 2023Lecture 19-Improved List-Ranking, Eulertours
2020 Dec 2023Lecture 20-Applications of Eulertours, Expression Tree Evaluation I
2109 Jan 2024Lecture 21-Expression Tree Evaluation II, Symmetry Breaking I
2210 Jan 2024Lecture 22-Symmetry Breaking II
2316 Jan 2024Lecture 23-Fast Merging on CREW
2417 Jan 2024Lecture 24-Connections between Parallelism and Memory Hierarchies I
2523 Jan 2024Lecture 25-Connections between Parallelism and Memory Hierarchies II
2630 Jan 2024Lecture 26-Connections between Parallelism and Memory Hierarchies III
2731 Jan 2024Lecture 27-Matrix Tricks
2802 Feb 2024Lecture 28-Reconfigurable Networks


Assignment 131. Oct 10:00Prefix problemsManuel Penschuck-
Assignment 207. Nov 10:00MeshesManuel Penschuck-
Assignment 314. Nov 10:00HyperCube + SimManuel Penschuck-
Assignment 421. Nov 10:00Routing SimulationManuel Penschuck-
Assignment 528. Nov 10:00MPIManuel Penschuck-
Assignment 605. Dec 10:00LogGP, SpeedupAlexander Leonhardt-
Assignment 712. Dec 10:00First steps with PRAMManuel PenschuckAufgabe 7.3 wird auf das nächste Blatt verschoben.
Assignment 819. Dec 10:00PRAM in-depthAlexander Leonhardt-
Assignment 916. Jan 10:00Euler Tour, ISAlexander LeonhardtAddendum
Assignment 1023. Jan 10:00Sorting, ColoringAlexander Leonhardt-