book

Parallel and High Performance Computing

by Yuliana Zamora, Robert Robey

July 2021

Intermediate to advanced

704 pages

21h 6m

English

Manning Publications

Read now

Unlock full access

forewordYulie Zamora, University of Chicago, IllinoisHow we came to write this bookacknowledgmentsabout this bookWho should read this book
1.1 Why should you learn about parallel computing?1.1.1 What are the potential benefits of parallel computing?1.1.2 Parallel computing cautions1.2 The fundamental laws of parallel computing1.2.1 The limit to parallel computing: Amdahl’s Law1.2.2 Breaking through the parallel limit: Gustafson-Barsis’s Law1.3 How does parallel computing work?1.3.1 Walking through a sample application1.3.2 A hardware model for today’s heterogeneous parallel systems1.3.3 The application/software model for today’s heterogeneous parallel systems1.4 Categorizing parallel approaches1.5 Parallel strategies1.6 Parallel speedup versus comparative speedups: Two different measures1.7 What will you learn in this book?1.7.1 Additional reading1.7.2 ExercisesSummary
2.1 Approaching a new project: The preparation2.1.1 Version control: Creating a safety vault for your parallel code2.1.2 Test suites: The first step to creating a robust, reliable application2.1.3 Finding and fixing memory issues2.1.4 Improving code portability2.2 Profiling: Probing the gap between system capabilities and application performance2.3 Planning: A foundation for success2.3.1 Exploring with benchmarks and mini-apps2.3.2 Design of the core data structures and code modularity2.3.3 Algorithms: Redesign for parallel2.4 Implementation: Where it all happens2.5 Commit: Wrapping it up with quality2.6 Further explorations2.6.1 Additional reading2.6.2 ExercisesSummary
3.1 Know your application’s potential performance limits3.2 Determine your hardware capabilities: Benchmarking3.2.1 Tools for gathering system characteristics3.2.2 Calculating theoretical maximum flops3.2.3 The memory hierarchy and theoretical memory bandwidth3.2.4 Empirical measurement of bandwidth and flops3.2.5 Calculating the machine balance between flops and bandwidth3.3 Characterizing your application: Profiling3.3.1 Profiling tools3.3.2 Empirical measurement of processor clock frequency and energy consumption3.3.3 Tracking memory during run time3.4 Further explorations3.4.1 Additional reading3.4.2 ExercisesSummary
4.1 Performance data structures: Data-oriented design4.1.1 Multidimensional arrays4.1.2 Array of Structures (AoS) versus Structures of Arrays (SoA)4.1.3 Array of Structures of Arrays (AoSoA)4.2 Three Cs of cache misses: Compulsory, capacity, conflict4.3 Simple performance models: A case study4.3.1 Full matrix data representations4.3.2 Compressed sparse storage representations4.4 Advanced performance models4.5 Network messages4.6 Further explorations4.6.1 Additional reading4.6.2 ExercisesSummary

