Structured Parallel Programming: Patterns for Efficient Computation

Front Cover......Page 1
Structured Parallel Programming: Patterns for Efficient Computation......Page 4
Copyright......Page 5
Table of Contents......Page 6
Listings......Page 16
Preface......Page 20
Preliminaries......Page 24
1 Introduction......Page 28
1.1 Think Parallel......Page 29
1.2 Performance......Page 31
1.3.1 Hardware Trends Encouraging Parallelism......Page 34
1.3.2 Observed Historical Trends in Parallelism......Page 38
1.3.3 Need for Explicit Parallel Programming......Page 41
1.4 Structured Pattern-Based Programming......Page 46
1.5.1 Desired Properties......Page 48
1.5.2 Abstractions Instead of Mechanisms......Page 50
1.5.3 Expression of Regular Data Parallelism......Page 51
1.5.4 Composability......Page 54
1.5.6 Performance Portability......Page 55
Cilk Plus......Page 56
Threading Building Blocks (TBB)......Page 58
OpenMP......Page 59
Array Building Blocks (ArBB)......Page 61
OpenCL......Page 62
1.5.9 When to Use Which Model?......Page 63
1.6 Organization of this Book......Page 64
1.7 Summary......Page 65
2.1 Vocabulary and Notation......Page 66
2.2 Strategies......Page 67
2.3 Mechanisms......Page 68
Instruction Parallelism......Page 71
Memory Hierarchy......Page 72
Virtual Memory......Page 74
Attached Devices......Page 75
Data Locality......Page 77
2.4.3 Flynn\'s Characterization......Page 78
2.4.4 Evolution......Page 80
2.5 Performance Theory......Page 81
2.5.1 Latency and Throughput......Page 82
2.5.2 Speedup, Efficiency, and Scalability......Page 83
2.5.3 Power......Page 84
2.5.4 Amdahl\'s Law......Page 85
2.5.5 Gustafson-Barsis\' Law......Page 87
2.5.6 Work-Span Model......Page 89
2.5.7 Asymptotic Complexity......Page 92
2.5.9 Little\'s Formula......Page 94
2.6.1 Race Conditions......Page 95
2.6.2 Mutual Exclusion and Locks......Page 97
2.6.3 Deadlock......Page 99
2.6.5 Lack of Locality......Page 100
2.6.7 Overhead......Page 101
2.7 Summary......Page 102
I Patterns......Page 104
3 Patterns......Page 106
3.1 Nesting Pattern......Page 107
3.2.1 Sequence......Page 109
3.2.3 Iteration......Page 111
3.2.4 Recursion......Page 114
3.3.2 Map......Page 115
3.3.3 Stencil......Page 116
3.3.4 Reduction......Page 117
3.3.5 Scan......Page 119
3.4 Serial Data Management Patterns......Page 122
3.4.3 Heap Allocation......Page 123
3.4.5 Objects......Page 124
3.5.1 Pack......Page 125
3.5.2 Pipeline......Page 126
3.5.3 Geometric Decomposition......Page 127
3.5.5 Scatter......Page 128
3.6.2 Futures......Page 129
3.6.3 Speculative Selection......Page 131
3.6.6 Segmentation......Page 132
3.6.8 Category Reduction......Page 133
3.6.9 Term Graph Rewriting......Page 134
3.7.1 Branch and Bound......Page 135
3.7.2 Transactions......Page 136
3.8 Programming Model Support for Patterns......Page 137
Reduction......Page 139
Nesting, Recursion, Fork–Join......Page 140
3.8.3 OpenMP......Page 141
Map......Page 142
3.8.5 OpenCL......Page 143
Reduction, Scan, Pack, Expand......Page 144
3.9 Summary......Page 145
4 Map......Page 148
4.1 Map......Page 150
4.2.1 Description of the Problem......Page 151
4.2.3 TBB......Page 152
4.2.5 Cilk Plus with Array Notation......Page 154
4.2.7 ArBB Using Vector Operations......Page 155
4.2.8 ArBB Using Elemental Functions......Page 156
4.2.9 OpenCL......Page 157
4.3.1 Description of the Problem......Page 158
4.3.4 Cilk Plus......Page 159
4.3.7 ArBB......Page 161
4.3.8 OpenCL......Page 165
4.4 Sequence of Maps versus Map of Sequence......Page 166
4.6.1 Stencil......Page 168
4.6.3 Divide-and-conquer......Page 169
4.7 Summary......Page 170
5.1 Reduce......Page 172
5.1.1 Reordering Computations......Page 173
5.1.2 Vectorization......Page 175
5.1.3 Tiling......Page 176
5.1.4 Precision......Page 177
TBB......Page 178
5.2.1 Explicit Fusion in TBB......Page 179
5.2.3 Automatic Fusion in ArBB......Page 180
5.3.2 Serial Implementation......Page 181
5.3.3 SSE Intrinsics......Page 182
5.3.4 TBB......Page 183
5.3.5 Cilk Plus......Page 185
5.3.6 OpenMP......Page 187
5.3.7 ArBB......Page 188
5.4 Scan......Page 189
5.4.1 Cilk Plus......Page 191
5.4.4 OpenMP......Page 192
5.5 Fusing Map and Scan......Page 193
5.6 Integration......Page 196
5.6.4 OpenMP......Page 197
5.6.5 TBB......Page 199
5.6.6 ArBB......Page 202
5.7 Summary......Page 204
6 Data Reorganization......Page 206
6.1.1 General Gather......Page 207
6.2 Scatter......Page 209
6.2.2 Permutation Scatter......Page 211
6.2.4 Priority Scatter......Page 212
6.3 Converting Scatter to Gather......Page 213
6.4 Pack......Page 214
6.5 Fusing Map and Pack......Page 216
6.6 Geometric Decomposition and Partition......Page 218
6.7 Array of Structures vs. Structures of Arrays......Page 221
6.8 Summary......Page 224
7.1 Stencil......Page 226
7.2 Implementing Stencil with Shift......Page 228
7.3 Tiling Stencils for Cache......Page 229
7.4 Optimizing Stencils for Communication......Page 230
7.5 Recurrence......Page 231
7.6 Summary......Page 234
8 Fork–Join......Page 236
8.1 Definition......Page 237
8.2 Programming Model Support for Fork–Join......Page 238
8.2.1 Cilk Plus Support for Fork–Join......Page 239
8.2.2 TBB Support for Fork–Join......Page 240
8.2.3 OpenMP Support for Fork–Join......Page 241
8.3 Recursive Implementation of Map......Page 242
8.4 Choosing Base Cases......Page 244
8.5 Load Balancing......Page 245
8.6 Complexity of Parallel Divide-and-Conquer......Page 248
8.7 Karatsuba Multiplication of Polynomials......Page 251
8.8 Cache Locality and Cache-Oblivious Algorithms......Page 254
8.9 Quicksort......Page 257
8.9.1 Cilk Quicksort......Page 258
8.9.2 TBB Quicksort......Page 260
8.9.3 Work and Span for Quicksort......Page 264
8.10 Reductions and Hyperobjects......Page 265
8.11 Implementing Scan with Fork–Join......Page 268
8.12 Applying Fork–Join to Recurrences......Page 273
8.12.1 Analysis......Page 277
8.13 Summary......Page 278
9.1 Basic Pipeline......Page 280
9.2 Pipeline with Parallel Stages......Page 281
9.3 Implementation of a Pipeline......Page 282
9.4.1 Pipeline in TBB......Page 284
9.4.2 Pipeline in Cilk Plus......Page 285
9.6 Mandatory versus Optional Parallelism......Page 288
9.7 Summary......Page 289
II Examples......Page 290
10.1 Background......Page 292
10.2 Stencil Computation......Page 293
10.3 Impact of Caches on Arithmetic Intensity......Page 294
10.4 Raising Arithmetic Intensity with Space–Time Tiling......Page 297
10.5 Cilk Plus Code......Page 299
10.6 ArBB Implementation......Page 302
10.7 Summary......Page 304
11.1 Algorithm......Page 306
11.2.1 Hyperobjects......Page 308
11.3 K-Means with TBB......Page 312
11.4 Summary......Page 316
12.1 The Bzip2 Algorithm......Page 318
12.2 Three-Stage Pipeline Using TBB......Page 319
12.4 Three-Stage Pipeline Using Cilk Plus......Page 323
12.5 Summary......Page 324
13.1 Parallel Merge......Page 326
13.1.2 Work and Span of Parallel Merge......Page 328
13.2 Parallel Merge Sort......Page 330
13.2.1 Work and Span of Merge Sort......Page 331
13.3 Summary......Page 332
14.1 Overall Structure......Page 334
14.3 Binning......Page 336
14.4 Repacking and Subsorting......Page 337
14.5 Performance Analysis of Sample Sort......Page 339
14.7 Summary......Page 340
15.1 Fortran Rules!......Page 342
15.2 Recursive Cholesky Decomposition......Page 344
15.3 Triangular Solve......Page 345
15.4 Symmetric Rank Update......Page 346
15.5 Where Is the Time Spent?......Page 348
15.6 Summary......Page 349
Appendices......Page 350
A.2 Computer Architecture Including Parallel Systems......Page 352
A.3 Parallel Programming Models......Page 353
B.2 Unique Characteristics......Page 356
B.3 Borrowing Components from TBB......Page 358
B.5 cilk_for......Page 359
B.6 cilk_spawn and cilk_sync......Page 360
B.7 Reducers (Hyperobjects)......Page 361
B.7.1 C++ Syntax......Page 362
B.7.2 C Syntax......Page 364
B.8 Array Notation......Page 365
B.8.1 Specifying Array Sections......Page 366
B.8.2 Operations on Array Sections......Page 367
B.8.3 Reductions on Array Sections......Page 368
B.8.5 Avoid Partial Overlap of Array Sections......Page 369
B.9 #pragma simd......Page 370
B.10 Elemental Functions......Page 371
B.11 Note on C++11......Page 372
B.13 History......Page 373
B.14 Summary......Page 374
C.1 Unique Characteristics......Page 376
C.2 Using TBB......Page 377
C.3.1 blocked_range......Page 378
C.3.2 Partitioners......Page 379
C.4 parallel_reduce......Page 380
C.7 parallel_invoke......Page 381
C.9 task......Page 382
C.10 atomic......Page 383
C.12 Notes on C++11......Page 385
C.13 History......Page 386
C.14 Summary......Page 387
D.2 Lambda Expressions......Page 388
D.3 std::move......Page 392
Appendix E: Glossary......Page 394
Bibliography......Page 418
C......Page 424
D......Page 425
F......Page 426
M......Page 427
O......Page 428
P......Page 429
S......Page 430
V......Page 432
Z......Page 433