• Group
• Research
• Projects
• Software
• Teaching
• Talks & Guests
• Open Positions
• How to find us

Contact us

TU Wien
Faculty of Informatics
Institute of Computer Engineering
Research Group Parallel Computing

Favoritenstrasse 16
1040 Vienna
Austria

Phone: +43 1 58801 191 411
E-mail:

• Home
• Teaching
• Advanced Multiprocessor Programming (184.726)

Advanced Multiprocessor Programming (184.726) - Summersemester 2020

Lecturers

• Jesper Larsson Träff
• Kyrill Winkler
• Sascha Hunold

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

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).

Except where noted, exercises are from the Herlihy/Shavit book.
• Batch 1 (HAND-IN: Before 26.3.2020 2.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.2020 9.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.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

• Exercises from the book, 1-75

Standards

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

Literature

• 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.