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