Is Parallel Programming Hard, And, If So, What Can You Do About It?

Cover......Page 1 Title......Page 2 Contents......Page 4 1.1 Roadmap......Page 12 1.2 Quick Quizzes......Page 13 1.3 Alternatives to This Book......Page 14 1.5 Whose Book Is This?......Page 15 2.1 Historic Parallel Programming Difficulties......Page 18 2.2.1 Performance......Page 20 2.2.2 Productivity......Page 22 2.2.3 Generality......Page 23 2.3 Alternatives to Parallel Programming......Page 25 2.3.3 Performance Optimization......Page 26 2.4 What Makes Parallel Programming Hard?......Page 27 2.4.1 Work Partitioning......Page 28 2.4.3 Resource Partitioning and Replication......Page 29 2.4.6 How Do Languages and Environments Assist With These Tasks?......Page 30 2.5 Discussion......Page 31 3.1.1 Pipelined CPUs......Page 32 3.1.2 Memory References......Page 34 3.1.3 Atomic Operations......Page 35 3.1.4 Memory Barriers......Page 36 3.1.6 I/O Operations......Page 37 3.2.1 Hardware System Architecture......Page 38 3.2.2 Costs of Operations......Page 39 3.3 Hardware Free Lunch?......Page 41 3.3.2 Novel Materials and Processes......Page 42 3.3.4 Special-Purpose Accelerators......Page 43 3.4 Software Design Implications......Page 44 4.1 Scripting Languages......Page 46 4.2.1 POSIX Process Creation and Destruction......Page 47 4.2.2 POSIX Thread Creation and Destruction......Page 49 4.2.3 POSIX Locking......Page 50 4.2.4 POSIX Reader-Writer Locking......Page 53 4.2.5 Atomic Operations (gcc Classic)......Page 56 4.2.6 Atomic Operations (C11)......Page 57 4.3.2 Thread Creation, Destruction, and Control......Page 58 4.3.3 Locking......Page 60 4.3.5 Per-CPU Variables......Page 62 4.4 The Right Tool for the Job: How to Choose?......Page 64 5 Counting......Page 66 5.1 Why Isn't Concurrent Counting Trivial?......Page 67 5.2.1 Design......Page 69 5.2.2 Array-Based Implementation......Page 70 5.2.3 Eventually Consistent Implementation......Page 71 5.2.4 Per-Thread-Variable-Based Implementation......Page 74 5.3.1 Design......Page 75 5.3.2 Simple Limit Counter Implementation......Page 76 5.3.3 Simple Limit Counter Discussion......Page 82 5.4 Exact Limit Counters......Page 83 5.4.1 Atomic Limit Counter Implementation......Page 84 5.4.3 Signal-Theft Limit Counter Design......Page 88 5.4.4 Signal-Theft Limit Counter Implementation......Page 90 5.5 Applying Specialized Parallel Counters......Page 96 5.6.1 Parallel Counting Performance......Page 97 5.6.2 Parallel Counting Specializations......Page 98 5.6.3 Parallel Counting Lessons......Page 99 6.1.1 Dining Philosophers Problem......Page 102 6.1.2 Double-Ended Queue......Page 106 6.2 Design Criteria......Page 114 6.3.1 Sequential Program......Page 117 6.3.2 Code Locking......Page 118 6.3.3 Data Locking......Page 120 6.3.4 Data Ownership......Page 122 6.3.5 Locking Granularity and Performance......Page 123 6.4 Parallel Fastpath......Page 126 6.4.2 Hierarchical Locking......Page 127 6.4.3 Resource Allocator Caches......Page 128 6.5.1 Work-Queue Parallel Maze Solver......Page 134 6.5.2 Alternative Parallel Maze Solver......Page 137 6.5.3 Performance Comparison I......Page 138 6.5.4 Alternative Sequential Maze Solver......Page 141 6.5.5 Performance Comparison II......Page 142 6.5.6 Future Directions and Conclusions......Page 143 6.6 Partitioning, Parallelism, and Optimization......Page 144 7 Locking......Page 146 7.1 Staying Alive......Page 147 7.1.1 Deadlock......Page 148 7.1.2 Livelock and Starvation......Page 156 7.1.3 Unfairness......Page 157 7.2 Types of Locks......Page 158 7.2.3 Beyond Reader-Writer Locks......Page 159 7.2.4 Scoped Locking......Page 161 7.3.1 Sample Exclusive-Locking Implementation Based on Atomic Exchange......Page 163 7.3.2 Other Exclusive-Locking Implementations......Page 164 7.4 Lock-Based Existence Guarantees......Page 166 7.5.2 Locking For Parallel Libraries: Just Another Tool......Page 168 7.5.3 Locking For Parallelizing Sequential Libraries: Villain!......Page 172 7.6 Summary......Page 174 8.1 Multiple Processes......Page 176 8.3 Function Shipping......Page 177 8.6 Other Uses of Data Ownership......Page 178 9.1 Running Example......Page 180 9.2 Reference Counting......Page 181 9.3 Hazard Pointers......Page 186 9.4 Sequence Locks......Page 189 9.5 Read-Copy Update (RCU)......Page 194 9.5.1 Introduction to RCU......Page 195 9.5.2 RCU Fundamentals......Page 198 9.5.3 RCU Usage......Page 208 9.5.4 RCU Linux-Kernel API......Page 223 9.5.5 ``Toy'' RCU Implementations......Page 229 9.5.6 RCU Exercises......Page 247 9.6 Which to Choose?......Page 248 9.7 What About Updates?......Page 249 10.1 Motivating Application......Page 252 10.2.2 Hash-Table Implementation......Page 253 10.2.3 Hash-Table Performance......Page 257 10.3 Read-Mostly Data Structures......Page 258 10.3.1 RCU-Protected Hash Table Implementation......Page 259 10.3.2 RCU-Protected Hash Table Performance......Page 260 10.3.3 RCU-Protected Hash Table Discussion......Page 263 10.4.1 Resizable Hash Table Design......Page 264 10.4.2 Resizable Hash Table Implementation......Page 266 10.4.3 Resizable Hash Table Discussion......Page 272 10.4.4 Other Resizable Hash Tables......Page 274 10.5 Other Data Structures......Page 277 10.6.2 Bits and Bytes......Page 278 10.6.3 Hardware Considerations......Page 279 10.7 Summary......Page 281 11.1 Introduction......Page 282 11.1.1 Where Do Bugs Come From?......Page 283 11.1.2 Required Mindset......Page 284 11.1.3 When Should Validation Start?......Page 285 11.1.4 The Open Source Way......Page 287 11.2 Tracing......Page 288 11.4 Static Analysis......Page 289 11.5.2 Walkthroughs......Page 290 11.5.3 Self-Inspection......Page 291 11.6 Probability and Heisenbugs......Page 293 11.6.1 Statistics for Discrete Testing......Page 294 11.6.3 Statistics for Continuous Testing......Page 296 11.6.4 Hunting Heisenbugs......Page 298 11.7 Performance Estimation......Page 301 11.7.2 Profiling......Page 302 11.7.4 Microbenchmarking......Page 303 11.7.5 Isolation......Page 304 11.7.6 Detecting Interference......Page 305 11.8 Summary......Page 308 12.1.1 Promela and Spin......Page 312 12.1.2 How to Use Promela......Page 316 12.1.3 Promela Example: Locking......Page 319 12.1.4 Promela Example: QRCU......Page 321 12.1.5 Promela Parable: dynticks and Preemptible RCU......Page 328 12.1.6 Validating Preemptible RCU and dynticks......Page 333 12.2 Special-Purpose State-Space Search......Page 353 12.2.1 Anatomy of a Litmus Test......Page 354 12.2.2 What Does This Litmus Test Mean?......Page 355 12.2.3 Running a Litmus Test......Page 356 12.2.4 PPCMEM Discussion......Page 357 12.3 Axiomatic Approaches......Page 358 12.5 Summary......Page 360 13.1.2 Counting Lookups......Page 364 13.2 Refurbish Reference Counting......Page 365 13.2.1 Implementation of Reference-Counting Categories......Page 366 13.2.2 Linux Primitives Supporting Reference Counting......Page 371 13.3 RCU Rescues......Page 372 13.3.1 RCU and Per-Thread-Variable-Based Statistical Counters......Page 373 13.3.2 RCU and Counters for Removable I/O Devices......Page 375 13.3.3 Array and Length......Page 376 13.3.4 Correlated Fields......Page 377 13.4.1 Correlated Data Elements......Page 378 13.4.2 Update-Friendly Hash-Table Traversal......Page 379 14.1 Avoiding Locks......Page 380 14.2.1 Memory Ordering and Memory Barriers......Page 381 14.2.2 If B Follows A, and C Follows B, Why Doesn't C Follow A?......Page 382 14.2.3 Variables Can Have More Than One Value......Page 384 14.2.4 What Can You Trust?......Page 385 14.2.6 A Few Simple Rules......Page 393 14.2.7 Abstract Memory Access Model......Page 394 14.2.8 Device Operations......Page 395 14.2.9 Guarantees......Page 396 14.2.10 What Are Memory Barriers?......Page 397 14.2.11 Locking Constraints......Page 410 14.2.12 Memory-Barrier Examples......Page 411 14.2.13 The Effects of the CPU Cache......Page 413 14.3 Non-Blocking Synchronization......Page 415 14.3.1 Simple NBS......Page 417 14.3.2 NBS Discussion......Page 418 15.1.1 Soft Real Time......Page 420 15.1.2 Hard Real Time......Page 421 15.1.3 Real-World Real Time......Page 422 15.2 Who Needs Real-Time Computing?......Page 426 15.3 Who Needs Parallel Real-Time Computing?......Page 427 15.4 Implementing Parallel Real-Time Systems......Page 428 15.4.1 Implementing Parallel Real-Time Operating Systems......Page 429 15.4.2 Implementing Parallel Real-Time Applications......Page 442 15.4.3 The Role of RCU......Page 445 15.5 Real Time vs. Real Fast: How to Choose?......Page 446 16.2 Rusty Scale for API Design......Page 448 16.3 Shaving the Mandelbrot Set......Page 450 17.1.1 Uniprocessor Über Alles......Page 452 17.1.2 Multithreaded Mania......Page 453 17.1.3 More of the Same......Page 454 17.1.4 Crash Dummies Slamming into the Memory Wall......Page 455 17.2.1 Outside World......Page 458 17.2.2 Process Modification......Page 462 17.2.3 Synchronization......Page 467 17.2.4 Discussion......Page 471 17.3 Hardware Transactional Memory......Page 473 17.3.1 HTM Benefits WRT to Locking......Page 474 17.3.2 HTM Weaknesses WRT Locking......Page 476 17.3.3 HTM Weaknesses WRT to Locking When Augmented......Page 482 17.3.4 Where Does HTM Best Fit In?......Page 485 17.3.5 Potential Game Changers......Page 486 17.3.6 Conclusions......Page 488 17.4 Functional Programming for Parallelism......Page 489 A.1 What Does ``After'' Mean?......Page 492 A.2 What is the Difference Between ``Concurrent'' and ``Parallel''?......Page 495 A.3 What Time Is It?......Page 496 B.1 Cache Structure......Page 498 B.2 Cache-Coherence Protocols......Page 500 B.2.2 MESI Protocol Messages......Page 501 B.2.3 MESI State Diagram......Page 502 B.2.4 MESI Protocol Example......Page 504 B.3.1 Store Buffers......Page 505 B.3.2 Store Forwarding......Page 506 B.3.3 Store Buffers and Memory Barriers......Page 507 B.4.1 Invalidate Queues......Page 510 B.4.3 Invalidate Queues and Memory Barriers......Page 511 B.5 Read and Write Memory Barriers......Page 514 B.6.1 Ordering-Hostile Architecture......Page 515 B.6.3 Example 2......Page 516 B.6.4 Example 3......Page 517 B.7 Memory-Barrier Instructions For Specific CPUs......Page 518 B.7.1 Alpha......Page 520 B.7.3 ARMv7-A/R......Page 522 B.7.4 IA64......Page 523 B.7.5 MIPS......Page 524 B.7.7 POWER / PowerPC......Page 525 B.7.8 SPARC RMO, PSO, and TSO......Page 526 B.7.9 x86......Page 527 B.8 Are Memory Barriers Forever?......Page 528 B.9 Advice to Hardware Designers......Page 529 C.1 How To Use This Book......Page 532 C.2 Introduction......Page 533 C.3 Hardware and its Habits......Page 539 C.4 Tools of the Trade......Page 543 C.5 Counting......Page 551 C.6 Partitioning and Synchronization Design......Page 571 C.7 Locking......Page 577 C.8 Data Ownership......Page 587 C.9 Deferred Processing......Page 590 C.10 Data Structures......Page 614 C.11 Validation......Page 618 C.12 Formal Verification......Page 625 C.13 Putting It All Together......Page 632 C.14 Advanced Synchronization......Page 636 C.15 Parallel Real-Time Computing......Page 641 C.16 Ease of Use......Page 643 C.17 Conflicting Visions of the Future......Page 644 C.18 Important Questions......Page 648 C.19 Why Memory Barriers?......Page 649 D Glossary and Bibliography......Page 654 E.2 Reviewers......Page 690 E.5 Figure Credits......Page 691 E.6 Other Support......Page 693 Back......Page 694