Parallel Programming: Concepts and Practice

Cover......Page 1
Half Title......Page 2
Parallel Programming:Concepts and Practice......Page 4
Copyright © 2018......Page 5
Preface......Page 6
Acknowledgments......Page 8
1 Introduction......Page 9
 1.1 Motivational Example and Its Analysis......Page 10
   The General Case and the Computation-to-Communication Ratio......Page 16
   Distributed Memory Systems......Page 18
   Shared Memory Systems......Page 19
   Considerations When Designing Parallel Programs......Page 21
 1.3 HPC Trends and Rankings......Page 24
 1.4 Additional Exercises......Page 26
2 Theoretical Background......Page 28
 2.1 PRAM......Page 29
   PRAM Variants......Page 30
   Parallel Prefix Computation on a PRAM......Page 31
   Sparse Array Compaction on a PRAM......Page 33
 2.2 Network Topologies......Page 34
 2.3 Amdahl\'s and Gustafson\'s Laws......Page 38
 2.4 Foster\'s Parallel Algorithm Design Methodology......Page 44
 2.5 Additional Exercises......Page 48
  References......Page 52
3 Modern Architectures......Page 53
   von Neumann Bottleneck......Page 54
   Cache Memory......Page 55
   Cache Algorithms......Page 57
   Optimizing Cache Accesses......Page 58
   Cache Coherence......Page 61
   Simultaneous Multi-threading and Prefetching......Page 63
   Flynn\'s Taxonomy......Page 64
   SIMD Concept......Page 66
   Vectorization on Common Microprocessors......Page 67
   AoS and SoA......Page 70
 3.3 Additional Exercises......Page 77
  References......Page 81
4 C++11 Multithreading......Page 82
   Distinction Between Multithreading and Multiprocessing......Page 83
   Spawning and Joining Threads......Page 84
   Our First Multithreaded Program......Page 86
   The Traditional Way......Page 88
   The Modern Way Using Promises and Futures......Page 90
   The Asynchronous Way......Page 95
 4.3 Scheduling Based on Static Distributions (Matrix Vector Multiplication)......Page 97
   The Sequential Program......Page 98
   Block Distribution of Threads......Page 102
   Cyclic Distribution of Threads......Page 105
   False Sharing......Page 106
   Block-Cyclic Distribution of Threads......Page 109
 4.4 Handling Load Imbalance (All-Pairs Distance Matrix)......Page 111
   Static Schedules......Page 114
   Dynamic Block-Cyclic Distributions......Page 117
 4.5 Signaling Threads with Condition Variables (Ping Pong)......Page 120
   Modeling a Sleeping Student......Page 121
   Playing Ping Pong With Condition Variables......Page 123
   One-Shot Synchronization Using Futures and Promises......Page 124
   Implicitly Enumerable Sets......Page 127
   Use Cases for a Thread Pool......Page 128
   A Simple Thread Pool Implementation......Page 131
 4.7 Additional Exercises......Page 136
  References......Page 138
5 Advanced C++11 Multithreading......Page 139
   Atomic Counting......Page 140
   Non-fundamental Atomic Data Types......Page 142
   Atomic Parallel Max-Reduction Using Compare-and-Swap......Page 144
   Arbitrary Atomic Operations......Page 146
   The ABA Problem......Page 150
   Use Case for a Work-Sharing Thread Pool......Page 151
   Implementation of Work-Sharing......Page 153
 5.3 Parallel Graph Search (Binary Knapsack Problem)......Page 155
   The Binary Knapsack Problem......Page 156
   Sequential Implementation......Page 157
   Parallel Implementation......Page 162
 5.4 Outlook......Page 164
 5.5 Additional Exercises......Page 166
  References......Page 168
