Parallel Programming. Concepts and Practice

Description

Preface......Page 3 1 Introduction......Page 5 1.1 Motivational Example and Its Analysis......Page 6 The General Case and the Computation-to-Communication Ratio......Page 12 Distributed Memory Systems......Page 14 Shared Memory Systems......Page 15 Considerations When Designing Parallel Programs......Page 17 1.3 HPC Trends and Rankings......Page 20 1.4 Additional Exercises......Page 22 2 Theoretical Background......Page 24 2.1 PRAM......Page 25 PRAM Variants......Page 26 Parallel Prefix Computation on a PRAM......Page 27 Sparse Array Compaction on a PRAM......Page 29 2.2 Network Topologies......Page 30 2.3 Amdahl's and Gustafson's Laws......Page 34 2.4 Foster's Parallel Algorithm Design Methodology......Page 40 2.5 Additional Exercises......Page 44 References......Page 48 3 Modern Architectures......Page 49 von Neumann Bottleneck......Page 50 Cache Memory......Page 51 Cache Algorithms......Page 53 Optimizing Cache Accesses......Page 54 Cache Coherence......Page 57 Simultaneous Multi-threading and Prefetching......Page 59 Flynn's Taxonomy......Page 60 SIMD Concept......Page 62 Vectorization on Common Microprocessors......Page 63 AoS and SoA......Page 66 3.3 Additional Exercises......Page 73 References......Page 77 4 C++11 Multithreading......Page 78 Distinction Between Multithreading and Multiprocessing......Page 79 Spawning and Joining Threads......Page 80 Our First Multithreaded Program......Page 82 The Traditional Way......Page 84 The Modern Way Using Promises and Futures......Page 86 The Asynchronous Way......Page 91 4.3 Scheduling Based on Static Distributions (Matrix Vector Multiplication)......Page 93 The Sequential Program......Page 94 Block Distribution of Threads......Page 98 Cyclic Distribution of Threads......Page 101 False Sharing......Page 102 Block-Cyclic Distribution of Threads......Page 105 4.4 Handling Load Imbalance (All-Pairs Distance Matrix)......Page 107 Static Schedules......Page 110 Dynamic Block-Cyclic Distributions......Page 113 4.5 Signaling Threads with Condition Variables (Ping Pong)......Page 116 Modeling a Sleeping Student......Page 117 Playing Ping Pong With Condition Variables......Page 119 One-Shot Synchronization Using Futures and Promises......Page 120 Implicitly Enumerable Sets......Page 123 Use Cases for a Thread Pool......Page 124 A Simple Thread Pool Implementation......Page 127 4.7 Additional Exercises......Page 132 References......Page 134 5 Advanced C++11 Multithreading......Page 135 Atomic Counting......Page 136 Non-fundamental Atomic Data Types......Page 138 Atomic Parallel Max-Reduction Using Compare-and-Swap......Page 140 Arbitrary Atomic Operations......Page 142 The ABA Problem......Page 146 Use Case for a Work-Sharing Thread Pool......Page 147 Implementation of Work-Sharing......Page 149 5.3 Parallel Graph Search (Binary Knapsack Problem)......Page 151 The Binary Knapsack Problem......Page 152 Sequential Implementation......Page 153 Parallel Implementation......Page 158 5.4 Outlook......Page 160 5.5 Additional Exercises......Page 162 References......Page 164 6 OpenMP......Page 165 6.1 Introduction to OpenMP (Hello World)......Page 166 Basics......Page 167 6.2 The parallel for Directive (Basic Linear Algebra)......Page 169 Vector Addition......Page 170 Implicit Synchronization......Page 172 Declaring Private Variables......Page 173 Initialization of Privatized Variables......Page 174 Final Remarks on Variable Privatization/Sharing......Page 175 Matrix Vector Multiplication......Page 176 One-Nearest-Neighbor Classification......Page 179 Theoretical Aspects of All-Pairs Distance Computation......Page 180 Implementation of All-Pairs Computation......Page 182 Problems Emerging During Fine-Grained Parallelization......Page 184 Parallel Label Prediction......Page 185 Performance Evaluation......Page 187 Load Imbalance Caused by Symmetry......Page 189 Implementation of Inner Product Computation......Page 190 Performance Evaluation......Page 192 Softmax Regression Classifier Over MNIST......Page 193 Implementation of the Prediction Step......Page 194 Gradient Descent-Based Parameter Optimization......Page 197 Implementation of the Training Step......Page 199 Performance Evaluation......Page 201 Theoretical Background of Parallel Reduction......Page 202 Declaring Custom Parallel Reductions......Page 204 OpenMP Reductions Under the Hood......Page 207 Tree Traversal......Page 209 Generating Tasks in a Loop......Page 212 6.7 SIMD Vectorization (Vector Addition)......Page 213 Vectorization-Aware Functions......Page 215 6.9 Additional Exercises......Page 216 References......Page 223 7 Compute Unified Device Architecture......Page 224 7.1 Introduction to CUDA (Hello World)......Page 225 Interconnection Between Host and Device......Page 227 Organization of Computational Resources......Page 228 Mapping Thread Blocks Onto SMs......Page 229 Mapping Threads Into Warps......Page 232 Computation of the Mean Celebrity Face......Page 233 Computing the Centered Data Matrix......Page 240 Computation of the Covariance Matrix......Page 243 Computation of Eigenfaces......Page 251 Introduction......Page 255 A Linear Memory Algorithm for Sequential DTW......Page 260 A Naive CUDA Port of Linear Memory DTW......Page 266 Wavefront Relaxation in Shared Memory......Page 270 Concurrent Scheduling and Bank Conflicts......Page 276 Texture Memory and Constant Memory......Page 277 7.5 Optimization Guidelines......Page 280 7.6 Additional Exercises......Page 281 References......Page 283 8 Advanced CUDA Programming......Page 285 Segmented Parallel Reduction......Page 286 Global Parallel Reduction......Page 290 Arbitrary Atomic Operations......Page 292 Outlook......Page 293 Newton's Iteration......Page 294 Harnessing Multiple GPUs......Page 297 Interleaving Communication and Computation......Page 300 Streamed Computation on Multiple GPUs......Page 303 Unified Memory......Page 305 Cooperative Groups......Page 306 8.4 Additional Exercises......Page 307 References......Page 310 9 Message Passing Interface......Page 312 9.1 Introduction to MPI......Page 313 9.2 Basic Concepts (Hello World)......Page 315 9.3 Point-to-Point Communication (Ping-Pong)......Page 316 9.4 Nonblocking Communication (Ping-Pong in a Ring of Processes)......Page 319 9.5 Collectives (Counting Primes)......Page 322 9.6 Overlapping Computation and Communication (Jacobi Iteration)......Page 328 9.7 Derived Datatypes (Matrix Multiplication With Submatrix Scattering)......Page 338 9.8 Complex Communicators (Matrix Multiplication Using SUMMA)......Page 345 9.9 Outlook......Page 353 9.10 Additional Exercises......Page 354 References......Page 360 10.1 Introduction to PGAS and UPC++......Page 362 10.3 Memory Affinity and Privatization (Vector Update)......Page 365 10.4 Global Pointers and Collectives (Letter Count)......Page 372 10.5 Locks (Image Histogramming)......Page 379 10.6 Remote Function Invocation (Mandelbrot Sets)......Page 384 10.7 Additional Exercises......Page 391 References......Page 394 Index......Page 396