|
The Art of Multiprocessor Programming
This book is the first comprehensive presentation of the principles and tools available for programming multiprocessor machines. It is of immediate use to programmers working with the new architectures. For example, the next generation of computer game consoles will all be multiprocessor-based, and the game industry is currently struggling to understand
how to address the programming challenges presented by these machines. This change in the industry is so fundamental that it is certain to require a significant response by universities, and courses on multicore programming will become a staple of computer science curriculums. The authors are well known and respected in this community and both teach and conduct research in this area. Prof. Maurice Herlihy is on the faculty of Brown University. He is the recipient of the 2003 Dijkstra Prize in distributed computing. Prof. Nir Shavit is on the faculty of Tel-Aviv University and a member of the technical staff at Sun Microsystems Laboratories. In 2004 they shared the Godel Prize, the highest award in theoretical computer science.
CONTENTS:
Contents
Part I: Foundations 1 Introduction 1.1 Shared Objects and Synchronization 1.2 A Fable 1.2.1 Properties of Mutual Exclusion 1.2.2 The Moral 1.3 The Producer-Consumer Problem 1.4 The Readers/Writers Problem 1.5 Missive 1.6 Exercises 1.7 Chapter Notes 2 Mutual Exclusion 2.1 Time 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 The Filter Lock 2.5 Fairness 2.6 Lamport's Bakery Algorithm 2.7 Bounded Timestamps 2.8 Lower Bounds on Number of Locations 2.9 Granularity of Mutual Exclusion 2.10 Exercises 2.11 Chapter Notes 3 Concurrent Objects and Lineraizability 3.1 Sequential Objects 3.2 The Linearizability Manifesto 3.3 Examples 3.4 Queue Implementations 3.5 Precise Definitions 3.5.1 Linearizability 3.6 The Locality Property 3.7 The Non-Blocking Property 3.8 Sequential Consistency 3.9 Serializability 3.10 Exercises 3.11 Chapter Notes 4 Foundations of Shared Memory 4.1 The Space of Registers 4.2 Register Constructions 4.2.1 Safe Boolean MRSW Registers 4.2.2 Regular Boolean MRSW Register 4.2.3 Regular M-valued MRSW Register 4.2.4 Atomic MRMW Register 4.3 Atomic Snapshots 4.3.1 A Simple Snapshot 4.3.2 A Wait-Free Snapshot 4.3.3 Correctness Arguments 4.3.4 Remarks 4.4 Exercises 4.5 Chapter Notes 5 The Relative Power of Synchronization Methods 5.1 Consensus Numbers 5.2 States and Valency 5.3 Atomic Registers 5.4 Consensus Protocols 5.5 FIFO Queues 5.6 Multiple Assignment 5.7 Read-Modify-Write Registers 5.8 Interfering Read-Modify Write Methods 5.9 The compareAndSet(())Method 5.10 Exercises 5.11 Chapter Notes 6 The Universality of Consensus 6.1 Introduction 6.2 Universality Results 6.3 Sequential Objects 6.4 Cells 6.5 The Algorithm 6.6 Exercises 6.7 Chapter Notes Part II: Practice 7 Spin Locks and Contention 7.1 Introduction to the Real World 7.2 testAndSet Locks 7.3 Multiprocessor Architectures 7.4 Caching and Consistency 7.5 TAS-Based Spin Locks Revisited 7.6 Exponential Backoff 7.7 Queue Locks 7.7.1 Array-Based Locks and False Sharing 7.7.2 The CLH Queue Lock 7.7.3 The MCS Queue Lock 7.8 Locks with Timeouts 7.9 Monitors 7.9.1 Condition Variables 7.9.2 Java Monitors 7.10 Exercises 7.11 Chapter Notes 8 Linked Lists: the Role of Locking 8.1 Introduction 8.2 List-based Sets 8.3 Concurrent Reasoning 8.4 Coarse-Grained Synchronization 8.5 Fine-Grained Synchronization 8.6 Optimistic Synchronization 8.7 Lazy Synchronization 8.8 A Lock-Free List 8.9 Discussion 8.10 Exercises 8.11 Chapter Notes 9 Concurrent Hashing and Natural Parallelism 9.1 Introduction 9.2 Hashing 9.3 Fine-Grained Locking 9.4 Read/Write Locking 9.5 Optimistic Synchronization 9.6 Lock-Free Hashing 9.6.1 Recursive split-ordering 9.6.2 Growing the Table 9.6.3 Lock-Free Hash Set Implementation 9.7 Exercises 9.8 Chapter Notes 10 Concurrent Counting and Structured Parallelism 10.1 Introduction 10.2 Combining Trees 10.2.1 Phase One 10.2.2 Phase Two 10.2.3 Phase Three 10.2.4 Phase Four 10.2.5 Performance Issues 10.3 Counting Networks 10.3.1 A Bitonic Counting Network 10.3.2 Proof of Correctness 10.3.3 A Periodic Counting Network 10.3.4 Proof of Correctness 10.3.5 Implementation 10.3.6 Performance Comparison 10.4 Supporting Decrements 10.5 Adding Networks 10.6 Exercises 10.7 Chapter Notes 11 Diffracting Trees and Data Structure Layout 11.1 Overview 11.2 Trees That Count 11.3 Diffraction Balancing 11.4 Implementation Details 11.5 Performance 11.6 Message Passing Implementation 11.7 Measuring Performance 12 Concurrent Stacks and the ABA Problem 12.1 Introduction 12.2 A Lock-Based Stack 12.3 A Lock-Free Stack 12.4 The ABA problem 12.5 Elimination 12.6 A Scalable Lock-free Stack 12.7 Exercises 12.8 Chapter Notes 13 Concurrent Queues and the Optimistic Approach 13.1 Introduction 13.2 A Lock-Based Queue 13.3 A Lock-Free Queue 13.4 Exercises 13.5 Chapter Notes 14 Concurrent Heaps 14.1 Introduction 14.2 A Lock-Based Heap 14.3 Lock-Free Heaps 14.4 Exercises 14.5 Chapter Notes 15 Concurrent Search Structures 15.1 Introduction 15.2 Lock-Based Search Trees 15.3 Concurrent Skiplists 15.4 Lock-Free Search Trees 15.5 Exercises 15.6 Chapter Notes 16 Barriers and Phased Computation 16.1 Introduction 16.2 Barrier Implementations 16.3 Sense-Reversing Barriers 16.4 Tree Barriers 16.5 Tournament Tree Barriers 16.6 Dissemination Barriers 16.7 Exercises 16.8 Chapter Notes 17 Work Stealing and Dynamic Load Distribution 17.1 Introduction 17.2 Model 17.3 Realistic Multiprocessor Scheduling 17.4 Work Stealing 17.5 The Steal-Half Protocol 17.6 Exercises 17.7 Chapter Notes Part III: Advanced Topics 18 Room Synchronization 18.1 Introduction 18.2 Properties 18.3 Dynamic Stack Example 18.4 Implementations 18.4.1 The Ticket Implementation 18.4.2 The Queue Implementation 18.5 Remarks 18.6 Chapter Notes 19 Transactional Memory 19.1 Introduction 19.2 Software Transactional Memory 19.3 Search Trees Revisited 19.4 Hardware Support for Transactional Synchronization 19.5 Hybrid Transactional Memory 19.6 Exercises 19.7 Chapter Notes
|
