After successful completion of the course, students are able to

• Appreciate fundamental synchronization and coordination problems for shared-memory multiprocessors, including fundamental limitations
• Understand, exploit and cope with memory models and behavior
• Understand and apply basic concepts for lock-based, lock- and wait-free algorithms
• Apply fundamental lock-free algorithms and data structures (lists, stacks, queues...)
• Understand concepts and implementations of work-stealing schedulers

Memory models, 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, ...), work-stealing. Practical implementation project (C/C++ with pthreads, Java, ...)

Book: Herlihy, Shavit: The Art of Multiprocessor Programming. Morgan Kaufmann, Revised First Edition, 2012.

Lecture slides, additional papers.

 First Lecture: Mo. 6.3, 13:00

Lectures and discussion, active participation, blackboard exercises, project work

ECTS Breakdown

• Overview, seminar room 384, planning: 2h
• Lectures: 15x2h = 30h
• Lecture preparation and digestion: 15x1.5h = 22.5h
• Projects and Exercises: 50h
• Oral exam/project presentation, including preparation: 8h

Total: 112.5h = 4.5 ECTS

Exercises (hand-ins), project, oral examination

Introduction to Parallel Computing