6 OpenMP......Page 169
 6.1 Introduction to OpenMP (Hello World)......Page 170
   Basics......Page 171
 6.2 The parallel for Directive (Basic Linear Algebra)......Page 173
   Vector Addition......Page 174
    Implicit Synchronization......Page 176
    Declaring Private Variables......Page 177
    Initialization of Privatized Variables......Page 178
    Final Remarks on Variable Privatization/Sharing......Page 179
   Matrix Vector Multiplication......Page 180
   One-Nearest-Neighbor Classification......Page 183
   Theoretical Aspects of All-Pairs Distance Computation......Page 184
   Implementation of All-Pairs Computation......Page 186
    Problems Emerging During Fine-Grained Parallelization......Page 188
   Parallel Label Prediction......Page 189
   Performance Evaluation......Page 191
   Load Imbalance Caused by Symmetry......Page 193
   Implementation of Inner Product Computation......Page 194
   Performance Evaluation......Page 196
   Softmax Regression Classifier Over MNIST......Page 197
    Implementation of the Prediction Step......Page 198
    Gradient Descent-Based Parameter Optimization......Page 201
    Implementation of the Training Step......Page 203
    Performance Evaluation......Page 205
    Theoretical Background of Parallel Reduction......Page 206
    Declaring Custom Parallel Reductions......Page 208
   OpenMP Reductions Under the Hood......Page 211
   Tree Traversal......Page 213
   Generating Tasks in a Loop......Page 216
 6.7 SIMD Vectorization (Vector Addition)......Page 217
   Vectorization-Aware Functions......Page 219
 6.9 Additional Exercises......Page 220
  References......Page 227
7 Compute Unified Device Architecture......Page 228
 7.1 Introduction to CUDA (Hello World)......Page 229
   Interconnection Between Host and Device......Page 231
   Organization of Computational Resources......Page 232
    Mapping Thread Blocks Onto SMs......Page 233
    Mapping Threads Into Warps......Page 236
   Computation of the Mean Celebrity Face......Page 237
   Computing the Centered Data Matrix......Page 244
   Computation of the Covariance Matrix......Page 247
   Computation of Eigenfaces......Page 255
   Introduction......Page 259
   A Linear Memory Algorithm for Sequential DTW......Page 264
   A Naive CUDA Port of Linear Memory DTW......Page 270
   Wavefront Relaxation in Shared Memory......Page 274
   Concurrent Scheduling and Bank Conflicts......Page 280
   Texture Memory and Constant Memory......Page 281
 7.5 Optimization Guidelines......Page 284
 7.6 Additional Exercises......Page 285
  References......Page 287
8 Advanced CUDA Programming......Page 289
   Segmented Parallel Reduction......Page 290
   Global Parallel Reduction......Page 294
   Arbitrary Atomic Operations......Page 296
   Outlook......Page 297
   Newton\'s Iteration......Page 298
   Harnessing Multiple GPUs......Page 301
   Interleaving Communication and Computation......Page 304
   Streamed Computation on Multiple GPUs......Page 307
   Unified Memory......Page 309
   Cooperative Groups......Page 310
 8.4 Additional Exercises......Page 311
  References......Page 314
9 Message Passing Interface......Page 316
 9.1 Introduction to MPI......Page 317
 9.2 Basic Concepts (Hello World)......Page 319
 9.3 Point-to-Point Communication (Ping-Pong)......Page 320
 9.4 Nonblocking Communication (Ping-Pong in a Ring of Processes)......Page 323
 9.5 Collectives (Counting Primes)......Page 326
 9.6 Overlapping Computation and Communication (Jacobi Iteration)......Page 332
 9.7 Derived Datatypes (Matrix Multiplication With Submatrix Scattering)......Page 342
 9.8 Complex Communicators (Matrix Multiplication Using SUMMA)......Page 349
 9.9 Outlook......Page 357
 9.10 Additional Exercises......Page 358
  References......Page 364
 10.1 Introduction to PGAS and UPC++......Page 366
 10.3 Memory Affinity and Privatization (Vector Update)......Page 369
 10.4 Global Pointers and Collectives (Letter Count)......Page 376
 10.5 Locks (Image Histogramming)......Page 383
 10.6 Remote Function Invocation (Mandelbrot Sets)......Page 388
 10.7 Additional Exercises......Page 395
  References......Page 398
Index......Page 400
Back Cover......Page 405