The schedule is tentative and may change.
Date Lecture Papers
Mar 16

Introduction
Overview
Administrative details
Taste of topics

Getting to the Root of Concurrent Binary Search Tree Performance

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

Mar 23

Out-of-order execution and memory-level parallelism

Cuckoo Trie: Exploiting Memory-Level Parallelism for Efficient DRAM Indexing

Mar 30

Speculative execution attacks & defenses

FLUSH+RELOAD: a High Resolution, Low Noise L3 Cache Side-Channel Attack

Spectre Attacks: Exploiting Speculative Execution

Meltdown: Reading Kernel Memory from User Space

Speculative Taint Tracking (STT): A Comprehensive Protection for Speculatively Accessed Data

Apr 20

Reasoning about concurrency (linearizability)

Linearizability: A Correctness Condition for Concurrent Objects

A Lazy Concurrent List-Based Set Algorithm

Apr 27

Cache coherence

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

May 4

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

Algorithms for scalable synchronization on shared-memory multiprocessors

Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

Flat Combining and the Synchronization-Parallelism Tradeof

OpLog: a library for scaling update-heavy data structures

Fast concurrent queues for x86 processors

May 11

Memory consistency models (hardware)

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

WeeFence: Toward Making Fences Free in TSO

May 18

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

Jun 1

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

Jun 8

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)

Jun 15

Ordered parallelism and relaxed data structures (2/2)

A Scalable Architecture for Ordered Parallelism

Jun 22

Transactional memory

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

Speculative Lock Elision: Enabling Highly Concurrent Multithreaded Execution

Transactional Locking II

TicToc: Time Traveling Optimistic Concurrency Control

Reduced Hardware NOrec: A Safe and Scalable Hybrid Transactional Memory

LogTM: Log-based Transactional Memory

Jun 29

Concurrent search trees

A Practical Concurrent Binary Search Tree

A General Technique for Non-blocking Trees

Pragmatic Primitives for Non-blocking Data Structures

Harnessing Epoch-based Reclamation for Efficient Range Queries