Advanced Multiprocessor Programming (184.726) - Summersemester 2021

Lecturers

Plan

Lecture with practical project part (VU). This semester in unfortunately again in online-mode, with weekly (streamed) lectures.

Overview

Synchronization problems, operations and primitives, atomic operations, consensus, impossibility and universality results, locks, lock- and wait-free data structures (lists, stacks, queues, hashtables, search structures, ...), memory models, work-stealing, transactional memory. Practical implementation project in C++.

Lectures, material

  1. Monday, 8.3.2021: Vorbesprechung. Intro, Mutual Exclusion problem and solutions
  2. Monday, 15.3.2021: Constructions of atomic registers, register snapshot
  3. Monday, 22.3.2021: Relative power of synchronization operations, correctness conditions
  4. Monday, 29.3.2021: No lecture (Easter holidays)
  5. Monday, 5.04.2021: No lecture (Easter holidays)
  6. Monday, 12.4.2021: Relative power of synchronization operations
  7. Monday, 19.4.2021: Projects (description). Relative power of synchronization operations (continue)
  8. Monday, 26.4.2021: Projects (selection). Relative power of synchronization operations (finish). Practical lock implementations.
  9. Monday, 3.5.2021: Practical lock implementations (con't and complete). Data structures (I): List-based sets. Data structures (II): Queues and stacks
  10. Monday, 10.5.2021: Data structures (III): Skiplist
  11. Monday, 17.5.2021: Memory consistency models. Here is a note on memory consistency models.
  12. Monday, 24.5.2021: No lecture (Whitsun holiday)
  13. Monday, 31.5.2021: Memory consistency models, memory reclamation (brief intro) (continued).
  14. Monday, 7.6.2021: Data structures (IV): Hash tables
  15. Monday, 14.6.2021: Work-stealing theory
  16. Monday, 21.6: TBA, Project hand-in

Exercises

Exercises at home, with online discussion and feedback.
The exercises are to be done individually and should be handed in electronically as a .pdf-file by TUWEL upload.

On the exercise days all must be present (attend online-meeting), and be prepared to discuss solutions at the blackboard.


Projects

Project topics, projects can be done in groups of two, group topic presentation early June 2021, hand-in deadline (TUWEL) Monday 21.6.2021
The programming project is mandatory, hand-in deadline Monday 21.6.2021, see TUWEL. Benchmarking will have to be done on the system provided for this lecture (Nebula), see TUWEL for instructions and use.

Special exercise (mandatory, deadline 19.4): Getting access to the systems (key upload)

Resources

Standards

C++11, C11, CilkPlus, TBB, OpenMP, Go

Literature