What Problems Fit Well on GPUs?

This episode introduces the characteristics of problems that are well-suited, or not well-suited, for GPU acceleration. It explains the key factors that determine whether an application can effectively leverage the massive parallelism of modern GPUs.

Using representative examples such as matrix multiplication, the episode also showcases GPU programming applications across a range of disciplines, including electronic structure calculations, computational chemistry, and the digital humanities.

Questions

  • What are the strengths and weaknesses of GPUs?

  • What characteristics make a problem well-suited for GPU acceleration?

  • What types of applications benefit most from GPU computing?

  • Why are GPUs so widely used in machine learning applications?

Objectives

  • Identify the characteristics of problems that are well-suited for GPU acceleration.

  • Evaluate whether an application is a good candidate for GPU porting.

  • Recognize application domains that benefit from GPU computing, including scientific simulations, machine learning, image processing, and other large-scale parallel workloads.

Instructor note

  • 20 min teaching

  • 10 min exercises/discussion

Problems Well-Suited for GPUs

A useful way to build intuition is to think about how a GPU is designed. GPUs contain thousands of lightweight processing cores that execute the same operation on many pieces of data simultaneously. As a result, they deliver their best performance on highly parallel, compute-intensive workloads with regular computation and memory access patterns.

The following analogy from Stack Exchange illustrates this idea:

From a metaphorical point of view, the GPU can be seen as a person lying on a bed of nails. The person lying on top is the data and in the base of each nail there is a processor, so the nail is actually an arrow pointing from processor to memory. All nails are in a regular pattern, like a grid. If the body is well spread, it feels good (performance is good), if the body only touches some spots of the nail bed, then the pain is bad (bad performance).

The analogy emphasizes an important principle: GPUs perform best when the workload can be evenly distributed across a large number of processing cores. When there is sufficient parallel work to keep most cores busy, the hardware can achieve substantial speedups over a CPU.

Typical examples of GPU-friendly applications include:

  • Graphics rendering: Original application domain for GPUs, involving millions of pixels and vertices processed in parallel.

  • Large-scale matrix and vector operations: Fundamental to machine learning, scientific computing, numerical linear algebra, and image processing.

  • Large-scale data analytics: Including clustering, classification, regression, and other parallel data-processing tasks.

  • Fourier Transforms: Widely used in signal processing, image analysis, and computational physics.

  • Monte Carlo simulations: Used in finance, physics, and uncertainty quantification.

  • Molecular dynamics simulations: Modeling atomic and molecular interactions in chemistry, physics, biology, and materials science.

  • Computational fluid dynamics: Simulating fluid flow in engineering, aerospace, and environmental sciences.

  • Deep learning and computer vision: Especially training and inference for convolutional neural networks and other neural network architectures.

Although these applications span diverse scientific and engineering disciplines, they share a common characteristic: the same computation is applied independently to many data elements, making them excellent candidates for GPU acceleration.

Discussion

What type of applications or workloads do you run on GPUs?

  • Scientific simulations?

  • Machine learning or AI?

  • Data analysis & visualization?

  • Other applications?

Problems Less Suited for GPUs

Although GPUs excel at massively parallel computation, not every problem benefits from GPU acceleration. Applications with limited parallelism, irregular execution patterns, or heavy memory requirements often achieve little speedup, or may even run more slowly, than optimized CPU implementations.

Examples of workloads that are generally less suitable for GPUs include:

  • Sequential algorithms: Problems with strong dependencies between successive computations cannot be effectively parallelized. Examples include recursive algorithms, certain dynamic programming methods, and many graph traversal algorithms.

  • Irregular control flow (branch divergence): GPUs are most efficient when many threads execute the same instructions simultaneously. Frequent branching (e.g., numerous if/else statements) causes threads to diverge, reducing hardware utilization and overall performance.

  • Low arithmetic intensity: GPUs excel at performing large numbers of mathematical operations in parallel. However, if a problem has low arithmetic intensity (i.e., a low ratio of computational operations to memory accesses), GPU’s computational resources may not be fully utilized. In such cases, memory access, rather than computation, becomes the primary performance bottleneck.

  • Small data sets: For small datasets that do not provide sufficient parallelism, using a GPU may not deliver noticeable performance improvements. In such cases, the overhead of transferring data between the CPU and GPU, along with the cost of GPU initialization and kernel launches, may outweigh the benefits of parallel execution.

  • Limited parallelism: Some algorithms inherently expose only a small amount of parallel work. If there are not enough independent tasks to keep thousands of GPU cores busy, the hardware cannot be efficiently utilized.

  • Memory-bound workloads: Applications dominated by memory accesses rather than computation often see limited performance gains. In addition, problems with very large memory footprints may exceed the GPU’s available memory or become constrained by memory bandwidth.

