The Art of Multiprocessor Programming, Revised Reprint
- 1st Edition - June 25, 2012
- Authors: Maurice Herlihy, Nir Shavit
- Language: English
- eBook ISBN:9 7 8 - 0 - 1 2 - 3 9 7 7 9 5 - 3
Revised and updated with improvements conceived in parallel programming courses, The Art of Multiprocessor Programming is an authoritative guide to multicore programming. It introd… Read more
Revised and updated with improvements conceived in parallel programming courses, The Art of Multiprocessor Programming is an authoritative guide to multicore programming. It introduces a higher level set of software development skills than that needed for efficient single-core programming. This book provides comprehensive coverage of the new principles, algorithms, and tools necessary for effective multiprocessor programming. Students and professionals alike will benefit from thorough coverage of key multiprocessor programming issues.
- This revised edition incorporates much-demanded updates throughout the book, based on feedback and corrections reported from classrooms since 2008
- Learn the fundamentals of programming multiple threads accessing shared memory
- Explore mainstream concurrent data structures and the key elements of their design, as well as synchronization techniques from simple locks to transactional memory systems
- Visit the companion site and download source code, example Java programs, and materials to support and enhance the learning experience
Students in multiprocessor and multicore programming courses and engineers working with multiprocessor and multicore systems.
Dedication
Acknowledgments
Product Note
Preface
Suggested Ways to Teach the Art of Multiprocessor Programming
1. Introduction
1.1 Shared Objects and Synchronization
1.2 A Fable
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
I Principles
2. Mutual Exclusion
2.1 Time
2.2 Critical Sections
2.3 2-Thread Solutions
2.4 The Filter Lock
2.5 Fairness
2.6 Lamport’s Bakery Algorithm
2.7 Bounded Timestamps
2.8 Lower Bounds on the Number of Locations
2.9 Chapter Notes
3. Concurrent Objects
3.1 Concurrency and Correctness
3.2 Sequential Objects
3.3 Quiescent Consistency
3.4 Sequential Consistency
3.5 Linearizability
3.6 Formal Definitions
3.7 Progress Conditions
3.8 The Java Memory Model
3.9 Remarks
3.10 Chapter Notes
4. Foundations of Shared Memory
4.1 The Space of Registers
4.2 Register Constructions
4.3 Atomic Snapshots
4.4 Chapter Notes
5. The Relative Power of Primitive Synchronization Operations
5.1 Consensus Numbers
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
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
II Practice
7. Spin Locks and Contention
7.1 Welcome to the Real World
7.2 Test-And-Set Locks
7.3 TAS-Based Spin Locks Revisited
7.4 Exponential Backoff
7.5 Queue Locks
7.6 A Queue Lock with Timeouts
7.7 A Composite Lock
7.8 Hierarchical Locks
7.9 One Lock To Rule Them All
7.10 Chapter Notes
8. Monitors and Blocking Synchronization
8.1 Introduction
8.2 Monitor Locks and Conditions
8.3 Readers–Writers Locks
8.4 Our Own Reentrant Lock
8.5 Semaphores
8.6 Chapter Notes
9. Linked Lists
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 Non-Blocking Synchronization
9.9 Discussion
9.10 Chapter Notes
10. Concurrent Queues and the ABA Problem
10.1 Introduction
10.2 Queues
10.3 A Bounded Partial Queue
10.4 An Unbounded Total Queue
10.5 An Unbounded Lock-Free Queue
10.6 Memory Reclamation and the ABA Problem
10.7 Dual Data Structures
10.8 Chapter Notes
11. Concurrent Stacks and Elimination
11.1 Introduction
11.2 An Unbounded Lock-Free Stack
11.3 Elimination
11.4 The Elimination Backoff Stack
11.5 Chapter Notes
12. Counting, Sorting, and Distributed Coordination
12.1 Introduction
12.2 Shared Counting
12.3 Software Combining
12.4 Quiescently Consistent Pools and Counters
12.5 Counting Networks
12.6 Diffracting Trees
12.7 Parallel Sorting
12.8 Sorting Networks
12.9 Sample Sorting
12.10 Distributed Coordination
12.11 Chapter Notes
13. Concurrent Hashing and Natural Parallelism
13.1 Introduction
13.2 Closed-Address Hash Sets
13.3 A Lock-Free Hash Set
13.4 An Open-Addressed Hash Set
13.5 Chapter Notes
14. Skiplists and Balanced Search
14.1 Introduction
14.2 Sequential Skiplists
14.3 A Lock-Based Concurrent Skiplist
14.4 A Lock-Free Concurrent Skiplist
14.5 Concurrent Skiplists
14.6 Chapter Notes
15. Priority Queues
15.1 Introduction
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.5 A Skiplist-Based Unbounded Priority Queue
15.6 Chapter Notes
16. Futures, Scheduling, and Work Distribution
16.1 Introduction
16.2 Analyzing Parallelism
16.3 Realistic Multiprocessor Scheduling
16.4 Work Distribution
16.5 Work-Stealing Dequeues
16.6 Chapter Notes
17. Barriers
17.1 Introduction
17.2 Barrier Implementations
17.3 Sense-Reversing Barrier
17.4 Combining Tree Barrier
17.5 Static Tree Barrier
17.6 Termination Detecting Barriers
17.7 Chapter Notes
18. Transactional Memory
18.1 Introduction
18.2 Transactions and Atomicity
18.3 Software Transactional Memory
18.4 Hardware Transactional Memory
18.5 Chapter Notes
III Appendix
A. Software Basics
B. Hardware Basics
Index
- Edition: 1
- Published: June 25, 2012
- Language: English
MH
Maurice Herlihy
Maurice Herlihy received an A.B. in Mathematics from Harvard University, and a Ph.D. in Computer Science from M.I.T. He has served on the faculty of Carnegie Mellon University, on the staff of DEC Cambridge Research Lab, and is currently a Professor in the Computer Science Department at Brown University. Dr. Herlihy is an ACM Fellow, and is the recipient of the 2003 Dijkstra Prize in Distributed Computing. He shared the 2004 Gödel Prize with Nir Shavit, with whom he also shared the 2012 Edsger W. Dijkstra Prize In Distributed Computing.
Affiliations and expertise
Brown University, Providence, RI, USANS
Nir Shavit
Nir Shavit received a B.A. and M.Sc. from the Technion and a Ph.D. from the Hebrew University, all in Computer Science. From 1999 to 2011 he served as a member of technical staff at Sun Labs and Oracle Labs. He shared the 2004 Gödel Prize with Maurice Herlihy, with whom he also shared the 2012 Edsger W. Dijkstra Prize in Distributed Computing. He is a Professor in the Electrical Engineering and Computer Science Department at M.I.T. and the Computer Science Department at Tel-Aviv University.
Affiliations and expertise
Professor of Computer Science, Massachusetts Institute of Technology, Cambridge, MA, USA