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

Aufgabe 7.3 wird auf das nächste Blatt verschoben.

Lectures

Prof. Dr. Ulrich Meyer

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

Tutorials

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

Language

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.

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

LectureDateSlidesRecordingTopics
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

Assignments

DownloadDueTopicsTutorComments
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.