Multicore Application Programming: for Windows, Linux, and Oracle Solaris (Developer's Library)

Contents......Page 7
Preface......Page 15
Acknowledgments......Page 19
About the Author......Page 21
Examining the Insides of a Computer......Page 23
The Motivation for Multicore Processors......Page 25
Supporting Multiple Threads on a Single Chip......Page 26
Increasing Instruction Issue Rate with Pipelined Processor Cores......Page 31
Using Caches to Hold Recently Used Data......Page 34
Using Virtual Memory to Store Data......Page 37
Translating from Virtual Addresses to Physical Addresses......Page 38
The Characteristics of Multiprocessor Systems......Page 40
How Latency and Bandwidth Impact Performance......Page 42
The Translation of Source Code to Assembly Language......Page 43
The Performance of 32-Bit versus 64-Bit Code......Page 45
Ensuring the Correct Order of Memory Operations......Page 46
The Differences Between Processes and Threads......Page 48
Summary......Page 51
Defining Performance......Page 53
Examples of Algorithmic Complexity......Page 55
Why Algorithmic Complexity Is Important......Page 59
Using Algorithmic Complexity with Care......Page 60
Performance and Convenience Trade-Offs in Source Code and Build Structures......Page 61
Using Libraries to Structure Applications......Page 64
The Impact of Data Structures on Performance......Page 75
The Role of the Compiler......Page 82
The Two Types of Compiler Optimization......Page 84
Selecting Appropriate Compiler Options......Page 86
How Cross-File Optimization Can Be Used to Improve Performance......Page 87
Using Profile Feedback......Page 90
How Potential Pointer Aliasing Can Inhibit Compiler Optimizations......Page 92
Identifying Where Time Is Spent Using Profiling......Page 96
Commonly Available Profiling Tools......Page 97
How Not to Optimize......Page 102
Performance by Design......Page 104
Summary......Page 105
Using Multiple Processes to Improve System Productivity......Page 107
Multiple Users Utilizing a Single System......Page 109
Improving Machine Efficiency Through Consolidation......Page 110
Hosting Multiple Operating Systems Using Hypervisors......Page 111
One Approach to Visualizing Parallel Applications......Page 114
How Parallelism Can Change the Choice of Algorithms......Page 115
Amdahl’s Law......Page 116
Determining the Maximum Practical Threads......Page 119
How Synchronization Costs Reduce Scaling......Page 120
Parallelization Patterns......Page 122
Data Parallelism Using SIMD Instructions......Page 123
Multiple Independent Tasks......Page 124
Multiple Loosely Coupled Tasks......Page 125
Multiple Copies of the Same Task......Page 127
Using a Pipeline of Tasks to Work on a Single Item......Page 128
Division of Work into a Client and a Server......Page 130
Combining Parallelization Strategies......Page 131
How Dependencies Influence the Ability Run Code in Parallel......Page 132
Antidependencies and Output Dependencies......Page 133
Using Speculation to Break Dependencies......Page 135
Critical Paths......Page 139
Identifying Parallelization Opportunities......Page 140
Summary......Page 141
Data Races......Page 143
Using Tools to Detect Data Races......Page 145
Mutexes and Critical Regions......Page 148
Semaphores......Page 150
Readers-Writer Locks......Page 151
Atomic Operations and Lock-Free Code......Page 152
Deadlocks and Livelocks......Page 154
Communication Between Threads and Processes......Page 155
Memory, Shared Memory, and Memory-Mapped Files......Page 156
Condition Variables......Page 157
Signals and Events......Page 159
Message Queues......Page 160
Communication Through the Network Stack......Page 161
Other Approaches to Sharing Data Between Threads......Page 162
Storing Thread-Private Data......Page 163
Summary......Page 164
Creating Threads......Page 165
Thread Termination......Page 166
Passing Data to and from Child Threads......Page 167
Detached Threads......Page 169
Setting the Attributes for Pthreads......Page 170
Compiling Multithreaded Code......Page 173
Process Termination......Page 175
Protecting Access Using Mutex Locks......Page 176
Mutex Attributes......Page 178
Using Spin Locks......Page 179
Read-Write Locks......Page 181
Barriers......Page 184
Semaphores......Page 185
Condition Variables......Page 192
Variables and Memory......Page 197
Multiprocess Programming......Page 201
Sharing Memory Between Processes......Page 202
Sharing Semaphores Between Processes......Page 205
Message Queues......Page 206
Pipes and Named Pipes......Page 208
Using Signals to Communicate with a Process......Page 210
Sockets......Page 215
Reentrant Code and Compiler Flags......Page 219
Summary......Page 220
Creating Native Windows Threads......Page 221
Terminating Threads......Page 226
Using Handles to Kernel Resources......Page 229
Methods of Synchronization and Resource Sharing......Page 230
An Example of Requiring Synchronization Between Threads......Page 231
Protecting Access to Code with Critical Sections......Page 232
Protecting Regions of Code with Mutexes......Page 235
Slim Reader/Writer Locks......Page 236
Semaphores......Page 238
Condition Variables......Page 240
Signaling Event Completion to Other Threads or Processes......Page 241
Wide String Handling in Windows......Page 243
Creating Processes......Page 244
Sharing Memory Between Processes......Page 247
Inheriting Handles in Child Processes......Page 250
Naming Mutexes and Sharing Them Between Processes......Page 251
Communicating with Pipes......Page 253
Communicating Using Sockets......Page 256
Atomic Updates of Variables......Page 260
Allocating Thread-Local Storage......Page 262
Setting Thread Priority......Page 264
Summary......Page 266
Using Automatic Parallelization to Produce a Parallel Application......Page 267
Identifying and Parallelizing Reductions......Page 272
Automatic Parallelization of Codes Containing Calls......Page 273
Assisting Compiler in Automatically Parallelizing Code......Page 276
Using OpenMP to Produce a Parallel Application......Page 278
Runtime Behavior of an OpenMP Application......Page 280
Variable Scoping Inside OpenMP Parallel Regions......Page 281
Parallelizing Reductions Using OpenMP......Page 282
Accessing Private Data Outside the Parallel Region......Page 283
Improving Work Distribution Using Scheduling......Page 285
Using Parallel Sections to Perform Independent Work......Page 289
Nested Parallelism......Page 290
Using OpenMP for Dynamically Defined Parallel Tasks......Page 291
Keeping Data Private to Threads......Page 296
Controlling the OpenMP Runtime Environment......Page 298
Waiting for Work to Complete......Page 300
Restricting the Threads That Execute a Region of Code......Page 303
Ensuring That Code in a Parallel Region Is Executed in Order......Page 307
Collapsing Loops to Improve Workload Balance......Page 308
Enforcing Memory Consistency......Page 309
An Example of Parallelization......Page 310
Summary......Page 315
Atomic Operations......Page 317
Using Compare and Swap Instructions to Form More Complex Atomic Operations......Page 319
Enforcing Memory Ordering to Ensure Correct Operation......Page 323
Compiler Support of Memory-Ordering Directives......Page 325
Reordering of Operations by the Compiler......Page 326
Volatile Variables......Page 330
Operating System–Provided Atomics......Page 331
Dekker’s Algorithm......Page 334
Producer-Consumer with a Circular Buffer......Page 337
Scaling to Multiple Consumers or Producers......Page 340
Scaling the Producer-Consumer to Multiple Threads......Page 341
Modifying the Producer-Consumer Code to Use Atomics......Page 348
The ABA Problem......Page 351
Summary......Page 354
Constraints to Application Scaling......Page 355
Performance Limited by Serial Code......Page 356
Superlinear Scaling......Page 358
Workload Imbalance......Page 360
Hot Locks......Page 362
Scaling of Library Code......Page 367
Insufficient Work......Page 369
Algorithmic Limit......Page 372
Hardware Constraints to Scaling......Page 374
Bandwidth Sharing Between Cores......Page 375
False Sharing......Page 377
Cache Conflict and Capacity......Page 381
Pipeline Resource Starvation......Page 385
Oversubscription......Page 391
Using Processor Binding to Improve Memory Locality......Page 393
Priority Inversion......Page 401
Multicore Processors and Scaling......Page 402
Summary......Page 403
GPU-Based Computing......Page 405
Threading Building Blocks......Page 408
Cilk++......Page 411
Grand Central Dispatch......Page 414
Features Proposed for the Next C and C++ Standards......Page 416
Microsoft\'s C++/CLI......Page 419
Alternative Languages......Page 421
MPI......Page 424
MapReduce as a Strategy for Scaling......Page 428
Transactional Memory......Page 429
Vectorization......Page 430
Summary......Page 431
Identifying Tasks......Page 433
Estimating Performance Gains......Page 434
Locking Granularity......Page 435
Parallel Code on Multicore Processors......Page 436
Optimizing Programs for Multicore Processors......Page 437
The Future......Page 438
Parallel Programming......Page 439
Parallelization Approaches......Page 440
A......Page 441
B......Page 442
C......Page 443
D......Page 445
E......Page 446
G......Page 447
I......Page 448
L......Page 449
M......Page 450
O......Page 452
P......Page 454
Q......Page 456
S......Page 457
T......Page 460
U......Page 461
W......Page 462
Z......Page 463