Load balancing

Understanding Load Balancing in Parallel Programs

Load balancing is about making sure that all processing elements in a parallel program, whether threads, cores, or MPI processes, have roughly the same amount of useful work to do at any given time. When this does not happen, some resources sit idle while others are overloaded, and total runtime is determined by the slowest or most heavily loaded part.

In this chapter, the focus is on what load imbalance looks like, what causes it, how it interacts with different kinds of parallelism, and what basic strategies you can use to mitigate it in high performance computing codes.

What Load Imbalance Looks Like

In an ideal parallel execution with $P$ processing elements and total work $W$, each element would perform $W / P$ units of work, and they would all finish at the same time. In practice, some elements finish early and wait, while others continue to compute. This wait time is idle time and represents a loss of potential speedup.

A simple way to think about load imbalance is to imagine a team project where the grade is given when everyone is done. If a few people do most of the work while others sit around waiting for instructions or for data, the project finishes later than it would if the work were divided more evenly. The same idea applies to parallel programs.

In shared memory, idle time often appears as a few threads still active while the rest sit at a synchronization point, for example at the end of a parallel loop. In distributed memory, some MPI ranks may wait in communication calls because others are still computing.

Two simple metrics are often used informally when thinking about load balance:

1. Maximum local work: the largest amount of work assigned to a single processing element.
2. Imbalance ratio: $\text{max\_work} / \text{average\_work}$.

If this ratio is close to 1, the load is well balanced. If it is much larger than 1, the imbalance is severe.

Sources of Load Imbalance

Load imbalance rarely appears by accident. It usually arises from features of the problem, of the algorithm, or of the way work is assigned to processing elements.

Data-dependent or irregular work

Many scientific and engineering applications do not have uniform work per data item. For example, a simulation might spend more time computing where the physics is complicated, or a mesh may be locally refined in a region of interest. A graph or network problem might have nodes with widely differing degrees. Simple partitioning strategies that assume each element is equal then lead to imbalance.

For instance, if you split a spatial domain into equal sized blocks and assign one block per process, but some blocks contain features that require much more computation, the processes that own those blocks become bottlenecks.

Algorithmic branching and adaptivity

Algorithms with conditionals, early exits, or adaptive refinement can create different paths and different workload per task. Even if the input data is evenly distributed, the actual execution time per element may vary a lot. Adaptive mesh refinement, multigrid methods with dynamic levels, or iterative methods with data-dependent convergence are all prone to this.

Static assignment of highly variable tasks

Static assignment means that work is allocated once at the start and then does not change. If task sizes vary or are not known accurately in advance, a static partition often leaves some workers underused. This is particularly common in task parallel programs where some tasks are cheap and others are expensive, but they are allocated before their true cost is known.

Communication and synchronization overhead

Even if the computational work is balanced, communication or synchronization can lead to effective imbalance. A process that must wait for late messages or for locks to be released is idle, even if its own computation is not heavy. If some processes participate in more communication than others, or if barriers are used frequently, then faster processes repeatedly wait for slower ones.

In distributed memory codes, global collectives like MPI_Allreduce will not complete until every rank has arrived. If a few ranks have heavier computation or slower I/O, they hold back the rest.

I/O and heterogeneous performance

Practical HPC environments are not always uniform. Some nodes may be slower due to hardware variation, thermal throttling, or sharing I/O paths. If a program does significant I/O per process, variation in I/O performance can manifest as load imbalance, since some processes finish their I/O early and sit idle.

In heterogeneous systems with accelerators, different types of processing elements have different speeds. Giving equal work to a CPU and a GPU, for instance, usually causes the GPU to wait for the CPU, unless the workload is proportionally scaled.

Load Balancing in Different Parallel Models

The way you detect and address load imbalance depends strongly on the style of parallelism used. The core idea is the same, but the mechanisms differ.

In shared memory and OpenMP style programs

In shared memory, parallel loops are common. A basic strategy is to divide loop iterations evenly among threads. If each iteration has about the same cost, this can work well. But when some iterations take much longer than others, a naive static schedule can be very imbalanced.

The main features that affect load balancing here are:

1. How iterations of a loop are assigned to threads.
2. Where synchronization points such as barriers and locks are placed.
3. How data is laid out, which can change effective cost due to cache effects and false sharing.

If, for example, the first half of the loop has cheap iterations and the second half has expensive ones, a static contiguous partition that assigns the first half to some threads and the second half to others will create severe imbalance. Threads with cheap iterations will reach the end of the loop and then wait for the others at the implicit barrier.

In distributed memory and MPI style programs

With distributed memory, load balancing generally means distributing data and associated work across MPI ranks so that each rank has a similar amount of computation and communication. This often involves domain decomposition, where the physical or logical domain of the problem is split into subdomains.

Simple decompositions such as splitting an array in equal blocks can work when work per element is uniform. For irregular meshes or graphs, more advanced partitioning based on structure and connectivity is needed to balance both computation and communication.

Communication patterns also matter. A process that owns a region with many neighbors or with long interfaces may need more communication than others. Even if its computation is balanced, communication overhead can create effective imbalance.

