skip to primary navigationskip to content

Department of Computer Science and Technology



Course pages 2023–24

Multicore Semantics and Programming

Principal lecturers: Prof Peter Sewell, Dr Timothy Harris
Additional lecturer: Dr Christopher Pulte
Taken by: MPhil ACS, Part III
Code: L304
Term: Michaelmas
Hours: 16 (8 x 2h blocks, including 2 x 1h practical sessions)
Format: In-person lectures
Class limit: max. 10 students
Prerequisites: Some familiarity with discrete mathematics (sets, partial orders, etc.) and with sequential Java programming will be assumed. Experience with operational semantics and with some concurrent programming would be helpful.
Moodle, timetable


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.


Part 1: Introduction and relaxed-memory concurrency [Professor P. 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 [Dr T. 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]


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.

Assessment - Part II Students

Two assignments each worth 50%

Recommended reading

Herlihy, M. and Shavit, N. (2008). The art of multiprocessor programming. Morgan Kaufmann.


Coursework will consist of assessed exercises.

Practical work

Part 2 of the course will include a practical exercise sheet.  The practical exercises involve building concurrent data structures and measuring their performance.  The work can be completed in C, Java, or similar languages.

Assessment - Part III and MPhil Students

  • Assignment 1, for 50% of the overall grade. Written coursework comprising a series of questions on hardware and software relaxed-memory concurrency semantics.
  • Assignment 2, for 50% of the overall grade. Written coursework comprising a series of questions on the design of mutual exclusion locks and shared-memory data structures.

Further Information

Current Cambridge undergraduate students who are continuing onto Part III or the MPhil in Advanced Computer Science may only take this module if they did NOT take it as a Unit of Assessment in Part II.

This module is shared with Part II of the Computer Science Tripos. Assessment will be adjusted for the two groups of students to be at an appropriate level for whichever course the student is enrolled on. Further information about assessment and practicals will follow at the first lecture.