5.1 Algorithm analysis for parallel computing applications5.2 Performance models versus algorithmic complexity5.3 Parallel algorithms: What are they?5.4 What is a hash function?5.5 Spatial hashing: A highly-parallel algorithm5.5.1 Using perfect hashing for spatial mesh operations5.5.2 Using compact hashing for spatial mesh operations5.6 Prefix sum (scan) pattern and its importance in parallel computing5.6.1 Step-efficient parallel scan operation5.6.2 Work-efficient parallel scan operation5.6.3 Parallel scan operations for large arrays5.7 Parallel global sum: Addressing the problem of associativity5.8 Future of parallel algorithm research5.9 Further explorations5.9.1 Additional reading5.9.2 ExercisesSummary
6.1 Vectorization and single instruction, multiple data (SIMD) overview6.2 Hardware trends for vectorization6.3 Vectorization methods6.3.1 Optimized libraries provide performance for little effort6.3.2 Auto-vectorization: The easy way to vectorization speedup (most of the time1)6.3.3 Teaching the compiler through hints: Pragmas and directives6.3.4 Crappy loops, we got them: Use vector intrinsics6.3.5 Not for the faint of heart: Using assembler code for vectorization6.4 Programming style for better vectorization6.5 Compiler flags relevant for vectorization for various compilers6.6 OpenMP SIMD directives for better portability6.7 Further explorations6.7.1 Additional reading6.7.2 ExercisesSummary
7.1 OpenMP introduction7.1.1 OpenMP concepts7.1.2 A simple OpenMP program7.2 Typical OpenMP use cases: Loop-level, high-level, and MPI plus OpenMP7.2.1 Loop-level OpenMP for quick parallelization7.2.2 High-level OpenMP for better parallel performance7.2.3 MPI plus OpenMP for extreme scalability7.3 Examples of standard loop-level OpenMP7.3.1 Loop level OpenMP: Vector addition example7.3.2 Stream triad example7.3.3 Loop level OpenMP: Stencil example7.3.4 Performance of loop-level examples7.3.5 Reduction example of a global sum using OpenMP threading7.3.6 Potential loop-level OpenMP issues7.4 Variable scope importance for correctness in OpenMP7.5 Function-level OpenMP: Making a whole function thread parallel7.6 Improving parallel scalability with high-level OpenMP7.6.1 How to implement high-level OpenMP7.6.2 Example of implementing high-level OpenMP7.7 Hybrid threading and vectorization with OpenMP7.8 Advanced examples using OpenMP7.8.1 Stencil example with a separate pass for the x and y directions7.8.2 Kahan summation implementation with OpenMP threading7.8.3 Threaded implementation of the prefix scan algorithm7.9 Threading tools essential for robust implementations7.9.1 Using Allinea/ARM MAP to get a quick high-level profile of your application7.9.2 Finding your thread race conditions with Intel® Inspector7.10 Example of a task-based support algorithm7.11 Further explorations7.11.1 Additional reading7.11.2 ExercisesSummary
8.1 The basics for an MPI program8.1.1 Basic MPI function calls for every MPI program8.1.2 Compiler wrappers for simpler MPI programs8.1.3 Using parallel startup commands8.1.4 Minimum working example of an MPI program8.2 The send and receive commands for process-to-process communication8.3 Collective communication: A powerful component of MPI8.3.1 Using a barrier to synchronize timers8.3.2 Using the broadcast to handle small file input8.3.3 Using a reduction to get a single value from across all processes8.3.4 Using gather to put order in debug printouts8.3.5 Using scatter and gather to send data out to processes for work8.4 Data parallel examples8.4.1 Stream triad to measure bandwidth on the node8.4.2 Ghost cell exchanges in a two-dimensional (2D) mesh8.4.3 Ghost cell exchanges in a three-dimensional (3D) stencil calculation8.5 Advanced MPI functionality to simplify code and enable optimizations8.5.1 Using custom MPI data types for performance and code simplification8.5.2 Cartesian topology support in MPI8.5.3 Performance tests of ghost cell exchange variants8.6 Hybrid MPI plus OpenMP for extreme scalability8.6.1 The benefits of hybrid MPI plus OpenMP8.6.2 MPI plus OpenMP example8.7 Further explorations8.7.1 Additional reading8.7.2 ExercisesSummary
9.1 The CPU-GPU system as an accelerated computational platform9.1.1 Integrated GPUs: An underused option on commodity-based systems9.1.2 Dedicated GPUs: The workhorse option9.2 The GPU and the thread engine9.2.1 The compute unit is the streaming multiprocessor (or subslice)9.2.2 Processing elements are the individual processors9.2.3 Multiple data operations by each processing element9.2.4 Calculating the peak theoretical flops for some leading GPUs9.3 Characteristics of GPU memory spaces9.3.1 Calculating theoretical peak memory bandwidth9.3.2 Measuring the GPU stream benchmark9.3.3 Roofline performance model for GPUs9.3.4 Using the mixbench performance tool to choose the best GPU for a workload9.4 The PCI bus: CPU to GPU data transfer overhead9.4.1 Theoretical bandwidth of the PCI bus9.4.2 A benchmark application for PCI bandwidth9.5 Multi-GPU platforms and MPI9.5.1 Optimizing the data movement between GPUs across the network9.5.2 A higher performance alternative to the PCI bus9.6 Potential benefits of GPU-accelerated platforms9.6.1 Reducing time-to-solution9.6.2 Reducing energy use with GPUs9.6.3 Reduction in cloud computing costs with GPUs9.7 When to use GPUs9.8 Further explorations9.8.1 Additional reading9.8.2 ExercisesSummary
10.1 GPU programming abstractions: A common framework10.1.1 Massive parallelism10.1.2 Inability to coordinate among tasks10.1.3 Terminology for GPU parallelism10.1.4 Data decomposition into independent units of work: An NDRange or grid10.1.5 Work groups provide a right-sized chunk of work10.1.6 Subgroups, warps, or wavefronts execute in lockstep10.1.7 Work item: The basic unit of operation10.1.8 SIMD or vector hardware10.2 The code structure for the GPU programming model10.2.1 “Me” programming: The concept of a parallel kernel10.2.2 Thread indices: Mapping the local tile to the global world10.2.3 Index sets10.2.4 How to address memory resources in your GPU programming model10.3 Optimizing GPU resource usage10.3.1 How many registers does my kernel use?10.3.2 Occupancy: Making more work available for work group scheduling10.4 Reduction pattern requires synchronization across work groups10.5 Asynchronous computing through queues (streams)10.6 Developing a plan to parallelize an application for GPUs10.6.1 Case 1: 3D atmospheric simulation10.6.2 Case 2: Unstructured mesh application10.7 Further explorations10.7.1 Additional reading10.7.2 ExercisesSummary
11.1 Process to apply directives and pragmas for a GPU implementation11.2 OpenACC: The easiest way to run on your GPU11.2.1 Compiling OpenACC code11.2.2 Parallel compute regions in OpenACC for accelerating computations11.2.3 Using directives to reduce data movement between the CPU and the GPU11.2.4 Optimizing the GPU kernels11.2.5 Summary of performance results for the stream triad11.2.6 Advanced OpenACC techniques11.3 OpenMP: The heavyweight champ enters the world of accelerators11.3.1 Compiling OpenMP code11.3.2 Generating parallel work on the GPU with OpenMP11.3.3 Creating data regions to control data movement to the GPU with OpenMP11.3.4 Optimizing OpenMP for GPUs11.3.5 Advanced OpenMP for GPUs11.4 Further explorations11.4.1 Additional reading11.4.2 ExercisesSummary
Figure 12.1 The interoperability map for the GPU languages shows an increasingly complex situation. Four GPU languages are shown at the top with the various hardware devices at the bottom. The arrows show the code generation pathways from the languages to the hardware. The dashed lines are for hardware that is still in development.12.1 Features of a native GPU programming language12.2 CUDA and HIP GPU languages: The low-level performance option12.2.1 Writing and building your first CUDA application12.2.2 A reduction kernel in CUDA: Life gets complicatedFigure 12.2 Pair-wise reduction tree for a warp that sums up values in log n steps.12.2.3 Hipifying the CUDA code12.3 OpenCL for a portable open source GPU language12.3.1 Writing and building your first OpenCL application12.3.2 Reductions in OpenCLFigure 12.3 Comparison of OpenCL and CUDA reduction kernels: sum_within_blockFigure 12.4 Comparison for the first of two kernel passes for the OpenCL and CUDA reduction kernelsFigure 12.5 Comparison of the second pass for the reduction sum12.4 SYCL: An experimental C++ implementation goes mainstream12.5 Higher-level languages for performance portability12.5.1 Kokkos: A performance portability ecosystem12.5.2 RAJA for a more adaptable performance portability layer12.6 Further explorations12.6.1 Additional reading12.6.2 ExercisesSummary
13.1 An overview of profiling tools13.2 How to select a good workflow13.3 Example problem: Shallow water simulation13.4 A sample of a profiling workflow13.4.1 Run the shallow water application13.4.2 Profile the CPU code to develop a plan of action13.4.3 Add OpenACC compute directives to begin the implementation step13.4.4 Add data movement directives13.4.5 Guided analysis can give you some suggested improvements13.4.6 The NVIDIA Nsight suite of tools can be a powerful development aid13.4.7 CodeXL for the AMD GPU ecosystem13.5 Don’t get lost in the swamp: Focus on the important metrics13.5.1 Occupancy: Is there enough work?13.5.2 Issue efficiency: Are your warps on break too often?13.5.3 Achieved bandwidth: It always comes down to bandwidth13.6 Containers and virtual machines provide alternate workflows13.6.1 Docker containers as a workaround13.6.2 Virtual machines using VirtualBox13.7 Cloud options: A flexible and portable capability13.8 Further explorations13.8.1 Additional reading13.8.2 ExercisesSummary
14.1 Why is affinity important?14.2 Discovering your architecture14.3 Thread affinity with OpenMP14.4 Process affinity with MPI14.4.1 Default process placement with OpenMPI14.4.2 Taking control: Basic techniques for specifying process placement in OpenMPI14.4.3 Affinity is more than just process binding: The full picture14.5 Affinity for MPI plus OpenMP14.6 Controlling affinity from the command line14.6.1 Using hwloc-bind to assign affinity14.6.2 Using likwid-pin: An affinity tool in the likwid tool suite14.7 The future: Setting and changing affinity at run time14.7.1 Setting affinities in your executable14.7.2 Changing your process affinities during run time14.8 Further explorations14.8.1 Additional reading14.8.2 ExercisesSummary
15.1 The chaos of an unmanaged system15.2 How not to be a nuisance when working on a busy cluster15.2.1 Layout of a batch system for busy clusters15.2.2 How to be courteous on busy clusters and HPC sites: Common HPC pet peeves15.3 Submitting your first batch script15.4 Automatic restarts for long-running jobs15.5 Specifying dependencies in batch scripts15.6 Further explorations15.6.1 Additional reading15.6.2 ExercisesSummary
16.1 The components of a high-performance filesystem16.2 Standard file operations: A parallel-to-serial interface16.3 MPI file operations (MPI-IO) for a more parallel world16.4 HDF5 is self-describing for better data management16.5 Other parallel file software packages16.6 Parallel filesystem: The hardware interface16.6.1 Everything you wanted to know about your parallel file setup but didn’t know how to ask16.6.2 General hints that apply to all filesystems16.6.3 Hints specific to particular filesystems16.7 Further explorations16.7.1 Additional reading16.7.2 ExercisesSummary
17.1 Version control systems: It all begins here17.1.1 Distributed version control fits the more mobile world17.1.2 Centralized version control for simplicity and code security17.2 Timer routines for tracking code performance17.3 Profilers: You can’t improve what you don’t measure17.3.1 Simple text-based profilers for everyday use17.3.2 High-level profilers for quickly identifying bottlenecks17.3.3 Medium-level profilers to guide your application development17.3.4 Detailed profilers give the gory details of hardware performance17.4 Benchmarks and mini-apps: A window into system performance17.4.1 Benchmarks measure system performance characteristics17.4.2 Mini-apps give the application perspective17.5 Detecting (and fixing) memory errors for a robust application17.5.1 Valgrind Memcheck: The open source standby17.5.2 Dr. Memory for your memory ailments17.5.3 Commercial memory tools for demanding applications17.5.4 Compiler-based memory tools for convenience17.5.5 Fence-post checkers detect out-of-bounds memory accesses17.5.6 GPU memory tools for robust GPU applications17.6 Thread checkers for detecting race conditions17.6.1 Intel® Inspector: A race condition detection tool with a GUI17.6.2 Archer: A text-based tool for detecting race conditions17.7 Bug-busters: Debuggers to exterminate those bugs17.7.1 TotalView debugger is widely available at HPC sites17.7.2 DDT is another debugger widely available at HPC sites17.7.3 Linux debuggers: Free alternatives for your local development needs17.7.4 GPU debuggers can help crush those GPU bugs17.8 Profiling those file operations17.9 Package managers: Your personal system administrator17.9.1 Package managers for macOS17.9.2 Package managers for Windows17.9.3 The Spack package manager: A package manager for high performance computing17.10 Modules: Loading specialized toolchains17.10.1 TCL modules: The original modules system for loading software toolchains17.10.2 Lmod: A Lua-based alternative Modules implementation17.11 Reflections and exercisesSummary

Content preview from Parallel and High Performance Computing

5 Parallel algorithms and patterns

This chapter covers

What parallel algorithms and patterns are and their importance
How to compare the performance of different algorithms
What distinguishes parallel algorithms from other algorithms

Algorithms are at the core of computational science. Along with data structures, covered in the previous chapter, algorithms form the basis of all computational applications. For this reason, it is important to give careful thought to the key algorithms in your code. To begin, let’s define what we mean by parallel algorithms and parallel patterns.

A parallel algorithm is a well-defined, step-by-step computational procedure that emphasizes concurrency to solve a problem. Examples of algorithms include sorting, ...