Aufgabe 7.3 wird auf das nächste Blatt verschoben.
Tue, 12:00 - 14:00, in SR11
Wed, 12:00 - 14:00, in SR11
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
|1||17 Oct 2023||Lecture 1||-||Intro, O-Notation|
|2||18 Oct 2023||Lecture 2||-||Graph Basics|
|3||24 Oct 2023||Lecture 3||-||Prefix problems|
|4||25 Oct 2023||Lecture 4||-||Prefix problems continued, Meshes|
|5||31 Oct 2023||Lecture 5||-||Odd-Even Transposition Sort, 0-1 Principle|
|6||01 Nov 2023||Lecture 6||-||OETS continued, Shearsort|
|7||07 Nov 2023||Lecture 7||-||Hypercubes|
|8||08 Nov 2023||Lecture 8||-||Simulation of Tree and Mesh Algs on Hypercubes|
|9||14 Nov 2023||Lecture 9||-||Butterfly Networks, Hypercube Routing|
|10||15 Nov 2023||Lecture 10||-||Analysis Randomized Hypercube Routing|
|11||21 Nov 2023||Lecture 11||-||2d Mesh Routing|
|12||22 Nov 2023||Lecture 12||-||Message Passing Interface (MPI)|
|13||28 Nov 2023||Lecture 13||-||LogGL Model|
|14||29 Nov 2023||Lecture 14||-||Implementations of collective MPI routines|
|15||05 Dec 2023||Lecture 15||-||Arbeit, Speedup, etc / PRam Modell|
|16||06 Dec 2023||Lecture 16||-||Sim PRAM <-> DMM, Stärken von PRam Varianten I|
|Assignment 1||31. Oct 10:00||Prefix problems||Manuel Penschuck||-|
|Assignment 2||07. Nov 10:00||Meshes||Manuel Penschuck||-|
|Assignment 3||14. Nov 10:00||HyperCube + Sim||Manuel Penschuck||-|
|Assignment 4||21. Nov 10:00||Routing Simulation||Manuel Penschuck||-|
|Assignment 5||28. Nov 10:00||MPI||Manuel Penschuck||-|
|Assignment 6||05. Dec 10:00||LogGP, Speedup||Alexander Leonhardt||-|
|Assignment 7||12. Dec 10:00||First steps with PRAM||Manuel Penschuck||Aufgabe 7.3 wird auf das nächste Blatt verschoben.|