Parallel (and Distributed) Algorithms (WS 2020/2021)

Lectures

Lectures and tutorials will take place electronically.

  • Lectures will begin on 3.11. (Tuesday) at 10 ct.
  • Lectures and tutorials will be held live via screen sharing at the below mentioned times.
  • Access links to the streams will be made avaialble in Moodle (HRZ-account necessary).

Prof. Dr. Ulrich Meyer

Tue, 10:00 - 12:00
Thu, 10:00 - 12:00

Tutorials

Manuel Penschuck

Hung Tran

Please contact us via pal20@ae.cs.uni-frankfurt.de

Thu, 12.15 - 13.45

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

LectureDateNotesRecordingTopics
103.11.20NotesRecordingIntroduction and Definitions
205.11.20NotesRecordingMulticomputer/Multiprocessors, Graph properties
310.11.20NotesRecordingPrefix Problems
412.11.20NotesRecordingMeshes, OETS, 0/1 principle
517.11.20NotesRecordingCorrectness of OETS, Shearsort
619.11.20NotesRecordingHypercubes, Simulations on Hypercubes
724.11.20NotesRecordingNormal tree algorithms, Simulations on Hypercubes II
826.11.20NotesRecordingButterfly network, Routing on Hypercubes I
901.12.20NotesRecordingRouting on Hypercubes II and 2D meshes
1003.12.20NotesRecordingDerandomization of 2D routing, MPI introduction
1108.12.20NotesRecordingMPI communication primitives, LogGP introduction
1210.12.20NotesRecordingAnalysis of MPI primitives
1315.12.20NotesRecordingParallel vs Sequential, Scaling Down, PRam I
1417.12.20NotesRecordingPRam II, Nick’s class, Simulation PRam
1512.01.21NotesRecordingComparing PRams I
1614.01.21NotesRecordingComparing PRams II, List Ranking I
1719.01.21NotesRecordingList Ranking II, Euler Tours I
1821.01.21NotesRecordingEuler Tours and applications
1926.01.21NotesRecordingExpression trees and Symmetry Breaking I
2028.01.21NotesRecordingSymmetry Breaking II
2102.02.21NotesRecordingFast Merging I
2204.02.21NotesRecordingFast Merging II, External Memory I
2309.02.21NotesRecordingExternal Memory II – Simulation of PRam
2416.02.21NotesRecordingLinear Algebra
2518.02.21NotesRecordingReconfig. Meshes

Assignments

DownloadIssuedDueComments
Assignment 110.11.17.11 at 10 AMupdate 1 pm 10.11, removed exercise 1.3
Assignment 217.11.24.11 at 10 AM-
Assignment 324.11.01.12 at 10 AM-
Assignment 404.12.15.12 at 10 AM-
Assignment 515.12.12.01 at 10 AMupdate 2 pm 17.12, changed due time
Assignment 612.01.19.01 at 10 AM-
Assignment 719.01.26.01. at 10 AM-
Assignment 826.01.02.02. at 10 AM-
Assignment 902.02.09.02. at 10 AM-