Art of Multiprocessor Programming (eBook)

Maurice Herlihy, Nir Shavit (Autoren)

eBook Download: PDF

2011 | 1. Auflage
528 Seiten
Elsevier Science (Verlag)
978-0-08-056958-1 (ISBN)

Infos

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

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.

---

The Art of Multiprocessor Programming promises to be the first comprehensive presentation of the principles and tools available for programming multiprocessor machines. 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, programmers need to learn the new principles, algorithms, and tools. The book will be 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. This book includes fully-developed Java examples detailing data structures, synchronization techniques, transactional memory, and more. Students in multiprocessor and multicore programming courses and engineers working with multiprocessor and multicore systems will find this book quite useful. 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

Inhalt

Front Cover 1
The Art of Multiprocessor Programming 4
Copyright Page 5
Table of Contents 8
Acknowledgments 18
Preface 20
Chapter 1. Introduction 22
1.1 Shared Objects and Synchronization 24
1.2 A Fable 27
1.3 The Producer–Consumer Problem 31
1.4 The Readers–Writers Problem 33
1.5 The Harsh Realities of Parallelization 34
1.6 Parallel Programming 36
1.7 Chapter Notes 36
1.8 Exercises 37
Part I: Principles 40
Chapter 2. Mutual Exclusion 42
2.1 Time 42
2.2 Critical Sections 43
2.3 2-Thread Solutions 45
2.4 The Filter Lock 49
2.5 Fairness 52
2.6 Lamport’s Bakery Algorithm 52
2.7 Bounded Timestamps 54
2.8 Lower Bounds on the Number of Locations 58
2.9 Chapter Notes 61
2.10 Exercises 62
Chapter 3. Concurrent Objects 66
3.1 Concurrency and Correctness 66
3.2 Sequential Objects 69
3.3 Quiescent Consistency 70
3.4 Sequential Consistency 72
3.5 Linearizability 75
3.6 Formal Definitions 76
3.7 Progress Conditions 80
3.8 The Java Memory Model 82
3.9 Remarks 85
3.10 Chapter Notes 86
3.11 Exercises 87
Chapter 4. Foundations of Shared Memory 92
4.1 The Space of Registers 93
4.2 Register Constructions 98
4.3 Atomic Snapshots 108
4.4 Chapter Notes 114
4.5 Exercises 115
Chapter 5. The Relative Power of Primitive Synchronization Operations 120
5.1 Consensus Numbers 121
5.2 Atomic Registers 124
5.3 Consensus Protocols 127
5.4 FIFO Queues 127
5.5 Multiple Assignment Objects 131
5.6 Read–Modify–Write Operations 133
5.7 Common2 RMW Operations 135
5.8 The compareAndSet() Operation 137
5.9 Chapter Notes 138
5.10 Exercises 139
Chapter 6. Universality of Consensus 146
6.1 Introduction 146
6.2 Universality 147
6.3 A Lock-Free Universal Construction 147
6.4 A Wait-Free Universal Construction 151
6.5 Chapter Notes 157
6.6 Exercises 158
Part II: Practice 160
Chapter 7. Spin Locks and Contention 162
7.1 Welcome to the Real World 162
7.2 Test-And-Set Locks 165
7.3 TAS-Based Spin Locks Revisited 167
7.4 Exponential Backoff 168
7.5 Queue Locks 170
7.6 A Queue Lock with Timeouts 178
7.7 A Composite Lock 180
7.8 Hierarchical Locks 188
7.9 One Lock To Rule Them All 194
7.10 Chapter Notes 194
7.11 Exercises 195
Chapter 8. Monitors and Blocking Synchronization 198
8.1 Introduction 198
8.2 Monitor Locks and Conditions 199
8.3 Readers–Writers Locks 204
8.4 Our Own Reentrant Lock 208
8.5 Semaphores 210
8.6 Chapter Notes 210
8.7 Exercises 211
Chapter 9. Linked Lists: The Role of Locking 216
9.1 Introduction 216
9.2 List-Based Sets 217
9.3 Concurrent Reasoning 219
9.4 Coarse-Grained Synchronization 221
9.5 Fine-Grained Synchronization 222
9.6 Optimistic Synchronization 226
9.7 Lazy Synchronization 229
9.8 Non-Blocking Synchronization 234
9.9 Discussion 239
9.10 Chapter Notes 240
9.11 Exercises 240
Chapter 10. Concurrent Queues and the ABA Problem 244
10.1 Introduction 244
10.2 Queues 245
10.3 A Bounded Partial Queue 246
10.4 An Unbounded Total Queue 250
10.5 An Unbounded Lock-Free Queue 251
10.6 Memory Reclamation and the ABA Problem 254
10.7 Dual Data Structures 259
10.8 Chapter Notes 262
10.9 Exercises 262
Chapter 11. Concurrent Stacks and Elimination 266
11.1 Introduction 266
11.2 An Unbounded Lock-Free Stack 266
11.3 Elimination 269
11.4 The Elimination Backoff Stack 270
11.5 Chapter Notes 276
11.6 Exercises 276
Chapter 12. Counting, Sorting, and Distributed Coordination 280
12.1 Introduction 280
12.2 Shared Counting 280
12.3 Software Combining 281
12.4 Quiescently Consistent Pools and Counters 290
12.5 Counting Networks 291
12.6 Diffracting Trees 303
12.7 Parallel Sorting 307
12.8 Sorting Networks 307
12.9 Sample Sorting 311
12.10 Distributed Coordination 312
12.11 Chapter Notes 313
12.12 Exercises 314
Chapter 13. Concurrent Hashing and Natural Parallelism 320
13.1 Introduction 320
13.2 Closed-Address Hash Sets 321
13.3 A Lock-Free Hash Set 330
13.4 An Open-Addressed Hash Set 337
13.5 Chapter Notes 346
13.6 Exercises 347
Chapter 14. Skiplists and Balanced Search 350
14.1 Introduction 350
14.2 Sequential Skiplists 350
14.3 A Lock-Based Concurrent Skiplist 352
14.4 A Lock-Free Concurrent Skiplist 360
14.5 Concurrent Skiplists 369
14.6 Chapter Notes 369
14.7 Exercises 370
Chapter 15. Priority Queues 372
15.1 Introduction 372
15.2 An Array-Based Bounded Priority Queue 373
15.3 A Tree-Based Bounded Priority Queue 374
15.4 An Unbounded Heap-Based Priority Queue 376
15.5 A Skiplist-Based Unbounded Priority Queue 384
15.6 Chapter Notes 387
15.7 Exercises 387
Chapter 16. Futures, Scheduling, and Work Distribution 390
16.1 Introduction 390
16.2 Analyzing Parallelism 396
16.3 Realistic Multiprocessor Scheduling 399
16.4 Work Distribution 402
16.5 Work-Stealing Dequeues 403
16.6 Chapter Notes 413
16.7 Exercises 413
Chapter 17. Barriers 418
17.1 Introduction 418
17.2 Barrier Implementations 419
17.3 Sense-Reversing Barrier 420
17.4 Combining Tree Barrier 422
17.5 Static Tree Barrier 423
17.6 Termination Detecting Barriers 425
17.7 Chapter Notes 429
17.8 Exercises 430
Chapter 18. Transactional Memory 438
18.1 Introduction 438
18.2 Transactions and Atomicity 442
18.3 Software Transactional Memory 445
18.4 Hardware Transactional Memory 466
18.5 Chapter Notes 469
18.6 Exercises 470
Part III: Appendix 472
Appendix A. Software Basics 474
A.1 Introduction 474
A.2 Java 474
A.3 C# 481
A.4 Pthreads 485
A.5 Chapter Notes 487
Appendix B. Hardware Basics 490
B.1 Introduction (and a Puzzle) 490
B.2 Processors and Threads 493
B.3 Interconnect 493
B.4 Memory 494
B.5 Caches 494
B.6 Cache-Conscious Programming, or the Puzzle Solved 497
B.7 Multi-Core and Multi-Threaded Architectures 498
B.8 Hardware Synchronization Instructions 500
B.9 Chapter Notes 502
B.10 Exercises 502
Bibliography 504
Index 516

Produkt-Details

• Erscheint lt. Verlag: 29.8.2011
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Mathematik / Informatik ► Informatik ► Software Entwicklung
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Informatik ► Weitere Themen ► Hardware
• ISBN-10: 0-08-056958-7 / 0080569587
• ISBN-13: 978-0-08-056958-1 / 9780080569581