In MPI programs, you usually cannot dynamically move data and work between processes without explicit implementation. This makes load balancing a design problem, not just a runtime setting.

In task based and hybrid programs

Task based models, whether implemented with OpenMP tasks, MPI plus a task scheduler, or runtime systems, introduce another level. Work is decomposed into tasks, and a runtime assigns these to workers. Load balancing depends on task granularity and on how tasks are scheduled and possibly stolen from busy workers.

Hybrid programs that combine MPI and threads bring additional complexity. You must think about balance between nodes (MPI ranks) and also within each node (threads or GPU kernels). A good global balance can still fail if one node is internally imbalanced, or if some nodes map badly to the hardware.

Static vs Dynamic Load Balancing

Load balancing techniques fall broadly into two categories: static and dynamic. Each has advantages and tradeoffs. For many real HPC applications, some combination of both is used.

Static load balancing

Static load balancing decides how to distribute work at or before the start of the computation, and then does not change this assignment. The decision is based on problem geometry, estimated costs, or empirical measurements from previous runs.

Typical static approaches include:

Even partitioning by index or space, for example splitting a 1D array into contiguous chunks of size $N / P$.
Geometric domain decompositions, such as block or block-cyclic layouts for multidimensional grids.
Graph or mesh partitioning done once, using tools that try to minimize edge cuts while balancing node weights.

Static approaches have low runtime overhead and are predictable, which is helpful for debugging and performance tuning. They work well when the distribution of work is known and does not change much in time.

However, static balancing can fail if the workload changes during the run. This is true in adaptive methods, problems where physical features move around, or simulations with time varying behavior.

Dynamic load balancing

Dynamic load balancing adjusts the assignment of work while the program runs. The goal is to react to imbalances as they appear, rather than trying to predict them perfectly in advance.

There are two main forms:

1. Dynamic scheduling of tasks or iterations, where idle workers request more work from a central queue or from other workers.
2. Dynamic repartitioning of data, where the ownership of part of the domain is moved between processes or threads.

Dynamic schemes introduce overhead, both computational and communicational. They can also complicate reasoning about data locality and cache reuse. However, they can significantly improve effective utilization and reduce runtime in the presence of unpredictable or changing workloads.

Practical Load Balancing Strategies

Although many sophisticated methods exist, several practical strategies show up again and again in HPC codes. These are not tied to any particular programming model, but the implementation details differ.

Chunking and scheduling strategies for loops

In shared memory, parallel loops often support different scheduling strategies. For example, work may be divided into fixed size chunks and assigned once, or assigned in smaller chunks at runtime as threads become free.

Small chunks improve adaptability, because faster threads can pick up extra chunks. Larger chunks reduce scheduling overhead and may improve cache reuse. There is usually a tradeoff between overhead and balance.

When iteration cost is highly irregular, using a guided or dynamic schedule with appropriate chunk size can dramatically reduce idle time at the end of loops.

Domain decomposition and geometric partitioning

For problems defined over a physical or logical domain, geometric decomposition is frequently used. The domain is partitioned into subdomains that are assigned to processes. To obtain better balance and communication behavior, partitions are chosen to satisfy at least two goals:

1. Similar computational load per subdomain.
2. Minimal surface area or boundary length between subdomains, to reduce communication.

For uniformly discretized grids, simple block or block-cyclic decompositions can work. For irregular meshes or particle systems, more advanced geometric heuristics or space filling curves are used to create partitions that reflect the underlying work distribution.

When the domain changes or when regions become more expensive, periodic re-partitioning can help maintain balance. This is a form of dynamic load balancing at the domain level.

Graph and mesh partitioning

Irregular problems such as unstructured meshes or graphs require more sophisticated approaches. These can be represented as graphs where nodes carry computational cost and edges represent communication. The goal is to split the graph into parts with roughly equal node weight and minimal cut edges.

Specialized partitioning libraries implement heuristic algorithms that provide good partitions in practice. They can be used offline before a run or invoked during the run to rebalance.

In many applications, the partition is updated occasionally, not at every time step. This amortizes the cost of repartitioning.

Master worker and work stealing schemes

In task oriented codes, a common strategy is to use a master worker pattern. A master process or thread maintains a pool of tasks. Workers repeatedly request a task, perform it, and return for more. When tasks have uncertain or highly variable cost, this central pool helps balance the load, since faster workers simply complete more tasks.

However, a single master can become a bottleneck. To avoid this, some designs distribute work queues and use work stealing. Each worker owns a queue. When its queue is empty, it steals tasks from others. This tends to equalize the number of tasks across workers without a central coordinator.

Work stealing provides a natural way to adapt to both unknown and changing workloads, but can introduce additional overhead and complexity, including contention on task queues and more irregular memory access patterns.

Measuring and Diagnosing Load Imbalance

To improve load balance, you first need to observe it. On real HPC systems, you do not just guess, you measure. Although details of tools are covered elsewhere, it is useful to know how load imbalance usually appears in measurements.

Timing per process or thread

The simplest and most direct approach is to measure how much time each processing element spends in a critical region of code. If you record local runtimes and then inspect their minimum, maximum, and average, you immediately see any imbalance.

