The schedule is tentative and may change.
Date Lecture Papers
Oct 22

Administrative details
Taste of topics

The Implementation of the Cilk-5 Multithreaded Language

Idempotent Work Stealing

Laws of Order: Synchronization in Concurrent Algorithms

Fence-Free Work Stealing on Bounded TSO Processors

Oct 29

Reasoning about concurrency (linearizability)

Linearizability: A Correctness Condition for Concurrent Objects

A Lazy Concurrent List-Based Set Algorithm

Nov 5

Cache coherence

A Primer on Memory Consistency and Cache Coherence (Chapters 2, 6-8)

Nov 12

Serializing efficiently
Spin locks and local spinning
Lock-free synchronization and CAS failures

Algorithms for scalable synchronization on shared-memory multiprocessors

Flat Combining and the Synchronization-Parallelism Tradeof

OpLog: a library for scaling update-heavy data structures

Fast concurrent queues for x86 processors

Nov 19

Memory consistency models (hardware)

A Primer on Memory Consistency and Cache Coherence (Chapters 3-5)

WeeFence: Toward Making Fences Free in TSO

Nov 26

Memory consistency models (programming language)

Threads Cannot be Implemented as a Library

The Java Memory Model

Further reading:

Foundations of the C++ Concurrency Memory Model

Dec 3

Safe memory reclamation

High Performance Dynamic Lock-Free Hash Tables and List-Based Sets

Structured Deferral: Synchronization via Procrastination (explains RCU and compares to hazard pointers)

Practical lock-freedom (Epoch-based reclamation, Section 5.2.3)

Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects

Further reading:

Fast non-intrusive memory reclamation for highly-concurrent data structures

Drop the Anchor: Lightweight Memory Management for Non-Blocking Data Structures

Efficient Memory Management for Lock-Free Data Structures with Optimistic Access

StackTrack: An Automated Transactional Approach to Concurrent Memory Reclamation

Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way

Dec 10

Transactional memory (1/2)

Transactional Memory: Architectural Support for Lock-Free Data Struct ures

Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution

Transactional Locking II

Dec 24

Transactional memory (2/2)

TicToc: Time Traveling Optimistic Concurrency Control

Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory

LogTM: Log-based Transactional Memory

Dec 31

Concurrent search trees

A Practical Concurrent Binary Search Tree

A General Technique for Non-blocking Trees

Pragmatic Primitives for Non-blocking Data Structures

Jan 7

Ordered parallelism and relaxed data structures (1/2)

Skip lists (Section 4.3.3 of the thesis)

The SprayList: A Scalable Relaxed Priority Queue

MultiQueues: Simpler, Faster, and Better Relaxed Concurrent Priority Queues

A Lightweight Infrastructure for Graph Analytics (Section 4.1)

Jan 14

Ordered parallelism and relaxed data structures (2/2)

A Scalable Architecture for Ordered Parallelism

Persistent memory

Programming and Usage Models for Non-Volatile Memory

Jan 21

How to do sound experimental research