• 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
Fax : +43 1 58801 191 404
E-mail:

• Home
• Teaching
• Advanced Multiprocessor Programming (184.726)

Advanced Multiprocessor Programming (184.726) - Summersemester 2019

Lecturers

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

Plan

Lecture with practical project part (VU).

• Lectures Mondays 10:10 - 12:00, first 2.3.2019. Attendance mandatory, and generally recommended.
• Additional slots for exercises, project matters, etc.: Some Thursdays, 9:00 - 11:00.
• Lecture hall EI 6 (Gusshausstrasse 25-27), both lectures and exercises.
• Vorbesprechung (and first lecture): 2.3.2019. All potential students should be present!
• Project hand-in: 22.6.2019.
• Exam: First week of July, estimated (29.6-3.7.2019).
• 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.2019: Vorbesprechung. Intro, Mutual Exclusion problem and solutions
2. Monday, 9.3.2019: Mutual Exclusion problem and solutions
3. Monday, 16.3.2019: Constructions of atomic registers, register snapshot
4. Monday, 23.3.2019: Relative power of synchronization operations, correctness conditions
5. Thursday, 26.3.2019: Exercises batch 1
6. Monday, 30.3.2019: Relative power of synchronization operations
7. Thursday, 2.4.2019: Exercises batch 2
8. Monday, 6.4.2019: No lecture (Easter holidays)
9. Monday, 13.04.2019: No lecture (Easter holidays)
10. Monday, 20.4.2019: Projects (description). Practical lock implementations
11. Monday, 27.4.2019: Projects (selection). Data structures (I): List-based sets
12. Monday, 4.5.2019: Data structures (II): Queues and stacks
13. Monday, 11.5.2019: Data structures (III): Skiplist
14. Monday, 18.5.2019: Memory consistency models. Here is a note on memory consistency models.
15. Monday, 25.5.2019: Memory consistency models, memory reclamation (brief intro) (continued).
16. Monday, 1.6.2019: No lecture (Whitsun holiday)
17. Thursday, 4.6.2019: Project (status presentations): 10 minutes per group, all present (later that day: Gödel lecture);
18. Monday, 8.6.2019: Data structures (IV): Hash tables
19. Monday, 15.6.2019: Work-stealing theory
20. Monday, 22.6: Project hand-in

Exercises

1. Thursday, 26.3.2019, 9:00-11:00: EI 6, Gusshausstrasse 25-29
2. Thursday, 2.4.2019, 9:00-11:00: EI 6, Gusshausstrasse 25-29

The exercises are to be done individually, can be handed in on paper, or electronically by via TUWEL upload.

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

Except where noted, exercises are from the Herlihy/Shavit book.
• Batch 1 (HAND-IN: Before/at 26.3.2019; Blackboard: 26.3.2019). 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/at 2.4.2019; Blackboard: 2.4.2019). 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.2019, hand-in deadline (TUWEL) Monday 22.6.2019
The programming project is mandatory, hand-in deadline Monday 22.6.2019, 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.