For example, if threads or ranks perform the same nominal kernel, but some take twice as long as others, then the slower ones define your effective runtime. A similar idea applies to counting the number of iterations or tasks completed per worker.

Plotting per rank or per thread runtime is often very revealing. In a well balanced code, these bars have similar height. In an imbalanced code, you see a few much higher bars and many low ones.

Idle and wait time

Modern profiling tools can distinguish between time spent in useful computation and time spent waiting at barriers, in MPI calls, or blocked on locks. Large amounts of wait time are a sign that other processing elements are late and that the program is limited by them.

If you see, for example, that most of the total wall clock time is accounted for by a small number of processes, and that others spend their time waiting, then you know you have a load balancing problem.

Scaling behavior

Load imbalance also reveals itself when you scale to more cores or nodes. Sometimes, performance improves when you go from 1 to 4 processes, but then gains slow dramatically beyond that. While many effects can cause this, load imbalance is a frequent contributor.

If, as you increase $P$, you see that the amount of work per processing element does not decrease as $W / P$, but levels off because some workers are always slower, you are hitting limits imposed by imbalance and other overheads. Improving the balance can extend the range where scaling is efficient.

Tradeoffs in Load Balancing Decisions

Improving load balance is not always free. In some cases, the simplest apparent fix can reduce performance overall, even if measured imbalance improves. Effective load balancing asks you to weigh several tradeoffs.

Locality versus balance

Many static partitions are designed to preserve data locality. When each processing element works on a contiguous region of memory or on a localized domain region, cache performance can be very good and communication can be minimal. Dynamic methods that move tasks or data can disrupt this, increasing memory traffic and communication distances.

A nearly perfect balance achieved at the cost of much worse locality can be slower than a slightly imbalanced but local arrangement. You need to consider both sides.

Overhead versus benefit

Dynamic methods often rely on runtime scheduling, communication of work units, or repartitioning operations. Each of these costs time. If tasks are very small, the overhead of scheduling can dominate. In such cases, larger static chunks with some imbalance may be better.

A practical rule is to ensure that each unit of work assigned by a dynamic scheduler is large enough that the cost of assigning it is small compared to the useful computation. The ideal task size depends on the runtime, the hardware, and the cost distribution.

Predictability and complexity

Sophisticated load balancing schemes can be difficult to implement and reason about, especially in production codes that must be correct, maintainable, and portable. Frequent data migration or complex task stealing logic can make debugging harder.

Sometimes a simple static balance coupled with a small amount of dynamic correction is preferable to a fully dynamic system. The right design depends on problem characteristics and on development constraints.

Common Patterns of Load Balancing in HPC Applications

Although applications are diverse, some recurring patterns exist in how real HPC codes tackle load balancing.

Time stepping simulations with static domains

Many simulations advance a fixed spatial domain through time with relatively uniform work per cell. For these, a well chosen static partition can provide good balance and excellent locality, and dynamic methods are unnecessary.

Here, load balancing appears primarily when new physics is added that concentrates work in certain regions, or when input data is very nonuniform. In such cases, developers may refine the static partition, perhaps using better domain decomposition, rather than add heavy dynamic logic.

Adaptive simulations and moving features

In adaptive mesh refinement and related methods, the mesh changes during the simulation, and fine regions move or grow. Periodic dynamic load balancing is standard here. The code may periodically remeasure the load per region, build a new partition, and migrate data to match.

Between rebalancing steps, the program often relies on a static partition of the then current mesh. Choosing how often to rebalance involves a compromise between keeping the balance good and keeping overhead manageable.

Irregular linear algebra and graph problems

Sparse linear algebra, graph analytics, and combinatorial problems often have inherently irregular structure. Load balancing here may rely on sophisticated graph partitioning and sometimes on runtime dynamic tasking for operations like sparse matrix vector multiplication or graph traversal.

Work stealing or queue based task distribution can help deal with unpredictable branching in algorithms like breadth first search or parallel graph coloring.

Data parallel analysis on large datasets

In data analysis and machine learning, operations may be applied to large but uneven datasets. Some subsets may process more slowly due to longer sequences, more complex features, or more I/O. Batch or shard sizes can be adjusted to take into account known differences in processing time, or dynamic task queues can provide better balance than fixed partitions.

Thinking About Load Balancing When Designing Codes

For beginners, load balancing may seem like an advanced topic, but it is helpful to think about it early rather than only in response to bad performance later. You can keep a few guiding questions in mind when designing a parallel algorithm.

First, ask whether the work per data item or per region is roughly uniform and predictable. If the answer is yes, a simple static scheme may be enough. If not, you should design for some dynamic flexibility.

Second, consider how the problem might evolve during a run. If important regions move, or if the cost per region changes, you might need a way to adapt your partition or your task assignment.

Third, think about how easy it will be to measure and diagnose imbalance in your design. Leaving room for per process timing, per thread counters, and simple tracing from the beginning pays off later when you try to optimize.

Finally, remember that load balancing is not separate from the rest of performance. It interacts with memory hierarchy, communication costs, algorithmic complexity, and even numerical methods. Good HPC codes treat it as a first class design concern, not just a late stage fix.