Pro Tbb: C++ Parallel Programming with Threading Building Blocks

Description

This open access book is a modern guide for all C++ programmers to learn Threading Building Blocks (TBB). Written by TBB and parallel programming experts, this book reflects their collective decades of experience in developing and teaching parallel programming with TBB, offering their insights in an approachable manner. Throughout the book the authors present numerous examples and best practices to help you become an effective TBB programmer and leverage the power of parallel systems. Pro TBBstarts with the basics, explaining parallel algorithms and C++'s built-in standard template library for parallelism. You'll learn the key concepts of managing memory, working with data structures and how to handle typical issues with synchronization. Later chapters apply these ideas to complex systems to explain performance tradeoffs, mapping common parallel patterns, controlling threads and overhead, and extending TBB to program heterogeneous systems or system-on-chips. What You'll Learn Use Threading Building Blocks to produce code that is portable, simple, scalable, and more understandable Review best practices for parallelizing computationally intensive tasks in your applications Integrate TBB with other threading packages Create scalable, high performance data-parallel programs Work with generic programming to write efficient algorithms Who This Book Is For C++ programmers learning to run applications on multicore systems, as well as C or C++ programmers without much experience with templates. No previous experience with parallel programming or multicore processors is required. Table of Contents......Page 4 About the Authors......Page 15 Acknowledgments......Page 17 Preface......Page 19 Part 1......Page 67 Why Threading Building Blocks?......Page 68 Performance: Small Overhead, Big Benefits for C++......Page 69 Evolving Support for Parallelism in TBB and C++......Page 70 Recent C++ Additions for Parallelism......Page 71 The Threading Building Blocks (TBB) Library......Page 72 Parallel Execution Interfaces......Page 73 Using the Building Blocks in TBB......Page 75 Getting the Threading Building Blocks (TBB) Library......Page 76 Writing a First “Hello, TBB!” Example......Page 77 Steps to Set Up an Environment......Page 80 Building on Windows Using Microsoft Visual Studio......Page 81 tbbvars and pstlvars Scripts......Page 82 Setting Up Variables Manually Without Using the tbbvars Script or the Intel Compiler......Page 84 Starting with a Serial Implementation......Page 86 Adding a Message-Driven Layer Using a Flow Graph......Page 90 Adding a Fork-Join Layer Using a parallel_for......Page 92 Adding a SIMD Layer Using a Parallel STL Transform......Page 94 Summary......Page 96 Chapter 2: Generic Parallel Algorithms......Page 97 Functional / Task Parallelism......Page 101 A Slightly More Complicated Example: A Parallel Implementation of Quicksort......Page 104 parallel_for: Applying a Body to Each Element in a Range......Page 106 A Slightly More Complicated Example: Parallel Matrix Multiplication......Page 108 parallel_reduce: Calculating a Single Result Across a Range......Page 110 þÿ......Page 115 parallel_scan: A Reduction with Intermediate Values......Page 116 How Does This Work?......Page 118 A Slightly More Complicated Example: Line of Sight......Page 120 Cook Until Done: parallel_do and parallel_pipeline......Page 121 parallel_do: Apply a Body Until There Are No More Items Left......Page 122 A Slightly More Complicated Example: Forward Substitution......Page 126 parallel_pipeline: Streaming Items Through a Series of Filters......Page 131 A Slightly More Complicated Example: Creating 3D Stereoscopic Images......Page 136 For More Information......Page 140 Chapter 3: Flow Graphs......Page 143 Why Use Graphs to Express Parallelism?......Page 144 The Basics of the TBB Flow Graph Interface......Page 146 Step 2: Make the Nodes......Page 148 Step 3: Add Edges......Page 151 Step 4: Start the Graph......Page 153 A More Complicated Example of a Data Flow Graph......Page 155 Implementing the Example as a TBB Flow Graph......Page 157 Understanding the Performance of a Data Flow Graph......Page 160 The Special Case of Dependency Graphs......Page 161 Implementing a Dependency Graph......Page 163 Estimating the Scalability of a Dependency Graph......Page 169 Summary......Page 170 Chapter 4: TBB and the Parallel Algorithms of the C++ Standard Template Library......Page 172 Does the C++ STL Library Belong in This Book?......Page 173 A Parallel STL Execution Policy Analogy......Page 175 A Simple Example Using std::for_each......Page 176 How to Get and Use a Copy of Parallel STL That Uses TBB......Page 180 Algorithms in Intel’s Parallel STL......Page 181 Capturing More Use Cases with Custom Iterators......Page 183 std::for_each, std::for_each_n......Page 187 std::transform......Page 189 std::reduce......Page 190 std::transform_reduce......Page 191 A Deeper Dive into the Execution Policies......Page 193 The parallel_policy......Page 194 Which Execution Policy Should We Use?......Page 195 Other Ways to Introduce SIMD Parallelism......Page 197 For More Information......Page 198 Chapter 5: Synchronization: Why and How to Avoid It......Page 200 A Running Example: Histogram of an Image......Page 201 An Unsafe Parallel Implementation......Page 204 A First Safe Parallel Implementation: Coarse-Grained Locking......Page 208 Mutex Flavors......Page 214 A Second Safe Parallel Implementation: Fine-Grained Locking......Page 216 A Third Safe Parallel Implementation: Atomics......Page 221 A Better Parallel Implementation: Privatization and Reduction......Page 226 Thread Local Storage, TLS......Page 227 enumerable_thread_specific, ETS......Page 228 combinable......Page 231 The Easiest Parallel Implementation: Reduction Template......Page 233 Recap of Our Options......Page 235 Summary......Page 240 For More Information......Page 241 Chapter 6: Data Structures for Concurrency......Page 242 Unordered Associative Containers......Page 243 Hashing......Page 244 Concurrent Containers......Page 245 Concurrent Unordered Associative Containers......Page 248 concurrent_hash_map......Page 249 Concurrent Support for map/multimap and set/multiset Interfaces......Page 254 Iterating Through These Structures Is Asking for Trouble......Page 255 Concurrent Queues: Regular, Bounded, and Priority......Page 256 Bounding Size......Page 260 Staying Thread-Safe: Try to Forget About Top, Size, Empty, Front, Back......Page 261 Iterators......Page 262 Why to Use This Concurrent Queue: The A-B-A Problem......Page 263 When to Use tbb::concurrent_vector Instead of std::vector......Page 265 Concurrent Growth of concurrent_vectors......Page 267 Summary......Page 268 Chapter 7: Scalable Memory Allocation......Page 270 Modern C++ Memory Allocation......Page 271 Scalable Memory Allocation: Why......Page 272 Avoiding False Sharing with Padding......Page 273 Scalable Memory Allocation Alternatives: Which......Page 275 Most Popular Usage (C/C++ Proxy Library): How......Page 277 macOS: malloc/new Proxy Library Usage......Page 279 Windows: malloc/new Proxy Library Usage......Page 280 Testing our Proxy Library Usage......Page 281 C Functions: Scalable Memory Allocators for C......Page 283 C++ Classes: Scalable Memory Allocators for C++......Page 284 tbb_allocator......Page 285 Memory Pool Support: memory_pool_allocator......Page 286 Replacing new and delete Selectively......Page 287 TBB Support for Huge Pages......Page 291 TBBMALLOC_USE_HUGE_PAGES......Page 292 TBBMALLOC_CLEAN_THREAD_BUFFERS......Page 293 Summary......Page 294 Parallel Patterns vs. Parallel Algorithms......Page 295 Patterns Categorize Algorithms, Designs, etc.......Page 297 Patterns That Work......Page 298 Data Parallelism Wins......Page 299 Nesting Pattern......Page 300 Map Pattern......Page 301 Workpile Pattern......Page 302 Reduction Patterns (Reduce and Scan)......Page 303 Fork-Join Pattern......Page 305 Branch-and-Bound Pattern......Page 306 Pipeline Pattern......Page 308 For More Information......Page 309 Part 2......Page 311 Chapter 9: The Pillars of Composability......Page 312 What Is Composability?......Page 314 Nested Composition......Page 315 Concurrent Composition......Page 317 Serial Composition......Page 319 The Features That Make TBB a Composable Library......Page 320 The TBB Thread Pool (the Market) and Task Arenas......Page 321 The TBB Task Dispatcher: Work Stealing and More......Page 324 Putting It All Together......Page 331 Work Isolation......Page 335 Summary......Page 336 For More Information......Page 337 Chapter 10: Using Tasks to Create Your Own Algorithms......Page 338 A Running Example: The Sequence......Page 339 The High-Level Approach: parallel_invoke......Page 341 The Highest Among the Lower: task_group......Page 343 The Low-Level Task Interface: Part One – Task Blocking......Page 345 The Low-Level Task Interface: Part Two – Task Continuation......Page 351 The Low-Level Task Interface: Part Three – Task Recycling......Page 358 Task Interface Checklist......Page 361 One More Thing: FIFO (aka Fire-and-Forget) Tasks......Page 362 Putting These Low-Level Features to Work......Page 363 For More Information......Page 371 Chapter 11: Controlling the Number of Threads Used for Execution......Page 373 A Brief Recap of the TBB Scheduler Architecture......Page 374 Controlling Thread Count with task_scheduler_init......Page 375 Controlling Thread Count with task_arena......Page 376 Summary of Concepts and Classes......Page 378 Using a Single task_scheduler_init Object for a Simple Application......Page 380 Using More Than One task_scheduler_init Object in a Simple Application......Page 383 Using Multiple Arenas with Different Numbers of Slots to Influence Where TBB Places Its Worker Threads......Page 385 Using global_control to Control How Many Threads Are Available to Fill Arena Slots......Page 389 Using global_control to Temporarily Restrict the Number of Available Threads......Page 390 When NOT to Control the Number of Threads......Page 392 Figuring Out Whats Gone Wrong......Page 394 Summary......Page 395 Chapter 12: Using Work Isolation for Correctness and Performance......Page 397 Work Isolation for Correctness......Page 398 Creating an Isolated Region with this_task_arena::isolate......Page 403 Oh No! Work Isolation Can Cause Its Own Correctness Issues!......Page 405 Using Task Arenas for Isolation: A Double-Edged Sword......Page 409 Don’t Be Tempted to Use task_arenas to Create Work Isolation for Correctness......Page 413 Summary......Page 415 For More Information......Page 416 Chapter 13: Creating Thread-to-Core and Task-to-Thread Affinity......Page 417 Creating Thread-to-Core Affinity......Page 418 Creating Task-to-Thread Affinity......Page 422 Summary......Page 430 For More Information......Page 431 Chapter 14: Using Task Priorities......Page 432 Support for Non-Preemptive Priorities in the TBB Task Class......Page 433 Setting Static and Dynamic Priorities......Page 435 Two Small Examples......Page 436 Implementing Priorities Without Using TBB Task Support......Page 441 Summary......Page 443 For More Information......Page 444 Chapter 15: Cancellation and Exception Handling......Page 445 How to Cancel Collective Work......Page 446 Advanced Task Cancellation......Page 448 Explicit Assignment of TGC......Page 450 Default Assignment of TGC......Page 453 Exception Handling in TBB......Page 457 Tailoring Our Own TBB Exceptions......Page 460 Putting All Together: Composability, Cancellation, and Exception Handling......Page 463 For More Information......Page 467 Chapter 16: Tuning TBB Algorithms: Granularity, Locality, Parallelism, and Determinism......Page 469 Task Granularity: How Big Is Big Enough?......Page 470 Choosing Ranges and Partitioners for Loops......Page 471 An Overview of Partitioners......Page 473 Choosing a Grainsize (or Not) to Manage Task Granularity......Page 475 Cache-Oblivious Algorithms......Page 478 Cache Affinity......Page 485 Using a static_partitioner......Page 486 Restricting the Scheduler for Determinism......Page 489 Tuning TBB Pipelines: Number of Filters, Modes, and Tokens......Page 491 Understanding a Balanced Pipeline......Page 492 Understanding an Imbalanced Pipeline......Page 494 Pipelines and Data Locality and Thread Affinity......Page 496 Making Your Own Range Type......Page 497 The Pipeline Class and Thread-Bound Filters......Page 500 Summary......Page 505 For More Information......Page 506 Chapter 17: Flow Graphs: Beyond the Basics......Page 508 Node Granularity: How Big Is Big Enough?......Page 509 What to Do If Nodes Are Too Small......Page 516 Data Locality in Flow Graphs......Page 519 Picking the Best Message Type and Limiting the Number of Messages in Flight......Page 525 The Default Arena Used by a Flow Graph......Page 534 Changing the Task Arena Used by a Flow Graph......Page 535 Do: Use Nested Parallelism......Page 537 Do: Use join_node, sequencer_node, or multifunction_node to Reestablish Order in a Flow Graph When Needed......Page 538 Do: Use the Isolate Function for Nested Parallelism......Page 542 Canceling a Flow Graph......Page 545 Exception Handling Examples......Page 546 Don’t: Make an Edge Between Nodes in Different Graphs......Page 549 Do: Use try_put to Communicate Across Graphs......Page 552 Do: Use composite_node to Encapsulate Groups of Nodes......Page 554 Introducing Intel Advisor: Flow Graph Analyzer......Page 558 The FGA Design Workflow......Page 559 Tips for Iterative Development with FGA......Page 560 The FGA Analysis Workflow......Page 562 Diagnosing Granularity Issues with FGA......Page 564 Recognizing Slow Copies in FGA......Page 565 Diagnosing Moonlighting using FGA......Page 566 Summary......Page 567 For More Information......Page 568 Chapter 18: Beef Up Flow Graphs with Async Nodes......Page 569 Async World Example......Page 570 Why and When async_node?......Page 575 A More Realistic Example......Page 577 For More Information......Page 589 Chapter 19: Flow Graphs on Steroids: OpenCL Nodes......Page 591 Hello OpenCL_Node Example......Page 592 Where Are We Running Our Kernel?......Page 600 Back to the More Realistic Example of Chapter 18......Page 607 The Devil Is in the Details......Page 617 The NDRange Concept......Page 618 Playing with the Offset......Page 624 Specifying the OpenCL Kernel......Page 625 Even More on Device Selection......Page 626 A Warning Regarding the Order Is in Order!......Page 630 Summary......Page 634 For More Information......Page 635 Chapter 20: TBB on NUMA Architectures......Page 636 Discovering Your Platform Topology......Page 638 Understanding the Costs of Accessing Memory......Page 642 Our Baseline Example......Page 643 Mastering Data Placement and Processor Affinity......Page 644 Putting hwloc and TBB to Work Together......Page 650 More Advanced Alternatives......Page 656 For More Information......Page 658 #1 TBBs Revolution Inside Intel......Page 660 #2 TBB’s First Revolution of Parallelism......Page 661 #3 TBB’s Second Revolution of Parallelism......Page 662 #4 TBBs Birds......Page 663 Inspiration for TBB......Page 666 Relaxed Sequential Execution Model......Page 667 Influential Libraries......Page 668 Influential Languages......Page 669 Influences of Generic Programming......Page 670 Considering Caches......Page 671 Considering Costs of Time Slicing......Page 672 Further Reading......Page 673 Appendix B:TBB Précis......Page 677 Debug and Conditional Coding......Page 678 Ranges......Page 680 Partitioners......Page 681 Algorithms......Page 682 Algorithm: parallel_do......Page 683 Algorithm: parallel_for......Page 685 Algorithm: parallel_for_each......Page 689 Algorithm: parallel_invoke......Page 690 Algorithm: parallel_pipeline......Page 692 Algorithm: parallel_reduce and parallel_deterministic_reduce......Page 695 Algorithm: parallel_scan......Page 699 Algorithm: parallel_sort......Page 702 Algorithm: pipeline......Page 705 Flow Graph......Page 707 Flow Graph: graph class......Page 708 Flow Graph: nodes......Page 709 tbb::flow::tuple vs. std::tuple......Page 710 Graph Policy (namespace)......Page 716 Memory Allocation......Page 721 Containers......Page 727 Synchronization......Page 747 Thread Local Storage (TLS)......Page 753 Timing......Page 762 Task Groups: Use of the Task Stealing Scheduler......Page 763 Task Scheduler: Fine Control of the Task Stealing Scheduler......Page 764 Floating-Point Settings......Page 775 Exceptions......Page 777 Threads......Page 779 Parallel STL......Page 780 Glossary......Page 783 Index......Page 798