Intel Threading Building Blocks: Outfitting C++ for Multi-Core Processor Parallelism

James Reinders0596514808, 9780596514808

Multi-core chips from Intel and AMD offer a dramatic boost in speed and responsiveness, and plenty of opportunities for multiprocessing on ordinary desktop computers. But they also present a challenge: More than ever, multithreading is a requirement for good performance. This guide explains how to maximize the benefits of these processors through a portable C++ library that works on Windows, Linux, Macintosh, and Unix systems. With it, you’ll learn how to use Intel Threading Building Blocks (TBB) effectively for parallel programming-without having to be a threading expert. Written by James Reinders, Chief Evangelist of Intel Software Products, and based on the experience of Intel’s developers and customers, this book explains the key tasks in multithreading and how to accomplish them with TBB in a portable and robust manner. With plenty of examples and full reference material, the book lays out common patterns of uses, reveals the gotchas in TBB, and gives important guidelines for choosing among alternatives in order to get the best performance. You’ll learn how Intel Threading Building Blocks: Enables you to specify tasks instead of threads for better portability, easier programming, more understandable source code, and better performance and scalability in general Focuses on the goal of parallelizing computationally intensive work to deliver high-level solutions Is compatible with other threading packages, and doesn’t force you to pick one package for your entire program Emphasizes scalable, data-parallel programming, which allows program performance to increase as you add processors Relies on generic programming, which enables you to write the best possible algorithms withthe fewest constraints Any C++ programmer who wants to write an application to run on a multi-core system will benefit from this book. TBB is also very approachable for a C programmer or a C++ programmer without much experience with templates. Best of all, you don’t need experience with parallel programming or multi-core processors to use this book.

---