Compute-bound vs memory-bound applications

To determine whether an application is compute-bound or memory-bound, we need to analyze the balance between computation and data movement.

  • A compute-bound application spends most of its time performing arithmetic operations, meaning that increasing computational resources can improve performance.

  • A memory-bound application is limited by the speed at which data can be loaded from and stored to memory, and performance is often improved by reducing memory accesses or optimizing data locality. A useful metric for this analysis is arithmetic intensity, which measures the ratio of computational operations to memory traffic.

Profiling tools and performance models can help identify the dominant bottleneck. For GPU applications, tools such as NVIDIA Nsight Compute can reveal whether the GPU is limited by compute throughput or memory bandwidth. The Roofline model is also commonly used to classify applications based on their arithmetic intensity and hardware capabilities.

Understanding whether an application is compute-bound or memory-bound helps guide optimization strategies and determine whether GPU acceleration is likely to provide significant benefits.

Discussion

  • What characteristics of an application make it a poor candidate for GPU acceleration?

    • (Consider factors such as limited parallelism, sequential dependencies, irregular control flow, low arithmetic intensity, and memory bottlenecks.)

  • How can you determine whether porting an application to a GPU will provide meaningful performance improvements?

    • (Consider profiling, identifying bottlenecks, and evaluating the overhead of data movement between CPU and GPU.)

  • Do you know whether your application is compute-bound or memory-bound?

    • If yes, how did you identify the performance bottleneck?

    • If not, what challenges prevent you from identifying the performance bottleneck?

Examples of GPU Acceleration

To get a better understanding of the potential performance improvements from GPU acceleration, let’s explore a few case studies where calculations have been successfully ported to GPUs.

A simple example: Matrix multiplication in Julia

Here we consider the example of matrix multiplication implemented in the Julia programming language:

Type-Along

using AMDGPU
using BenchmarkTools

N = [9, 10, 11, 12]

for n in N
   A = rand(2^n, 2^n); A_d = ROCArray(A);

   @btime $A * $A;

   @btime begin
      $A_d * $A_d;
      AMDGPU.synchronize()
   end
end

Discussion

  • How much faster do you expect the GPU version to be compared with running on a single CPU core?

  • Julia automatically parallelizes matrix multiplication across available CPU cores. Will the GPU version still outperform a 64-core CPU implementation?

  • How does the size of the array affect the performance improvement achieved with GPU acceleration?

Electronic structure calculations

The Vienna Ab initio Simulation Package (VASP) is a popular software package used for electronic structure calculations. The figures below present the speedups measured in a recent benchmark study, Understanding VASP Power Profiles on NVIDIA A100 GPUs, performed on the Perlmutter supercomputer at NERSC (National Energy Research Scientific Computing Center), a HPC facility operated by Lawrence Berkeley National Laboratory (LBNL) in the United States.

Parallel efficiency is a measure of the scalability of a parallel application and reflects how effectively additional computational resources are utilized. As shown in the figure below, VASP achieves strong parallel efficiency across a range of GPU nodes on the Perlmutter NVIDIA A100 system. The efficiency gradually decreases as the number of GPU nodes increases, primarily due to communication overhead and reduced computational workload per GPU. These computational results demonstrate that VASP can effectively maintain a good scalability for large-scale simulations, with the observed efficiency trends highlighting the importance of selecting appropriate levels of parallelism to balance performance and resource utilization.

../../_images/vasp-parallel-efficiency.png

Figure: Parallel efficiency of VASP on seven test cases representing diverse production workloads. Figure is reproduced from reference Understanding VASP Power Profiles on NVIDIA A100 GPUs

In addition, energy analysis of scientific applications is essential for understanding power consumption patterns and identifying opportunities to improve energy efficiency while maintaining performance. In large-scale HPC environments, where energy costs and power constraints are becoming increasingly critical, characterizing workload-dependent energy behavior provides valuable insights for developing effective optimization strategies.

An analysis of total energy consumption, as shown in the figure below, revealed that VASP’s power usage varies substantially across different workloads, with workload characteristics having a stronger influence than parallel concurrency. Furthermore, GPU power capping at 50% of the Thermal Design Power (TDP) can be effectively applied to most VASP workloads, resulting in less than a 10% performance degradation.

../../_images/vasp-energy-consumption.jpg

Figure: (Left) Power usage of seven representative VASP workloads. The horizontal axis shows number of nodes used, and vertical axis shows high power mode per node. (Right) Power consumed per GPU when running VASP under four different power caps: 400 W (default), 300 W, 200 W, and 100 W. Horizontal axis shows power caps applied to GPUs, and vertical axis shows high power mode per GPU as a fraction of applied cap. The dashed horizontal line represents applied power cap. Each benchmark was performed with a node count optimizing runtime while maintaining at least 70% parallel efficiency. Figures are reproduced from reference Understanding VASP Power Profiles on NVIDIA A100 GPUs

