Tue, 10:00 - 12:00, in SR 307
Thu, 10:00 - 12:00, in SR 307
Tue, 12:00 - 14:00, in SR 11
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.
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
Date | Notes | Topics |
---|---|---|
15 Oct 2024 | VL 01 | Einführung, Oh-Notation, Pfade uÄ |
17 Oct 2024 | VL 02 | Grapheigenschaften, Tournament Trees, Präfixsummen I |
22 Oct 2024 | VL 03 | Prefix sums II |
24 Oct 2024 | VL 04 | Meshes, OETS, 0-1 principle |
31 Oct 2024 | VL 05 | ShearSort and intro to HyperCubes (only black board) |
05 Nov 2024 | VL 06 | HyperCubes II + Simulation Tree Alg. |
07 Nov 2024 | VL 07 | Simulation Gitter, Butterfly Networks |
12 Nov 2024 | VL 08 | Routing I |
14 Nov 2024 | VL 09 | Routing II |
19 Nov 2024 | VL 10 | Derandomisierung Rounting / Anfang MPI |
21 Nov 2024 | VL 11 | MPI |
26 Nov 2024 | VL 12 | LogGP, collective MPI Comm. I |
28 Nov 2024 | VL 13 | collective MPI Comm. II |
03 Dec 2024 | VL 14 | Performance measures (Eff., Isoeff, Speedup) |
05 Dec 2024 | VL 15 | PRam Intro |
10 Dec 2024 | VL 16 | Simulation PRAM |
12 Dec 2024 | ||
17 Dec 2024 | ||
19 Dec 2024 |
Download | Due | Topics | Comments |
---|---|---|---|
Assignment 01 | 30 Oct 24 | Prefix sums / Tournament Trees | see registration infos! |
Assignment 02 | 04 Nov 24 | Meshes | |
Assignment 03 | 11 Nov 24 | Hypercubes | |
Assignment 04 | 18 Nov 24 | Simulation | |
Assignment 05 | 25 Nov 24 | MPI | max.py oets.py |
Assignment 06 | 05 Dec 24 | Broadcast / LogGP | |
Assignment 07 | 09 Dec 24 | Speedup/Efficiency |