The Art of Multiprocessor Programming
Regular price
29.250 KD
inc. VAT
Couldn't load pickup availability
Table of contents
- Cover
- Table of Contentsvii
- Acknowledgmentsxvii
- Prefacexix
- Chapter 1. Introduction1
- 1.1 Shared Objects and Synchronization3
- 1.2 A Fable6
- 1.3 The Producer–Consumer Problem10
- 1.4 The Readers–Writers Problem12
- 1.5 The Harsh Realities of Parallelization13
- 1.6 Parallel Programming15
- 1.7 Chapter Notes15
- 1.8 Exercises16
- Part I: Principles19
- Chapter 2. Mutual Exclusion21
- 2.1 Time21
- 2.2 Critical Sections22
- 2.3 2-Thread Solutions24
- 2.4 The Filter Lock28
- 2.5 Fairness31
- 2.6 Lamport’s Bakery Algorithm31
- 2.7 Bounded Timestamps33
- 2.8 Lower Bounds on the Number of Locations37
- 2.9 Chapter Notes40
- 2.10 Exercises41
- Chapter 3. Concurrent Objects45
- 3.1 Concurrency and Correctness45
- 3.2 Sequential Objects48
- 3.3 Quiescent Consistency49
- 3.4 Sequential Consistency51
- 3.5 Linearizability54
- 3.6 Formal Definitions55
- 3.7 Progress Conditions59
- 3.8 The Java Memory Model61
- 3.9 Remarks64
- 3.10 Chapter Notes65
- 3.11 Exercises66
- Chapter 4. Foundations of Shared Memory71
- 4.1 The Space of Registers72
- 4.2 Register Constructions77
- 4.3 Atomic Snapshots87
- 4.4 Chapter Notes93
- 4.5 Exercises94
- Chapter 5. The Relative Power of Primitive Synchronization Operations99
- 5.1 Consensus Numbers100
- 5.2 Atomic Registers103
- 5.3 Consensus Protocols106
- 5.4 FIFO Queues106
- 5.5 Multiple Assignment Objects110
- 5.6 Read–Modify–Write Operations112
- 5.7 Common2 RMW Operations114
- 5.8 The compareAndSet() Operation116
- 5.9 Chapter Notes117
- 5.10 Exercises118
- Chapter 6. Universality of Consensus125
- 6.1 Introduction125
- 6.2 Universality126
- 6.3 A Lock-Free Universal Construction126
- 6.4 A Wait-Free Universal Construction130
- 6.5 Chapter Notes136
- 6.6 Exercises137
- Part II: Practice139
- Chapter 7. Spin Locks and Contention141
- 7.1 Welcome to the Real World141
- 7.2 Test-And-Set Locks144
- 7.3 TAS-Based Spin Locks Revisited146
- 7.4 Exponential Backoff147
- 7.5 Queue Locks149
- 7.6 A Queue Lock with Timeouts157
- 7.7 A Composite Lock159
- 7.8 Hierarchical Locks167
- 7.9 One Lock To Rule Them All173
- 7.10 Chapter Notes173
- 7.11 Exercises174
- Chapter 8. Monitors and Blocking Synchronization177
- 8.1 Introduction177
- 8.2 Monitor Locks and Conditions178
- 8.3 Readers–Writers Locks183
- 8.4 Our Own Reentrant Lock187
- 8.5 Semaphores189
- 8.6 Chapter Notes189
- 8.7 Exercises190
- Chapter 9. Linked Lists: The Role of Locking195
- 9.1 Introduction195
- 9.2 List-Based Sets196
- 9.3 Concurrent Reasoning198
- 9.4 Coarse-Grained Synchronization200
- 9.5 Fine-Grained Synchronization201
- 9.6 Optimistic Synchronization205
- 9.7 Lazy Synchronization208
- 9.8 Non-Blocking Synchronization213
- 9.9 Discussion218
- 9.10 Chapter Notes219
- 9.11 Exercises219
- Chapter 10. Concurrent Queues and the ABA Problem223
- 10.1 Introduction223
- 10.2 Queues224
- 10.3 A Bounded Partial Queue225
- 10.4 An Unbounded Total Queue229
- 10.5 An Unbounded Lock-Free Queue230
- 10.6 Memory Reclamation and the ABA Problem233
- 10.7 Dual Data Structures238
- 10.8 Chapter Notes241
- 10.9 Exercises241
- Chapter 11. Concurrent Stacks and Elimination245
- 11.1 Introduction245
- 11.2 An Unbounded Lock-Free Stack245
- 11.3 Elimination248
- 11.4 The Elimination Backoff Stack249
- 11.5 Chapter Notes255
- 11.6 Exercises255
- Chapter 12. Counting, Sorting, and Distributed Coordination259
- 12.1 Introduction259
- 12.2 Shared Counting259
- 12.3 Software Combining260
- 12.4 Quiescently Consistent Pools and Counters269
- 12.5 Counting Networks270
- 12.6 Diffracting Trees282
- 12.7 Parallel Sorting286
- 12.8 Sorting Networks286
- 12.9 Sample Sorting290
- 12.10 Distributed Coordination291
- 12.11 Chapter Notes292
- 12.12 Exercises293
- Chapter 13. Concurrent Hashing and Natural Parallelism299
- 13.1 Introduction299
- 13.2 Closed-Address Hash Sets300
- 13.3 A Lock-Free Hash Set309
- 13.4 An Open-Addressed Hash Set316
- 13.5 Chapter Notes325
- 13.6 Exercises326
- Chapter 14. Skiplists and Balanced Search329
- 14.1 Introduction329
- 14.2 Sequential Skiplists329
- 14.3 A Lock-Based Concurrent Skiplist331
- 14.4 A Lock-Free Concurrent Skiplist339
- 14.5 Concurrent Skiplists348
- 14.6 Chapter Notes348
- 14.7 Exercises349
- Chapter 15. Priority Queues351
- 15.1 Introduction351
- 15.2 An Array-Based Bounded Priority Queue352
- 15.3 A Tree-Based Bounded Priority Queue353
- 15.4 An Unbounded Heap-Based Priority Queue355
- 15.5 A Skiplist-Based Unbounded Priority Queue363
- 15.6 Chapter Notes366
- 15.7 Exercises366
- Chapter 16. Futures, Scheduling, and Work Distribution369
- 16.1 Introduction369
- 16.2 Analyzing Parallelism375
- 16.3 Realistic Multiprocessor Scheduling378
- 16.4 Work Distribution381
- 16.5 Work-Stealing Dequeues382
- 16.6 Chapter Notes392
- 16.7 Exercises392
- Chapter 17. Barriers397
- 17.1 Introduction397
- 17.2 Barrier Implementations398
- 17.3 Sense-Reversing Barrier399
- 17.4 Combining Tree Barrier401
- 17.5 Static Tree Barrier402
- 17.6 Termination Detecting Barriers404
- 17.7 Chapter Notes408
- 17.8 Exercises409
- Chapter 18. Transactional Memory417
- 18.1 Introduction417
- 18.2 Transactions and Atomicity421
- 18.3 Software Transactional Memory424
- 18.4 Hardware Transactional Memory445
- 18.5 Chapter Notes448
- 18.6 Exercises449
- Part III: AppendixA1
- Appendix A. Software BasicsA3
- A.1 IntroductionA3
- A.2 JavaA3
- A.3 C#A10
- A.4 PthreadsA14
- A.5 Chapter NotesA16
- Appendix B. Hardware BasicsA19
- B.1 Introduction (and a Puzzle)A19
- B.2 Processors and ThreadsA22
- B.3 InterconnectA22
- B.4 MemoryA23
- B.5 CachesA23
- B.6 Cache-Conscious Programming, or the Puzzle SolvedA26
- B.7 Multi-Core and Multi-Threaded ArchitecturesA27
- B.8 Hardware Synchronization InstructionsA29
- B.9 Chapter NotesA31
- B.10 ExercisesA31
- Bibliography483
- Index495
As the computer industry changes from single-processor to multiprocessor architectures, this revolution requires a fundamental change in how programs are written. To leverage the performance and power of multiprocessor programming, also known as multicore programming, you need to learn the new principles, algorithms, and tools presented in this book. It includes fully-developed Java examples detailing data structures, synchronization techniques, transactional memory, and more.
Prof. Maurice Herlihy, who coined the phrase "transactional memory," 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 Gödel Prize, the highest award in theoretical computer science.
* THE book on multicore programming, the new paradigm of computer science
* Written by the world's most revered experts in multiprocessor programming and performance
* Includes examples, models, exercises, PowerPoint slides, and sample Java programs