Computational chemistry

In quantum chemistry calculations, a substantial portion of the computational cost arises from solving the Hartree-Fock eigenvalue problem. A key step in this process is the diagonalization of the Fock matrix, whose elements are defined as:

\[F_{\alpha \beta} = H^{\textrm{core}}_{\alpha \beta} + \sum_{\gamma \delta}D_{\gamma \delta} \left [ (\alpha \beta|\gamma \delta) - \frac{1}{2} (\alpha \delta|\gamma \beta) \right ].\]

Note

Note: For this example, you do not need to understand the underlying principles of quantum chemistry. Instead, focus on the pseudocode shown in the figure below, paying particular attention to the for loops, if–else statements, and the overall control flow.

The first term corresponds to the one-electron contributions, whereas the second term represents the electron repulsion integrals (ERIs), shown in parentheses and weighted by the density matrix $D_{\gamma \delta}$. Processing the ERIs is one of the most computationally expensive steps in solving the Hartree–Fock equations. A representative algorithm for this process is shown below.

../../_images/quantum-chem-algorithms.png

Figure: Algorithm for processing ERIs. Figure is reproduced from reference Faster Self-Consistent Field (SCF) Calculations on GPU Clusters.

This algorithm is well suited for GPU acceleration because it involves a large number of arithmetic operations. Moreover, the symmetries and mathematical properties of the electron repulsion integrals can be exploited to reorganize the loop structure, enabling more efficient execution on GPU architectures.

Humanities

Below is a brief introduction to several areas of humanities research that can benefit from GPU acceleration.

Language models and natural language processing (NLP)

With the recent popularity of ChatGPT, large language models have entered the mainstream, although they have been used in the humanities for many years. A major focus of humanities research is the analysis of textual data, which has grown exponentially with the rise of social media. Extracting insights relevant to sociology, linguistics, and other disciplines increasingly relies on language models, making access to GPUs essential for training and deploying these computationally intensive models.

Archeology

Archaeology also benefits from GPUs through 3D modeling and rendering of excavation sites. Because archaeological sites are often altered or destroyed during excavation, preserving their original state is a major challenge. Advances in GPU computing now enable the creation of highly detailed 3D reconstructions, allowing researchers to preserve sites digitally and provide future archaeologists with valuable data for analysis and interpretation.

Cognitive science

Techniques such as Markov Chain Monte Carlo (MCMC) sampling have become valuable tools for studying human behavior and population dynamics. MCMC sampling enables researchers to simulate and analyze complex systems by iteratively sampling from a Markov chain, allowing efficient exploration of high-dimensional parameter spaces. This method is particularly valuable for studying human behavior, as it accounts for the inherent randomness and interdependencies that define complex social systems. By applying MCMC sampling, researchers can gain deeper insights into diverse aspects of human behavior, including decision-making processes, social interactions, and the transmission of information or diseases within populations.

By offloading the computational workload to GPUs, researchers can achieve substantial speedups in the execution of MCMC algorithms. This acceleration enables more extensive exploration of parameter spaces and facilitates the analysis of larger datasets, leading to more accurate and detailed insights into human behavior and population dynamics. Examples of studies using these methods can be found at the Center for Humanities Computing Aarhus (CHCAA) and the Interacting Minds Centre (IMC) at Aarhus University.

Exercises

Discussion

  • Do you know which parts of your code are the main performance bottlenecks?

  • Have you used profiling tools to identify the most time-consuming parts of your application?

  • Did you use GPUs to accelerate any computations or applications?

  • How much performance improvement did you get from GPU acceleration?

Good and bad use cases for GPU porting

Which of the following computational tasks is least likely to benefit from GPU acceleration?

  • A. Training a large, deep neural network.

  • B. Performing a Monte Carlo simulation with a large number of independent trials.

  • C. Executing an algorithm with extensive recursion and frequent branching.

  • D. Processing a large image using convolutional filters.

Keypoints

  • GPUs excel at processing tasks with high levels of data parallelism, such as large-scale matrix operations, Fourier transforms, and big data analytics.

  • GPUs are less effective for sequential tasks, workloads with significant control-flow divergence, low arithmetic intensity, small datasets, and memory-bound applications.

  • Identifying whether a workload is compute-bound or memory-bound is essential when evaluating GPU acceleration potential.

    • Compute-bound tasks with intensive arithmetic operations are typically better suited for GPUs.

    • Memory-bound tasks may require optimization of data movement and memory access patterns to achieve performance gains.