A Primer on Memory Consistency and Cache Coherence: Second Edition (Synthesis Lectures on Computer Architecture)

Preface to the Second Edition
Preface to the First Edition
Introduction to Consistency and Coherence
	Consistency (a.k.a., Memory Consistency, Memory Consistency Model, or Memory Model)
	Coherence (a.k.a., Cache Coherence)
	Consistency and Coherence for Heterogeneous Systems
	Specifying and Validating Memory Consistency Models and Cache Coherence
	A Consistency and Coherence Quiz
	What This Primer Does Not Do
	References
Coherence Basics
	Baseline System Model
	The Problem: How Incoherence Could Possibly Occur
	The Cache Coherence Interface
	(Consistency-Agnostic) Coherence Invariants
		Maintaining the Coherence Invariants
		The Granularity of Coherence
		When is Coherence Relevant?
	References
Memory Consistency Motivation and Sequential Consistency
	Problems with Shared Memory Behavior
	What is a Memory Consistency Model?
	Consistency vs. Coherence
	Basic Idea of Sequential Consistency (SC)
	A Little SC Formalism
	Naive SC Implementations
	A Basic SC Implementation with Cache Coherence
	Optimized SC Implementations with Cache Coherence
	Atomic Operations with SC
	Putting it All Together: MIPS R10000
	Further Reading Regarding SC
	References
Total Store Order and the X86 Memory Model
	Motivation for TSO/x86
	Basic Idea of TSO/x86
	A Little TSO/x86 Formalism
	Implementing TSO/x86
		Implementing Atomic Instructions
		Implementing Fences
	Further Reading Regarding TSO
	Comparing SC and TSO
	References
Relaxed Memory Consistency
	Motivation
		Opportunities to Reorder Memory Operations
		Opportunities to Exploit Reordering
	An Example Relaxed Consistency Model (XC)
		The Basic Idea of the XC Model
		Examples Using Fences Under XC
		Formalizing XC
		Examples Showing XC Operating Correctly
	Implementing XC
		Atomic Instructions with XC
		Fences With XC
		A Caveat
	Sequential Consistency for Data-Race-Free Programs
	Some Relaxed Model Concepts
		Release Consistency
		Causality and Write Atomicity
	Relaxed Memory Model Case Studies
		RISC-V Weak Memory Order (RVWMO)
		IBM Power
	Further Reading and Commercial Relaxed Memory Models
		Academic Literature
		Commercial Models
	Comparing Memory Models
		How Do Relaxed Memory Models Relate to Each Other and TSO and SC?
		How Good Are Relaxed Models?
	High-Level Language Models
	References
Coherence Protocols
	The Big Picture
	Specifying Coherence Protocols
	Example of a Simple Coherence Protocol
	Overview of Coherence Protocol Design Space
		States
		Transactions
		Major Protocol Design Options
	References
Snooping Coherence Protocols
	Introduction to Snooping
	Baseline Snooping Protocol
		High-Level Protocol Specification
		Simple Snooping System Model: Atomic Requests, Atomic Transactions
		Baseline Snooping System Model: Non-Atomic Requests, Atomic Transactions
		Running Example
		Protocol Simplifications
	Adding the Exclusive State
		Motivation
		Getting to the Exclusive State
		High-Level Specification of Protocol
		Detailed Specification
		Running Example
	Adding the Owned State
		Motivation
		High-Level Protocol Specification
		Detailed Protocol Specification
		Running Example
	Non-Atomic Bus
		Motivation
		In-Order vs. Out-of-Order Responses
		Non-Atomic System Model
		An MSI Protocol with a Split-Transaction Bus
		An Optimized, Non-Stalling MSI Protocol with a Split-Transaction Bus
	Optimizations to the Bus Interconnection Network
		Separate Non-Bus Network for Data Responses
		Logical Bus for Coherence Requests
	Case Studies
		Sun Starfire E10000
		IBM Power5
	Discussion and the Future of Snooping
	References
Directory Coherence Protocols
	Introduction to Directory Protocols
	Baseline Directory System
		Directory System Model
		High-Level Protocol Specification
		Avoiding Deadlock
		Detailed Protocol Specification
		Protocol Operation
		Protocol Simplifications
	Adding the Exclusive State
		High-Level Protocol Specification
		Detailed Protocol Specification
	Adding the Owned State
		High-Level Protocol Specification
		Detailed Protocol Specification
	Representing Directory State
		Coarse Directory
		Limited Pointer Directory
	Directory Organization
		Directory Cache Backed by DRAM
		Inclusive Directory Caches
		Null Directory Cache (With no Backing Store)
	Performance and Scalability Optimizations
		Distributed Directories
		Non-Stalling Directory Protocols
		Interconnection Networks Without Point-to-Point Ordering
		Silent vs. Non-Silent Evictions of Blocks in State S
	Case Studies
		SGI Origin 2000
		Coherent HyperTransport
		Hypertransport Assist
		Intel QPI
	Discussion and the Future of Directory Protocols
	References
Advanced Topics in Coherence
	System Models
		Instruction Caches
		Translation Lookaside Buffers (TLBs)
		Virtual Caches
		Write-Through Caches
		Coherent Direct Memory Access (DMA)
		Multi-Level Caches and Hierarchical Coherence Protocols
	Performance Optimizations
		Migratory Sharing Optimization
		False Sharing Optimizations
	Maintaining Liveness
		Deadlock
		Livelock
		Starvation
	Token Coherence
	The Future of Coherence
	References
Consistency and Coherence for Heterogeneous Systems
	GPU Consistency and Coherence
		Early GPUs: Architecture and Programming Model
		Big Picture: GPGPU Consistency and Coherence
		Temporal Coherence
		Release Consistency-directed Coherence
	More Heterogeneity Than Just GPUs
		Heterogeneous Consistency Models
		Heterogeneous Coherence Protocols
	Further Reading
	References
Specifying and Validating Memory Consistency Models and Cache Coherence
	Specification
		Operational Specification
		Axiomatic Specification
	Exploring the Behavior of Memory Consistency Models
		Litmus Tests
		Exploration
	Validating Implementations
		Formal Methods
		Testing
	History and Further Reading
	References
Authors' Biographies
Blank Page