Herlihy / Shavit The Art of Multiprocessor Programming

1. Auflage 2011
ISBN: 978-0-08-056958-1
Verlag: Elsevier Science & Techn.
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 528 Seiten, Web PDF

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 scienceWritten by the world's most revered experts in multiprocessor programming and performanceIncludes examples, models, exercises, PowerPoint slides, and sample Java programs

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. Maurice 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, the highest award in theoretical computer science. In 2012 he shared the Edsger W. Dijkstra Prize In Distributed Computing with Nir Shavit.

Autoren/Hrsg.

Herlihy, Maurice

Shavit, Nir

Inhaltsverzeichnis

1;Front Cover;1
2;The Art of Multiprocessor Programming;4
3;Copyright Page;5
4;Table of Contents;8
5;Acknowledgments;18
6;Preface;20
7;Chapter 1. Introduction ;22
7.1;1.1 Shared Objects and Synchronization;24
7.2;1.2 A Fable;27
7.3;1.3 The Producer–Consumer Problem;31
7.4;1.4 The Readers–Writers Problem;33
7.5;1.5 The Harsh Realities of Parallelization;34
7.6;1.6 Parallel Programming;36
7.7;1.7 Chapter Notes;36
7.8;1.8 Exercises;37
8;Part I: Principles;40
8.1;Chapter 2. Mutual Exclusion;42
8.1.1;2.1 Time;42
8.1.2;2.2 Critical Sections;43
8.1.3;2.3 2-Thread Solutions;45
8.1.4;2.4 The Filter Lock;49
8.1.5;2.5 Fairness;52
8.1.6;2.6 Lamport’s Bakery Algorithm;52
8.1.7;2.7 Bounded Timestamps;54
8.1.8;2.8 Lower Bounds on the Number of Locations;58
8.1.9;2.9 Chapter Notes;61
8.1.10;2.10 Exercises;62
8.2;Chapter 3. Concurrent Objects;66
8.2.1;3.1 Concurrency and Correctness;66
8.2.2;3.2 Sequential Objects;69
8.2.3;3.3 Quiescent Consistency;70
8.2.4;3.4 Sequential Consistency;72
8.2.5;3.5 Linearizability;75
8.2.6;3.6 Formal Definitions;76
8.2.7;3.7 Progress Conditions;80
8.2.8;3.8 The Java Memory Model;82
8.2.9;3.9 Remarks;85
8.2.10;3.10 Chapter Notes;86
8.2.11;3.11 Exercises;87
8.3;Chapter 4. Foundations of Shared Memory;92
8.3.1;4.1 The Space of Registers;93
8.3.2;4.2 Register Constructions;98
8.3.3;4.3 Atomic Snapshots;108
8.3.4;4.4 Chapter Notes;114
8.3.5;4.5 Exercises;115
8.4;Chapter 5. The Relative Power of Primitive Synchronization Operations;120
8.4.1;5.1 Consensus Numbers;121
8.4.2;5.2 Atomic Registers;124
8.4.3;5.3 Consensus Protocols;127
8.4.4;5.4 FIFO Queues;127
8.4.5;5.5 Multiple Assignment Objects;131
8.4.6;5.6 Read–Modify–Write Operations;133
8.4.7;5.7 Common2 RMW Operations;135
8.4.8;5.8 The compareAndSet() Operation;137
8.4.9;5.9 Chapter Notes;138
8.4.10;5.10 Exercises;139
8.5;Chapter 6. Universality of Consensus;146
8.5.1;6.1 Introduction;146
8.5.2;6.2 Universality;147
8.5.3;6.3 A Lock-Free Universal Construction;147
8.5.4;6.4 A Wait-Free Universal Construction;151
8.5.5;6.5 Chapter Notes;157
8.5.6;6.6 Exercises;158
9;Part II: Practice;160
9.1;Chapter 7. Spin Locks and Contention;162
9.1.1;7.1 Welcome to the Real World;162
9.1.2;7.2 Test-And-Set Locks;165
9.1.3;7.3 TAS-Based Spin Locks Revisited;167
9.1.4;7.4 Exponential Backoff;168
9.1.5;7.5 Queue Locks;170
9.1.6;7.6 A Queue Lock with Timeouts;178
9.1.7;7.7 A Composite Lock;180
9.1.8;7.8 Hierarchical Locks;188
9.1.9;7.9 One Lock To Rule Them All;194
9.1.10;7.10 Chapter Notes;194
9.1.11;7.11 Exercises;195
9.2;Chapter 8. Monitors and Blocking Synchronization;198
9.2.1;8.1 Introduction;198
9.2.2;8.2 Monitor Locks and Conditions;199
9.2.3;8.3 Readers–Writers Locks;204
9.2.4;8.4 Our Own Reentrant Lock;208
9.2.5;8.5 Semaphores;210
9.2.6;8.6 Chapter Notes;210
9.2.7;8.7 Exercises;211
9.3;Chapter 9. Linked Lists: The Role of Locking;216
9.3.1;9.1 Introduction;216
9.3.2;9.2 List-Based Sets;217
9.3.3;9.3 Concurrent Reasoning;219
9.3.4;9.4 Coarse-Grained Synchronization;221
9.3.5;9.5 Fine-Grained Synchronization;222
9.3.6;9.6 Optimistic Synchronization;226
9.3.7;9.7 Lazy Synchronization;229
9.3.8;9.8 Non-Blocking Synchronization;234
9.3.9;9.9 Discussion;239
9.3.10;9.10 Chapter Notes;240
9.3.11;9.11 Exercises;240
9.4;Chapter 10. Concurrent Queues and the ABA Problem;244
9.4.1;10.1 Introduction;244
9.4.2;10.2 Queues;245
9.4.3;10.3 A Bounded Partial Queue;246
9.4.4;10.4 An Unbounded Total Queue;250
9.4.5;10.5 An Unbounded Lock-Free Queue;251
9.4.6;10.6 Memory Reclamation and the ABA Problem;254
9.4.7;10.7 Dual Data Structures;259
9.4.8;10.8 Chapter Notes;262
9.4.9;10.9 Exercises;262
9.5;Chapter 11. Concurrent Stacks and Elimination;266
9.5.1;11.1 Introduction;266
9.5.2;11.2 An Unbounded Lock-Free Stack;266
9.5.3;11.3 Elimination;269
9.5.4;11.4 The Elimination Backoff Stack;270
9.5.5;11.5 Chapter Notes;276
9.5.6;11.6 Exercises;276
9.6;Chapter 12. Counting, Sorting, and Distributed Coordination;280
9.6.1;12.1 Introduction;280
9.6.2;12.2 Shared Counting;280
9.6.3;12.3 Software Combining;281
9.6.4;12.4 Quiescently Consistent Pools and Counters;290
9.6.5;12.5 Counting Networks;291
9.6.6;12.6 Diffracting Trees;303
9.6.7;12.7 Parallel Sorting;307
9.6.8;12.8 Sorting Networks;307
9.6.9;12.9 Sample Sorting;311
9.6.10;12.10 Distributed Coordination;312
9.6.11;12.11 Chapter Notes;313
9.6.12;12.12 Exercises;314
9.7;Chapter 13. Concurrent Hashing and Natural Parallelism;320
9.7.1;13.1 Introduction;320
9.7.2;13.2 Closed-Address Hash Sets;321
9.7.3;13.3 A Lock-Free Hash Set;330
9.7.4;13.4 An Open-Addressed Hash Set;337
9.7.5;13.5 Chapter Notes;346
9.7.6;13.6 Exercises;347
9.8;Chapter 14. Skiplists and Balanced Search;350
9.8.1;14.1 Introduction;350
9.8.2;14.2 Sequential Skiplists;350
9.8.3;14.3 A Lock-Based Concurrent Skiplist;352
9.8.4;14.4 A Lock-Free Concurrent Skiplist;360
9.8.5;14.5 Concurrent Skiplists;369
9.8.6;14.6 Chapter Notes;369
9.8.7;14.7 Exercises;370
9.9;Chapter 15. Priority Queues;372
9.9.1;15.1 Introduction;372
9.9.2;15.2 An Array-Based Bounded Priority Queue;373
9.9.3;15.3 A Tree-Based Bounded Priority Queue;374
9.9.4;15.4 An Unbounded Heap-Based Priority Queue;376
9.9.5;15.5 A Skiplist-Based Unbounded Priority Queue;384
9.9.6;15.6 Chapter Notes;387
9.9.7;15.7 Exercises;387
9.10;Chapter 16. Futures, Scheduling, and Work Distribution;390
9.10.1;16.1 Introduction;390
9.10.2;16.2 Analyzing Parallelism;396
9.10.3;16.3 Realistic Multiprocessor Scheduling;399
9.10.4;16.4 Work Distribution;402
9.10.5;16.5 Work-Stealing Dequeues;403
9.10.6;16.6 Chapter Notes;413
9.10.7;16.7 Exercises;413
9.11;Chapter 17. Barriers;418
9.11.1;17.1 Introduction;418
9.11.2;17.2 Barrier Implementations;419
9.11.3;17.3 Sense-Reversing Barrier;420
9.11.4;17.4 Combining Tree Barrier;422
9.11.5;17.5 Static Tree Barrier;423
9.11.6;17.6 Termination Detecting Barriers;425
9.11.7;17.7 Chapter Notes;429
9.11.8;17.8 Exercises;430
9.12;Chapter 18. Transactional Memory;438
9.12.1;18.1 Introduction;438
9.12.2;18.2 Transactions and Atomicity;442
9.12.3;18.3 Software Transactional Memory;445
9.12.4;18.4 Hardware Transactional Memory;466
9.12.5;18.5 Chapter Notes;469
9.12.6;18.6 Exercises;470
10;Part III: Appendix;472
10.1;Appendix A. Software Basics;474
10.1.1;A.1 Introduction;474
10.1.2;A.2 Java;474
10.1.3;A.3 C#;481
10.1.4;A.4 Pthreads;485
10.1.5;A.5 Chapter Notes;487
10.2;Appendix B. Hardware Basics;490
10.2.1;B.1 Introduction (and a Puzzle);490
10.2.2;B.2 Processors and Threads;493
10.2.3;B.3 Interconnect;493
10.2.4;B.4 Memory;494
10.2.5;B.5 Caches;494
10.2.6;B.6 Cache-Conscious Programming, or the Puzzle Solved;497
10.2.7;B.7 Multi-Core and Multi-Threaded Architectures;498
10.2.8;B.8 Hardware Synchronization Instructions;500
10.2.9;B.9 Chapter Notes;502
10.2.10;B.10 Exercises;502
11;Bibliography;504
12;Index;516