The Art of Multiprocessor Programming

Contents
Preface
Acknowledgments
Suggested ways to teach the art of multiprocessor programming
1 Introduction
1.1 Shared objects and synchronization
1.2 A fable
1.2.1 Properties of a mutual exclusion protocol
1.2.2 The moral
1.3 The producer-consumer problem
1.4 The readers-writers problem
1.5 The harsh realities of parallelization
1.6 Parallel programming
1.7 Chapter notes
1.8 Exercises
2 Mutual exclusion
2.1 Time and events
2.2 Critical sections
2.3 Two-thread solutions
2.3.1 The LockOne class
2.3.2 The LockTwo class
2.3.3 The Peterson lock
2.4 Notes on deadlock
2.5 The filter lock
2.6 Fairness
2.7 Lamport's Bakery algorithm
2.8 Bounded timestamps
2.9 Lower bounds on the number of locations
2.10 Chapter notes
2.11 Exercises
3 Concurrent objects
3.1 Concurrency and correctness
3.2 Sequential objects
3.3 Sequential consistency
3.3.1 Sequential consistency versus real-time order
3.3.2 Sequential consistency is nonblocking
3.3.3 Compositionality
3.4 Linearizability
3.4.1 Linearization points
3.4.2 Linearizability versus sequential consistency
3.5 Quiescent consistency
3.5.1 Properties of quiescent consistency
3.6 Formal definitions
3.6.1 Histories
3.6.2 Linearizability
3.6.3 Linearizability is compositional
3.6.4 Linearizability is nonblocking
3.7 Memory consistency models
3.8 Progress conditions
3.8.1 Wait-freedom
3.8.2 Lock-freedom
3.8.3 Obstruction-freedom
3.8.4 Blocking progress conditions
3.8.5 Characterizing progress conditions
3.9 Remarks
3.10 Chapter notes
3.11 Exercises
4 Foundations of shared memory
4.1 The space of registers
4.2 Register constructions
4.2.1 Safe MRSW registers
4.2.2 A regular Boolean MRSW register
4.2.3 A regular M-valued MRSW register
4.2.4 An atomic SRSW register
4.2.5 An atomic MRSW register
4.2.6 An atomic MRMW register
4.3 Atomic snapshots
4.3.1 An obstruction-free snapshot
4.3.2 A wait-free snapshot
4.3.3 Correctness arguments
4.4 Chapter notes
4.5 Exercises
5 The relative power of primitive synchronization operations
5.1 Consensus numbers
5.1.1 States and valence
5.2 Atomic registers
5.3 Consensus protocols
5.4 FIFO queues
5.5 Multiple assignment objects
5.6 Read-modify-write operations
5.7 Common2 RMW operations
5.8 The compareAndSet operation
5.9 Chapter notes
5.10 Exercises
6 Universality of consensus
6.1 Introduction
6.2 Universality
6.3 A lock-free universal construction
6.4 A wait-free universal construction
6.5 Chapter notes
6.6 Exercises
7 Spin locks and contention
7.1 Welcome to the real world
7.2 Volatile fields and atomic objects
7.3 Test-and-set locks
7.4 Exponential back-off
7.5 Queue locks
7.5.1 Array-based locks
7.5.2 The CLH queue lock
7.5.3 The MCS queue lock
7.6 A queue lock with timeouts
7.7 Hierarchical locks
7.7.1 A hierarchical back-off lock
7.7.2 Cohort locks
7.7.3 A cohort lock implementation
7.8 A composite lock
7.9 A fast path for threads running alone
7.10 One lock to rule them all
7.11 Chapter notes
7.12 Exercises
8 Monitors and blocking synchronization
8.1 Introduction
8.2 Monitor locks and conditions
8.2.1 Conditions
8.2.2 The lost-wakeup problem
8.3 Readers-writers locks
8.3.1 Simple readers-writers lock
8.3.2 Fair readers-writers lock
8.4 Our own reentrant lock
8.5 Semaphores
8.6 Chapter notes
8.7 Exercises
9 Linked lists: The role of locking
9.1 Introduction
9.2 List-based sets
9.3 Concurrent reasoning
9.4 Coarse-grained synchronization
9.5 Fine-grained synchronization
9.6 Optimistic synchronization
9.7 Lazy synchronization
9.8 Nonblocking synchronization
9.9 Discussion
9.10 Chapter notes
9.11 Exercises
10 Queues, memory management, and the ABA problem
10.1 Introduction
10.2 Queues
10.3 A bounded partial queue
10.4 An unbounded total queue
10.5 A lock-free unbounded queue
10.6 Memory reclamation and the ABA problem
10.6.1 A naïve synchronous queue
10.7 Dual data structures
10.8 Chapter notes
10.9 Exercises
11 Stacks and elimination
11.1 Introduction
11.2 An unbounded lock-free stack
11.3 Elimination
11.4 The elimination back-off stack
11.4.1 A lock-free exchanger
11.4.2 The elimination array
11.5 Chapter notes
11.6 Exercises
12 Counting, sorting, and distributed coordination
12.1 Introduction
12.2 Shared counting
12.3 Software combining
12.3.1 Overview
12.3.2 An extended example
12.3.3 Performance and robustness
12.4 Quiescently consistent pools and counters
12.5 Counting networks
12.5.1 Networks that count
12.5.2 The bitonic counting network
12.5.2.1 A software bitonic counting network
12.5.2.2 Proof of correctness
12.5.2.3 A periodic counting network
12.5.2.4 A software periodic counting network
12.5.3 Performance and pipelining
12.6 Diffracting trees
12.7 Parallel sorting
12.8 Sorting networks
12.8.1 Designing a sorting network
12.8.1.1 A bitonic sorting algorithm
12.9 Sample sorting
12.10 Distributed coordination
12.11 Chapter notes
12.12 Exercises
13 Concurrent hashing and natural parallelism
13.1 Introduction
13.2 Closed-address hash sets
13.2.1 A coarse-grained hash set
13.2.2 A striped hash set
13.2.3 A refinable hash set
13.3 A lock-free hash set
13.3.1 Recursive split-ordering
13.3.2 The BucketList class
13.3.3 The LockFreeHashSet class
13.4 An open-address hash set
13.4.1 Cuckoo hashing
13.4.2 Concurrent cuckoo hashing
13.4.3 Striped concurrent cuckoo hashing
13.4.4 A refinable concurrent cuckoo hash set
13.5 Chapter notes
13.6 Exercises
14 Skiplists and balanced search
14.1 Introduction
14.2 Sequential skiplists
14.3 A lock-based concurrent skiplist
14.3.1 A bird's-eye view
14.3.2 The algorithm
14.4 A lock-free concurrent skiplist
14.4.1 A bird's-eye view
14.4.2 The algorithm in detail
14.5 Concurrent skiplists
14.6 Chapter notes
14.7 Exercises
15 Priority queues
15.1 Introduction
15.1.1 Concurrent priority queues
15.2 An array-based bounded priority queue
15.3 A tree-based bounded priority queue
15.4 An unbounded heap-based priority queue
15.4.1 A sequential heap
15.4.2 A concurrent heap
15.5 A skiplist-based unbounded priority queue
15.6 Chapter notes
15.7 Exercises
16 Scheduling and work distribution
16.1 Introduction
16.2 Analyzing parallelism
16.3 Realistic multiprocessor scheduling
16.4 Work distribution
16.4.1 Work stealing
16.4.2 Yielding and multiprogramming
16.5 Work-stealing deques
16.5.1 A bounded work-stealing deque
16.5.2 An unbounded work-stealing deque
16.5.3 Work dealing
16.6 Chapter notes
16.7 Exercises
17 Data parallelism
17.1 MapReduce
17.1.1 The MapReduce framework
17.1.2 A MapReduce-based WordCount application
17.1.3 A MapReduce-based KMeans application
17.1.4 The MapReduce implementation
17.2 Stream computing
17.2.1 A stream-based WordCount application
17.2.2 A stream-based KMeans application
17.2.3 Making aggregate operations parallel
17.3 Chapter notes
17.4 Exercises
18 Barriers
18.1 Introduction
18.2 Barrier implementations
18.3 Sense reversing barrier
18.4 Combining tree barrier
18.5 Static tree barrier
18.6 Termination detection barriers
18.7 Chapter notes
18.8 Exercises
19 Optimism and manual memory management
19.1 Transitioning from Java to C++
19.2 Optimism and explicit reclamation
19.3 Protecting pending operations
19.4 An object for managing memory
19.5 Traversing a list
19.6 Hazard pointers
19.7 Epoch-based reclamation
19.8 Chapter notes
19.9 Exercises
20 Transactional programming
20.1 Challenges in concurrent programming
20.1.1 Problems with locking
20.1.2 Problems with explicit speculation
20.1.3 Problems with nonblocking algorithms
20.1.4 Problems with compositionality
20.1.5 Summary
20.2 Transactional programming
20.2.1 An example of transactional programming
20.3 Hardware support for transactional programming
20.3.1 Hardware speculation
20.3.2 Basic cache coherence
20.3.3 Transactional cache coherence
20.3.4 Limitations of hardware support
20.4 Transactional lock elision
20.4.1 Discussion
20.5 Transactional memory
20.5.1 Run-time scheduling
20.5.2 Explicit self-abort
20.6 Software transactions
20.6.1 Transactions with ownership records
20.6.2 Transactions with value-based validation
20.7 Combining hardware and software transactions
20.8 Transactional data structure design
20.9 Chapter notes
20.10 Exercises
A Software basics
A.1 Introduction
A.2 Java
A.2.1 Threads
A.2.2 Monitors
A.2.3 Yielding and sleeping
A.2.4 Thread-local objects
A.2.5 Randomization
A.3 The Java memory model
A.3.1 Locks and synchronized blocks
A.3.2 Volatile fields
A.3.3 Final fields
A.4 C++
A.4.1 Threads in C++
A.4.2 Locks in C++
A.4.3 Condition variables
A.4.4 Atomic variables
A.4.5 Thread-local storage
A.5 C#
A.5.1 Threads
A.5.2 Monitors
A.5.3 Thread-local objects
A.6 Appendix notes
B Hardware basics
B.1 Introduction (and a puzzle)
B.2 Processors and threads
B.3 Interconnect
B.4 Memory
B.5 Caches
B.5.1 Coherence
B.5.2 Spinning
B.6 Cache-conscious programming, or the puzzle solved
B.7 Multicore and multithreaded architectures
B.7.1 Relaxed memory consistency
B.8 Hardware synchronization instructions
B.9 Appendix notes
B.10 Exercises
Bibliography
Index