Advanced Multiprocessor Programming (184.726) - Summersemester 2020

Lecturers

Plan

Lecture with practical project part (VU).

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, 2.3.2020: Vorbesprechung. Intro, Mutual Exclusion problem and solutions
  2. Monday, 9.3.2020: Mutual Exclusion problem and solutions
  3. Monday, 16.3.2020: Constructions of atomic registers, register snapshot
  4. Monday, 23.3.2020: Relative power of synchronization operations, correctness conditions
  5. Thursday, 26.3.2020: Exercises batch 1
  6. Monday, 30.3.2020: Relative power of synchronization operations
  7. Thursday, 2.4.2020: Exercises batch 2
  8. Monday, 6.4.2020: No lecture (Easter holidays)
  9. Monday, 13.04.2020: No lecture (Easter holidays)
  10. Monday, 20.4.2020: Projects (description). Practical lock implementations
  11. Monday, 27.4.2020: Projects (selection). Data structures (I): List-based sets
  12. Monday, 4.5.2020: Data structures (II): Queues and stacks
  13. Monday, 11.5.2020: Data structures (III): Skiplist
  14. Monday, 18.5.2020: Memory consistency models. Here is a note on memory consistency models.
  15. Monday, 25.5.2020: Memory consistency models, memory reclamation (brief intro) (continued).
  16. Monday, 1.6.2020: No lecture (Whitsun holiday)
  17. Thursday, 4.6.2020: Project (status presentations): 10 minutes per group, all present (later that day: Gödel lecture);
  18. Monday, 8.6.2020: Data structures (IV): Hash tables
  19. Monday, 15.6.2020: Work-stealing theory
  20. Monday, 29.6: Project hand-in

Exercises

  1. Thursday, 26.3.2020, 8:00-11:00: EI 6, Gusshausstrasse 25-29. Hand-in now 2.4.
  2. Thursday, 2.4.2020, 8:00-11:00: EI 6, Gusshausstrasse 25-29. Hand-in now 9.4

The exercises are to be done individually and should be handed in electronically as a .pdf-file by TUWEL upload.

On the exercise days (Thursdays) all must be present, and be prepared to discuss solutions at the blackboard.

Note that, due to the large number of participants, the exercises will be split over two slots (8:00-9:30, and 9:30-11:00).

Projects

Project topics, projects can be done in groups of two, group topic presentation on Thursday 6.6.2020, hand-in deadline (TUWEL) Monday 29.6.2020
The programming project is mandatory, hand-in deadline Monday 29.6.2020, 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): Getting access to the systems (key upload)

Resources

Standards

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

Literature