Table of contents :
Intel Threading Building Blocks……Page 1
Table of Contents……Page 10
Foreword……Page 14
Note from the Lead Developer of Intel Threading Building Blocks……Page 16
Assumptions This Book Makes……Page 20
Contents of This Book……Page 21
Informal Class Declarations……Page 22
Using Code Examples……Page 23
Acknowledgments……Page 24
Why Threading Building Blocks?……Page 28
Benefits……Page 29
Comparison with Raw Threads and MPI……Page 31
Comparison with OpenMP……Page 32
Recursive Splitting, Task Stealing, and Algorithms……Page 33
Thinking Parallel……Page 34
Elements of Thinking Parallel……Page 35
Data Parallelism……Page 36
Pipelining (Task and Data Parallelism Together)……Page 37
Mixed Solutions……Page 38
Achieving Parallelism……Page 39
Scaling and Speedup……Page 40
Amdahl’s Law……Page 41
Gustafson’s observations regarding Amdahl’s Law……Page 43
Serial versus parallel algorithms……Page 45
What Is a Thread?……Page 46
Programming Threads……Page 47
Safety in the Presence of Concurrency……Page 48
Mutual Exclusion and Locks……Page 49
Correctness……Page 50
Patterns……Page 52
Intuition……Page 54
Basic Algorithms……Page 56
Initializing and Terminating the Library……Page 57
Loop Parallelization……Page 59
parallel_for……Page 60
Grain size……Page 63
Automatic grain size……Page 65
parallel_for with partitioner……Page 66
parallel_reduce……Page 67
Advanced example……Page 70
Advanced Topic: Other Kinds of Iteration Spaces……Page 72
parallel_scan……Page 76
Parallel_scan with partitioner……Page 78
Model Types: Splittable Ranges……Page 79
Range Concept……Page 80
blocked_range Template Class……Page 81
blocked_range2d Template Class……Page 83
Partitioner Concept……Page 85
auto_partitioner Class……Page 86
parallel_for Template Function……Page 88
parallel_reduce Template Function……Page 89
pre_scan_tag and final_scan_tag Classes……Page 90
Summary of Loops……Page 91
Parallel Algorithms for Streams……Page 92
Cook Until Done: parallel_while……Page 93
parallel_while Template Class……Page 95
Working on the Assembly Line: Pipeline……Page 96
Throughput of pipeline……Page 101
Nonlinear pipelines……Page 102
pipeline Class……Page 103
filter Class……Page 104
parallel_sort……Page 105
parallel_sort Template Function……Page 106
Containers……Page 107
concurrent_queue……Page 108
Iterating over a concurrent_queue for Debugging……Page 109
concurrent_queue Template Class……Page 110
concurrent_vector……Page 113
concurrent_vector Template Class……Page 114
Concurrent Operations……Page 115
Capacity……Page 116
Iterators……Page 117
concurrent_hash_map……Page 118
More on HashCompare……Page 120
concurrent_hash_map Template Class……Page 121
Whole-Table Operations……Page 122
const_accessor……Page 123
accessor class……Page 124
Concurrent Operations: find, insert, erase……Page 125
Capacity……Page 126
Iterators……Page 127
Problems in Memory Allocation……Page 128
Memory Allocators……Page 130
Replace malloc, free, realloc, and calloc……Page 131
Replace new and delete……Page 132
Allocator Concept……Page 133
cache_aligned_allocator Template Class……Page 134
aligned_space Template Class……Page 136
Mutual Exclusion……Page 137
When to Use Mutual Exclusion……Page 138
Mutexes……Page 139
Mutex Flavors……Page 141
Upgrade/Downgrade……Page 143
Deadlock……Page 144
Mutexes……Page 145
mutex Class……Page 146
ReaderWriterMutex Concept……Page 147
Model Types……Page 148
Atomic Operations……Page 149
Why atomic Has No Constructors……Page 152
Memory Consistency and Fences……Page 153
atomic Template Class……Page 154
Timing……Page 157
tick_count Class……Page 158
tick_count::interval_t Class……Page 159
When Task-Based Programming Is Inappropriate……Page 160
Oversubscription……Page 161
Fair Scheduling……Page 162
Load Imbalance……Page 163
Example Program for Fibonacci Numbers……Page 164
Task Scheduling Overview……Page 167
How Task Scheduling Works……Page 169
Recycling the parent as the continuation……Page 172
Recycling the parent as a child……Page 173
Continuation Passing……Page 174
Scheduler bypass……Page 176
Recycling……Page 177
Empty tasks……Page 178
Lazy copying……Page 179
task_scheduler_init Class……Page 180
task Class……Page 182
Task allocation……Page 185
Explicit task destruction……Page 187
Recycling tasks……Page 188
Task depth……Page 189
Synchronization……Page 190
Task debugging……Page 192
empty_task Class……Page 193
task_list Class……Page 194
Task Scheduler Summary……Page 195
Key Steps to Success……Page 196
Relaxed Sequential Execution……Page 197
Safe Concurrency for Methods and Libraries……Page 198
The TBB_DO_ASSERT Macro……Page 199
The TBB_DO_THREADING_TOOLS Macro……Page 200
Mixing with Other Threading Packages……Page 201
The __TBB Prefix……Page 203
The Aha! Factor……Page 204
A Few Other Key Points……Page 206
ParallelAverage……Page 207
Seismic……Page 208
Matrix Multiply……Page 210
ParallelMerge……Page 211
SubstringFinder……Page 213
The Game of Life……Page 217
Automaton……Page 219
Automata: Implementation……Page 220
Extending the Application……Page 225
ParallelSum……Page 226
ParallelPrime……Page 227
CountStrings: Using concurrent_hash_map……Page 236
Switching from an STL map……Page 238
Quicksort: Visualizing Task Stealing……Page 242
A Better Matrix Multiply (Strassen)……Page 250
Start a Large Task in Parallel with the Main Program……Page 257
Two Mouths: Feeding Two from the Same Task in a Pipeline……Page 260
Packet Processing Pipeline……Page 264
Parallel Programming for an Internet Device……Page 265
Local Network Router Example……Page 267
Network address translation (NAT)……Page 268
Our example……Page 269
The Threading Building Blocks pipeline……Page 270
Synchronization with the pipeline item and concurrent hash maps……Page 273
Filter Classes……Page 274
Class output_packet : public tbb::filter……Page 278
Class translator : public tbb::filter……Page 279
Class gateway : public tbb::filter……Page 281
Class forwarding : public tbb::filter……Page 282
Replacing new and delete……Page 284
Replacing malloc, calloc, realloc, and free……Page 287
Game Threading Example……Page 289
Threading Architecture: Physics + Rendering……Page 290
Overview of Keys to Scalability……Page 291
A Frame Loop……Page 292
Domain Decomposition Data Structure Needs……Page 293
Think Tasks, Not Threads……Page 294
Load Balancing Versus Task Stealing……Page 295
Synchronization Between Physics Threads……Page 296
Integrating the Example into a Real Game……Page 297
Physics Interaction and Update Code……Page 298
Open Dynamics Engine……Page 302
Look for Hotspots……Page 303
Improving on the First Solution……Page 305
The Code……Page 307
Libraries……Page 310
Languages……Page 312
Generic Programming……Page 313
Pseudosignatures in Generic Programming……Page 314
Models in Generic Programming……Page 315
Caches……Page 316
Costs of Time Slicing……Page 317
Quick Introduction to Lambda Functions……Page 318
Further Reading……Page 319
Index……Page 324