Programming on Parallel Machines

Execution Speed......Page 15 Basic Architecture......Page 16 Example: SMP Systems......Page 17 SIMD......Page 18 Example......Page 19 Programmer View......Page 24 Example......Page 25 Relative Merits: Shared-Memory Vs. Message-Passing......Page 28 ``Embarrassingly Parallel'' Applications......Page 29 What Is Shared?......Page 31 Interleaving......Page 32 Bank Conflicts and Solutions......Page 33 SMP Systems......Page 34 NUMA Systems......Page 35 Crossbar Interconnects......Page 36 Omega (or Delta) Interconnects......Page 38 Comparative Analysis......Page 39 Why Have Memory in Modules?......Page 40 Test-and-Set Type Instructions......Page 41 Cache Coherency......Page 42 Example: the MESI Cache Coherency Protocol......Page 45 Memory-Access Consistency Policies......Page 47 Fetch-and-Add and Packet-Combining Operations......Page 49 Software Distributed Shared Memory......Page 51 Case Study: JIAJIA......Page 53 A Use-Once Version......Page 57 A Correct Version......Page 58 Use of Wait Operations......Page 59 Butterfly Barriers......Page 61 Running Example......Page 63 The OpenMP parallel Pragma......Page 66 Scope Issues......Page 67 Implicit Barriers......Page 68 Basic Example......Page 69 Controlling the Partitioning of Work to Threads......Page 72 The OpenMP reduction Clause......Page 73 The Task Directive......Page 74 The OpenMP atomic Clause......Page 76 Memory Consistency and the flush Pragma......Page 77 Debugging......Page 78 The Effect of Problem Size......Page 79 Some Fine Tuning......Page 80 The Rest of OpenMP......Page 84 Further Examples......Page 85 Overview......Page 87 Sample Program......Page 88 SIMT Architecture......Page 92 ``OS in Hardware''......Page 93 Shared and Global Memory......Page 94 Global-Memory Performance Issues......Page 97 Other Types of Memory......Page 98 Threads Hierarchy......Page 100 What's NOT There......Page 101 Hardware Requirements, Installation, Compilation, Debugging......Page 102 Improving the Sample Program......Page 103 Finding the Mean Number of Mutual Outlinks......Page 105 Finding Prime Numbers......Page 108 CUBLAS......Page 111 The New Generation......Page 114 Further Examples......Page 115 Overview......Page 117 Definitions......Page 118 The Network Is Literally the Weakest Link......Page 120 MapReduce......Page 121 History......Page 125 Performance Issues......Page 126 The Code......Page 127 MPI_Send()......Page 131 MPI_Recv()......Page 132 Example......Page 133 MPI_Bcast()......Page 135 MPI_Reduce()/MPI_Allreduce()......Page 136 MPI_Gather()/MPI_Allgather()......Page 137 Creating Communicators......Page 138 Buffering, Etc.......Page 139 Safe Exchange Operations......Page 141 Python: pyMPI......Page 142 R......Page 144 Example......Page 145 General Parallel Strategies......Page 146 Implementations......Page 149 Example from Graph Theory......Page 151 Partitioned Matrices......Page 152 Message-Passing Case......Page 154 Performance Issues......Page 155 CUDA......Page 156 Solving Systems of Linear Equations......Page 160 Gaussian Elimination......Page 161 OpenMP Implementation of the Jacobi Algorithm......Page 162 Matrix Inversion......Page 163 Power Series Method......Page 164 The Separation Process......Page 165 Shared-Memory Quicksort......Page 167 Hyperquicksort......Page 168 Message Passing Mergesort on a Tree Topology......Page 169 Bitonic Mergesort......Page 170 The Much-Maligned Bubble Sort......Page 172 CUDA Implementation of Odd/Even Transposition Sort......Page 173 Shearsort......Page 174 Bucket Sort with Sampling......Page 175 Enumeration Sort......Page 176 One-Dimensional Fourier Series......Page 177 Discrete Fourier Transforms......Page 181 One-Dimensional Data......Page 182 The Fast Fourier Transform......Page 183 Parallelizing Computation of the Inverse Transform......Page 184 Smoothing......Page 185 Edge Detection......Page 186 The Cosine Transform......Page 187 Does the Function g() Really Have to Be Repeating?......Page 188 Vector Space Issues (optional section)......Page 189 Bandwidth: How to Read the San Francisco Chronicle Business Page (optional section)......Page 190 What Is It?......Page 193 The Market Basket Problem......Page 194 Parallelizing the Apriori Algorithm......Page 195 Kernel-Based Density Estimation......Page 196 Histogram Computation for Images......Page 199 Clustering......Page 200 Principal Component Analysis (PCA)......Page 202 Rmpi......Page 203 The R snow Package......Page 204 Rdsm......Page 207 The gputools Package......Page 209 The rgpu Package......Page 210 Debugging R Applications......Page 211 The thread Module......Page 213 The threading Module......Page 222 General Ideas......Page 226 Event Example......Page 227 Threads Internals......Page 229 The Python Thread Manager......Page 230 The GIL......Page 231 The multiprocessing Module......Page 232 The Queue Module for Threads and Multiprocessing......Page 235 Debugging Threaded and Multiprocessing Python Programs......Page 238 Using PDB to Debug Threaded Programs......Page 239 RPDB2 and Winpdb......Page 240 Terminology and Notation......Page 241 Matrix Addition and Multiplication......Page 242 Linear Independence......Page 243 Eigenvalues and Eigenvectors......Page 244