Programming Massively Parallel Processors: A Hands-on Approach

Programming Massively Parallel Processors
Copyright
Dedication
Contents
Foreword
Preface
How to use the book
A two-phased approach
Tying it all together: the final project
The design document
The project report and symposium
Class competition
Course resources
Acknowledgments
1 Introduction
1.1 Heterogeneous parallel computing
1.2 Why more speed or parallelism?
1.3 Speeding up real applications
1.4 Challenges in parallel programming
1.5 Related parallel programming interfaces
1.6 Overarching goals
1.7 Organization of the book
References
2 Heterogeneous data parallel computing
2.1 Data parallelism
2.2 CUDA C program structure
2.3 A vector addition kernel
2.4 Device global memory and data transfer
2.5 Kernel functions and threading
2.6 Calling kernel functions
2.7 Compilation
2.8 Summary
2.8.1 Function declarations
2.8.2 Kernel call and grid launch
2.8.3 Built-in (predefined) variables
2.8.4 Runtime application programming interface
Exercises
References
3 Multidimensional grids and data
3.1 Multidimensional grid organization
3.2 Mapping threads to multidimensional data
3.3 Image blur: a more complex kernel
3.4 Matrix multiplication
3.5 Summary
Exercises
4 Compute architecture and scheduling
4.1 Architecture of a modern GPU
4.2 Block scheduling
4.3 Synchronization and transparent scalability
4.4 Warps and SIMD hardware
4.5 Control divergence
4.6 Warp scheduling and latency tolerance
4.7 Resource partitioning and occupancy
4.8 Querying device properties
4.9 Summary
Exercises
References
5 Memory architecture and data locality
5.1 Importance of memory access efficiency
5.2 CUDA memory types
5.3 Tiling for reduced memory traffic
5.4 A tiled matrix multiplication kernel
5.5 Boundary checks
5.6 Impact of memory usage on occupancy
5.7 Summary
Exercises
6 Performance considerations
6.1 Memory coalescing
6.2 Hiding memory latency
6.3 Thread coarsening
6.4 A checklist of optimizations
6.5 Knowing your computation’s bottleneck
6.6 Summary
Exercises
References
7 Convolution
7.1 Background
7.2 Parallel convolution: a basic algorithm
7.3 Constant memory and caching
7.4 Tiled convolution with halo cells
7.5 Tiled convolution using caches for halo cells
7.6 Summary
Exercises
8 Stencil
8.1 Background
8.2 Parallel stencil: a basic algorithm
8.3 Shared memory tiling for stencil sweep
8.4 Thread coarsening
8.5 Register tiling
8.6 Summary
Exercises
9 Parallel histogram
9.1 Background
9.2 Atomic operations and a basic histogram kernel
9.3 Latency and throughput of atomic operations
9.4 Privatization
9.5 Coarsening
9.6 Aggregation
9.7 Summary
Exercises
References
10 Reduction
10.1 Background
10.2 Reduction trees
10.3 A simple reduction kernel
10.4 Minimizing control divergence
10.5 Minimizing memory divergence
10.6 Minimizing global memory accesses
10.7 Hierarchical reduction for arbitrary input length
10.8 Thread coarsening for reduced overhead
10.9 Summary
Exercises
11 Prefix sum (scan)
11.1 Background
11.2 Parallel scan with the Kogge-Stone algorithm
11.3 Speed and work efficiency consideration
11.4 Parallel scan with the Brent-Kung algorithm
11.5 Coarsening for even more work efficiency
11.6 Segmented parallel scan for arbitrary-length inputs
11.7 Single-pass scan for memory access efficiency
11.8 Summary
Exercises
References
12 Merge
12.1 Background
12.2 A sequential merge algorithm
12.3 A parallelization approach
12.4 Co-rank function implementation
12.5 A basic parallel merge kernel
12.6 A tiled merge kernel to improve coalescing
12.7 A circular buffer merge kernel
12.8 Thread coarsening for merge
12.9 Summary
Exercises
References
13 Sorting
13.1 Background
13.2 Radix sort
13.3 Parallel radix sort
13.4 Optimizing for memory coalescing
13.5 Choice of radix value
13.6 Thread coarsening to improve coalescing
13.7 Parallel merge sort
13.8 Other parallel sort methods
13.9 Summary
Exercises
References
14 Sparse matrix computation
14.1 Background
14.2 A simple SpMV kernel with the COO format
14.3 Grouping row nonzeros with the CSR format
14.4 Improving memory coalescing with the ELL format
14.5 Regulating padding with the hybrid ELL-COO format
14.6 Reducing control divergence with the JDS format
14.7 Summary
Exercises
References
15 Graph traversal
15.1 Background
15.2 Breadth-first search
15.3 Vertex-centric parallelization of breadth-first search
15.4 Edge-centric parallelization of breadth-first search
15.5 Improving efficiency with frontiers
15.6 Reducing contention with privatization
15.7 Other optimizations
Reducing launch overhead
Improving load balance
Further challenges
15.8 Summary
Exercises
References
16 Deep learning
16.1 Background
Multilayer classifiers
Training models
Error function
Stochastic gradient descent
Epoch
Backpropagation
Chain rule
Learning rate
Minibatch
Training multilayer classifiers
Feedforward networks
16.2 Convolutional neural networks
Convolutional neural network inference
Convolutional neural network backpropagation
16.3 Convolutional layer: a CUDA inference kernel
16.4 Formulating a convolutional layer as GEMM
16.5 CUDNN library
16.6 Summary
Exercises
References
17 Iterative magnetic resonance imaging reconstruction
17.1 Background
17.2 Iterative reconstruction
17.3 Computing FHD
Step 1: Determine the kernel parallelism structure
Step 2: Getting around the memory bandwidth limitation
Step 3: Using hardware trigonometry functions
Step 4: Experimental performance tuning
17.4 Summary
Exercises
References
18 Electrostatic potential map
18.1 Background
18.2 Scatter versus gather in kernel design
18.3 Thread coarsening
18.4 Memory coalescing
18.5 Cutoff binning for data size scalability
18.6 Summary
Exercises
References
19 Parallel programming and computational thinking
19.1 Goals of parallel computing
19.2 Algorithm selection
19.3 Problem decomposition
19.4 Computational thinking
19.5 Summary
References
20 Programming a heterogeneous computing cluster
20.1 Background
20.2 A running example
20.3 Message passing interface basics
20.4 Message passing interface point-to-point communication
20.5 Overlapping computation and communication
20.6 Message passing interface collective communication
20.7 CUDA aware message passing interface
20.8 Summary
Exercises
References
21 CUDA dynamic parallelism
21.1 Background
21.2 Dynamic parallelism overview
21.3 An example: Bezier curves
Linear Bezier curves
Quadratic Bezier curves
Bezier curve calculation (without dynamic parallelism)
Bezier curve calculation (with dynamic parallelism)
21.4 A recursive example: quadtrees
21.5 Important considerations
Memory and data visibility
Pending launch pool configuration
Streams
Nesting depth
21.6 Summary
Exercises
A21.1 Support code for quadtree example
References
22 Advanced practices and future evolution
22.1 Model of host/device interaction
Zero-copy memory and unified virtual address space
Large virtual and physical address spaces
Unified memory
Virtual address space control
22.2 Kernel execution control
Function calls within kernel functions
Exception handling in kernel functions
Simultaneous execution of multiple grids
Hardware queues and dynamic parallelism
Interruptable grids
Cooperative kernels
22.3 Memory bandwidth and compute throughput
Double-precision speed
Better control flow efficiency
Configurable caching and scratchpad
Enhanced atomic operations
Enhanced global memory access
22.4 Programming environment
Unified device memory space
Profiling with critical path analysis
22.5 Future outlook
References
23 Conclusion and outlook
23.1 Goals revisited
23.2 Future outlook
Appendix A Numerical considerations
A.1 Floating-point data representation
A.1.1 Normalized representation of M
A.1.2 Excess encoding of E
A.2 Representable numbers
A.3 Special bit patterns and precision in IEEE format
A.4 Arithmetic accuracy and rounding
A.5 Algorithm considerations
A.6 Linear solvers and numerical stability
A.7 Summary
Exercises
References
Index