Lectures and tutorials will take place electronically.
Tue, 10:00 - 12:00
Thu, 10:00 - 12:00
Please contact us via firstname.lastname@example.org
Thu, 12.15 - 13.45
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||03.11.20||Notes||Recording||Introduction and Definitions|
|2||05.11.20||Notes||Recording||Multicomputer/Multiprocessors, Graph properties|
|4||12.11.20||Notes||Recording||Meshes, OETS, 0/1 principle|
|5||17.11.20||Notes||Recording||Correctness of OETS, Shearsort|
|6||19.11.20||Notes||Recording||Hypercubes, Simulations on Hypercubes|
|7||24.11.20||Notes||Recording||Normal tree algorithms, Simulations on Hypercubes II|
|8||26.11.20||Notes||Recording||Butterfly network, Routing on Hypercubes I|
|9||01.12.20||Notes||Recording||Routing on Hypercubes II and 2D meshes|
|10||03.12.20||Notes||Recording||Derandomization of 2D routing, MPI introduction|
|11||08.12.20||Notes||Recording||MPI communication primitives, LogGP introduction|
|12||10.12.20||Notes||Recording||Analysis of MPI primitives|
|13||15.12.20||Notes||Recording||Parallel vs Sequential, Scaling Down, PRam I|
|14||17.12.20||Notes||Recording||PRam II, Nick’s class, Simulation PRam|
|15||12.01.21||Notes||Recording||Comparing PRams I|
|15||12.01.21||Notes||Comparing PRams I, List Ranking I|
|Assignment 1||10.11.||17.11 at 10 AM||update 1 pm 10.11, removed exercise 1.3|
|Assignment 2||17.11.||24.11 at 10 AM||-|
|Assignment 3||24.11.||01.12 at 10 AM||-|
|Assignment 4||04.12.||15.12 at 10 AM||-|
|Assignment 5||15.12.||12.01 at 10 AM||update 2 pm 17.12, changed due time|
|Assignment 6||12.01.||19.01 at 10 AM||-|