| Distributed and Parallel Algorithms [2024 SoSe] | ||
|---|---|---|
| Code IDPA |
Name Distributed and Parallel Algorithms |
|
| CP 8 |
Duration one semester |
Offered every 3rd to 4th semester |
| Format 4 SWS lecture 2 SWS tutorial, homework assignments |
Workload 240h; thereof 90h lectures and tutorials, 15h exam preparations, 135h lecture wrap-up and homework |
Availability M.Sc. Angewandte Informatik M.Sc. Data and Computer Science M.Sc. Scientific Computing |
| Language English |
Lecturer(s) Christian Schulz |
Examination scheme |
| Learning objectives | Students understand fundamental theoretical and practical concepts of advanced parallel algorithms and data structures, get to know established methods and algorithms, are familiar with issues of efficient implementations, are able to identify/formulate algorithmic problems in/for different application areas where parallel or distributed algorithms are used, are able to analyse new distributed and parallel algorithms as well as analysing their running time, and select appropriate algorithms for parallel and distributed applications – students are able to apply parallel and distributed algorithms and data structures to real-world problems, and can objectively assess the quality of the results. | |
| Learning content | Introduction to distributed and parallel algorithms, PRAM model, design and analysis of parallel and distributed algorithms, isoefficiency, UMA vs. NUMA, memory consistency for shared-memory, communication models (with and without network, fully interconnected with half duplex or full duplex, BSP), critical path lengths, parallel associative operations, reduction operations, matrix multiplication, broadcast operations, MPI basic toolbox, ranking, parallel sorting (multiway merge, quick sort, sample sort), prefix sums, all-to-all communication, map-reduce, list ranking, parallel graph algorithms (minimum spanning trees, connected components, shortest paths, graph partitioning), process mapping, communication-free parallel graph generation, parallel sampling algorithms. | |
| Requirements for participation | recommended are: Einführung in die Praktische Informatik (IPI), Programmierkurs (IPK), Algorithmen und Datenstrukturen (IAD), Lineare Algebra 1 | |
| Requirements for the assignment of credits and final grade | The module is completed with a graded oral examination. The final grade of the module is determined by the grade of the examination. The requirements for the assignment of credits follows the regulations in section modalities for examinations. | |
| Useful literature | - Sanders, Mehlhorn, Dietzfelbringer, Dementiev. Sequential and Parallel Algorithms and Data Structures. 2019. - Kumar, Grama, Gupta, Karypis. Introduction to Parallel Computing. Design and Analysis of Algorithms. 1994 - Leighton. Introduction to Parallel Algorithms and Architectures. 1992 - Jaja. An Introduction to Parallel Algorithms. 1992 |
|