Das Tutorium beginnt zukünftig immer um 14:45 (s.t.).

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

Lectures

Prof. Dr. Ulrich Meyer

Tue, 16:00 - 18:00, in SR307
Wed, 12:00 - 14:00, in SR11

Tutorials

Manuel Penschuck Tue, 14:45 - 16:00, in SR11

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
118.10.22Notes-Grundlagen
219.10.22Notes-Binärbäume, Prefixproblem
325.10.22Notes-Prefixproblem rekursiv, Gitter, Odd-Even Transposition Sort
426.10.22Notes-0-1 Prinzip und Beweis für Odd-Even Transposition Sort, Shearsort
501.11.22Notes-Shearsort Korrektheit, Hypercube I
602.11.22Notes-Hypercube II, Simulation von Topologien
708.11.22Notes-Simulation von Bäumen und Gittern
809.11.22Notes-Routing I
915.11.22Notes-Routing II, Intro MPI
1016.11.22Notes-LogGP
1122.11.22Notes-MPI Broadcast (Binomial Bäume)
1223.11.22Notes-Broadcast von langen Nachrichten; Seq vs. Par (Speed-Up, Effizienz)
1329.11.22Notes-Brent’s Theorem, Isoefficency
1430.11.22Notes-PRam, Nick’s Class, Simulation
1506.12.22Notes-PRam Simulation, Zero Counting
1607.12.22Notes-Stärken von PRam Klassen (Suchen, OR, Simulation)
1713.12.22Notes-Pointer Jumping
1814.12.22Notes-List Ranking
1920.12.22Notes-Euler Touren
2010.01.23Notes-Anwedungen von Euler Touren, Arithmetische Auswertung
2111.01.23Notes-Symmetry Breaking
2217.01.23Notes-Symmetry Breaking I, Paralleles Mischen
2318.01.23Notes-Paralleles Mischen II, External Memory
2431.01.23Notes-External Memory II
2501.02.23Notes-External Memory III, EM <-> PRAM, Matrizen
2607.02.23Notes Single-Matrix-Matrix-Produkt
  Notes Single-Rekonfigurierbare Netze: Parität
2708.02.23Notes-Rekonfigurierbare Netze: Sortieren

Assignments

DownloadDueTopicsComments
Assignment 131.10.2022 10:00Prefixproblems-
Assignment 207.11.2022 10:00Meshes, Bisection-
Assignment 314.11.2022 10:00Hypercubes, Hypercubes, and Hypercubes ;) Sketches-
Assignment 421.11.2022 10:00Routing-
Assignment 528.11.2022 10:00MPI & LogGP-
Assignment 605.12.2022 10:00Speedup, Iso-Efficiency, Nick’s Class-
Assignment 712.12.2022 10:00Basic PRam Algorithms-
Assignment 819.12.2022 10:00Parallel Searching, Pointer Jumping-
Assignment 916.01.2023 10:00Euler Tours-
Assignment 1030.01.2023 10:00Integer Sort, Coloring-