798 Multicore programming

Instructor: Trevor Brown
E-mail: trevor (dot) brown (at) uwaterloo (dot) ca (include 798 in your subject)
Times: MW 3:30-4:50, DC 2585
My office: DC 2338
Course syllabus

Class Piazza

Please join and use the new class Piazza for your questions (unless they are sensitive).

We will also use Piazza to coordinate student presentation paper selections and for assignment submission.


Course materials

Class Topics Slides Supplementary material
Week 1 - Monday Asynchronous shared memory, counters, linearizability, cache coherence, false sharing PowerPoint Paper that introduced Linearizability
A few slides on cache coherence (Technion)
Week 1 - Wednesday More on padding, lock-freedom, lock-free stack (& proof sketch) PowerPoint Treiber stack (original paper)
Optional: a later stack technique (elimination)
Optional: even later stacks
Optional: hazard pointers (memory reclamation)
Optional: Treiber stack with hazard pointers for memory reclamation
Week 2 - Monday Stacks, queues, relaxed data structures, hash tables Powerpoint Optional: first lock-free queue
Optional: newer queues
Optional: Multi-Queue paper (mostly about graphs)
Week 2 - Wednesday Hash tables and deletion Powerpoint Expandable hash table we are studying
Week 3 - Monday Expanding a hash table Powerpoint (Same hash table paper as last class)
Week 3 - Wednesday More efficient expansion, linked data structures Powerpoint Harris' linked list
Week 4 - Monday k-word CAS and a doubly-linked list Powerpoint
Week 4 - Wednesday Implementing DCSS and k-word CAS Powerpoint k-CAS paper we are studying
My own fast C++ code for k-CAS (uses advanced techniques)
Week 5 - Monday Wrapping up k-word CAS Powerpoint Optional: my paper showing how to reuse descriptors
Week 5 - Wednesday Transactional memory Powerpoint Intel's restricted transactional memory (RTM) - also called HTM / TSX-NI
Nice article on lock elision and Intel's RTM
Some slides on using lock elision in Linux kernel
Week 6 - Monday Advanced uses of transactional memory, OpenMP Powerpoint Paper that introduced HTM-based KCAS
Nice slides on OpenMP
C++ code examples for this lecture's OpenMP slides
Week 6 - Wednesday Try-locks, versioned locks, lock-based KCAS + HTM, debugging tools Powerpoint GCC transactional memory intrinsics
A GDB tutorial (incl. relevant compilation options)
Very short Valgrind intro
A few nice Valgrind examples
A guide to Valgrind (with good frequently asked questions)
C++ code examples for this lecture's GDB and Valgrind slides


Assignment 3 [Starting code] Assignment 2 [Starting code] Assignment 1 [Starting code]

Paper presentations

The current presentation schedule is here.

Student presentation guidelines

Presenters Listening students Presenting students will be graded on their presentations.
Listening students will be graded on their reviews and feedback.

Recommended papers

See Piazza to determine which papers are already taken.