Course pages 2018–19
Unit: Multicore Semantics and Programming
This course is only taken by Part II 75% students.
Lecturers: Professor P. Sewell and Dr T. Harris
No. of lectures and practical classes: 8
Prerequisite courses: Discrete mathematics, Object-Oriented programing, Semantics of Programming Languages.
Capacity: 20
Aims
In recent years multiprocessors have become ubiquitous, but building reliable concurrent systems with good performance remains very challenging. The aim of this module is to introduce some of the theory and the practice of concurrent programming, from hardware memory models and the design of high-level programming languages to the correctness and performance properties of concurrent algorithms.
Lectures
Part 1: Introduction and relaxed-memory concurrency [Peter Sewell]
- Introduction. Sequential consistency, atomicity, basic concurrent problems. [1 block]
- Concurrency on real multiprocessors: the relaxed memory model(s) for x86, ARM, and IBM Power, and theoretical tools for reasoning about x86-TSO programs. [2 blocks]
- High-level languages. An introduction to C/C++11 and Java shared-memory concurrency. [1 block]
Part 2: Concurrent algorithms [Tim Harris]
- Concurrent programming. Simple algorithms (readers/writers, stacks, queues) and correctness criteria (linearisability and progress properties). Advanced synchronisation patterns (e.g. some of the following: optimistic and lazy list algorithms, hash tables, double-checked locking, RCU, hazard pointers), with discussion of performance and on the interaction between algorithm design and the underlying relaxed memory models. [3 blocks]
- Research topics, likely to include one hour on transactional memory and one guest lecture. [1 block]
Objectives
By the end of the course students should:
- have a good understanding of the semantics of concurrent programs, both at the multprocessor level and the C/Java programming language level;
- have a good understanding of some key concurrent algorithms, with practical experience.
Recommended reading
Herlihy, M. & Shavit, N. (2008). The art of multiprocessor programming. Morgan Kaufmann.
75=75