Advanced Multiprocessor Programming (184.726) - Summersemester 2020
Lecturers
Plan
Lecture with practical project part (VU).- Lectures Mondays 9:05-11:00 (changed from Mondays 10:10 - 12:00), first 2.3.2020. Attendance mandatory, and generally recommended. Due to the Corona-situation, lectures are suspended until Easter. Reading hints via TISS.
- Additional slots for exercises, project matters, etc.: Some Thursdays, 8:00 - 11:00 (note: changed from 9:00). The deadlines for post exercise batches have been extended by one week.
- Lecture hall EI 1 (lectures) and EI 6 (exercises). Both lecture halls are in Gusshausstrasse 25-27.
- Vorbesprechung (and first lecture): 2.3.2020. All potential students should be present!
- Project hand-in: 29.6.2020.
-
Exam: First week of July, estimated (29.6-3.7.2020). - AMP course in TUWEL
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
- Monday, 2.3.2020: Vorbesprechung. Intro, Mutual Exclusion problem and solutions
- Monday, 9.3.2020: Mutual Exclusion problem and solutions
- Monday, 16.3.2020: Constructions of atomic registers, register snapshot
- Monday, 23.3.2020: Relative power of synchronization operations, correctness conditions
- Thursday, 26.3.2020: Exercises batch 1
- Monday, 30.3.2020: Relative power of synchronization operations
- Thursday, 2.4.2020: Exercises batch 2
Monday, 6.4.2020: No lecture (Easter holidays)Monday, 13.04.2020: No lecture (Easter holidays)- Monday, 20.4.2020: Projects (description). Practical lock implementations
- Monday, 27.4.2020: Projects (selection). Data structures (I): List-based sets
- Monday, 4.5.2020: Data structures (II): Queues and stacks
- Monday, 11.5.2020: Data structures (III): Skiplist
- Monday, 18.5.2020: Memory consistency models. Here is a note on memory consistency models.
- Monday, 25.5.2020: Memory consistency models, memory reclamation (brief intro) (continued).
Monday, 1.6.2020: No lecture (Whitsun holiday)- Thursday, 4.6.2020: Project (status presentations): 10 minutes per group, all present (later that day: Gödel lecture);
- Monday, 8.6.2020: Data structures (IV): Hash tables
- Monday, 15.6.2020: Work-stealing theory
- Monday, 29.6: Project hand-in
Exercises
- Thursday, 26.3.2020, 8:00-11:00: EI 6, Gusshausstrasse 25-29. Hand-in now 2.4.
- 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).
-
Except where noted, exercises are from the Herlihy/Shavit book.
- Batch 1 (HAND-IN: Before
26.3.20202.4.2020;Blackboard: 26.3.2020). 6, 7, 8, 9, 10, 11, 12, 13, 15, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 46. - Batch 2 (HAND-IN: Before
2.4.20209.4.2020;Blackboard: 2.4.2020). 21, 22, 23, 24, 27, 32, 52 (hint: see 58), 53, 54, 59, 65 (hint: see 52).
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.2020The 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, GoLiterature
- Maurice Herlihy, Nir Shavit: The Art of Multiprocessor Programming. Morgan Kaufmann, 2008. Revised 1st Edition, 2012.
Source book for the lectures, recommended! Classical results for synchronization operations, standard set of lock- and wait-free data structures. The lectures in part follow this book. - Gadi Taubenfeld: Synchronization Algorithms amd Concurrent Programming. Pearson/Prentice Hall, 2006.
More limited in scope, but perhaps deeper, excellent literature overview. - Michel Raynal: Concurrent Programming - Algorithms, Principles, and Foundations. Springer 2013.
A recent book, good and careful on the theoretical concepts, highly recommended as supplement. - Daniel J. Sorin, Mark D. Hill, David A. Wood: A primer on memory consistency models. Synthesis Lectures on Computer Architecture. Morgan and Claypool Publishers, 2011.
- Michael L. Scott: Shared-Memory Synchronization. Synthesis Lectures on Computer Architecture. Morgan and Claypool Publishers, 2013.