Load balancing

What Load Balancing Means in Parallel Computing

In a parallel program, multiple processors (or cores, or nodes) work together on a problem. Load balancing is about making sure each of them gets “about the same amount of useful work” so no resources sit idle while others are overloaded.

More formally, for $P$ processing elements (PEs) with execution times $T_1, T_2, \dots, T_P$:

• The parallel runtime is dominated by the slowest (most heavily loaded) PE:
  $$T_{\text{parallel}} \approx \max_i T_i$$
• Even if the total work is fixed, imbalance (large variation between $T_i$) increases this maximum and wastes potential speedup.

Load balancing is therefore central to turning available hardware parallelism into actual performance.

Types of Load Imbalance

Load imbalance can arise from many causes. It helps to distinguish several common types.

Static vs dynamic imbalance

• Static imbalance
• Work per task or data element is known in advance or at least does not change much during execution.
• Example: each iteration of a loop performs a constant number of floating-point operations.
• You can often fix this with a good initial partitioning of work.
• Dynamic imbalance
• Work per task depends on runtime conditions (data, convergence behavior, branching).
• Example: some grid points require more iterations to converge; some particles interact with many neighbors, others with few.
• Requires mechanisms that adapt during execution (dynamic scheduling, work stealing, repartitioning).

Computational vs communication imbalance

• Computational imbalance
• Some PEs do far more computation than others.
• Caused by uneven distribution of data or by algorithms that take longer on certain inputs.
• Communication imbalance
• Some PEs do much more communication or wait longer on messages.
• A PE that must receive data from many neighbors, or handle I/O for others, can become a bottleneck.
• Can appear even when computational work is evenly distributed.

In practice, both often interact: a PE that does extra work may also send more messages, further delaying others.

Algorithmic vs architectural imbalance

• Algorithmic imbalance
• Rooted in the algorithm’s structure.
• Example: tree-based computations where upper levels have fewer nodes; sparse matrices with highly irregular non-zero patterns.
• Architectural imbalance
• Rooted in the underlying hardware or system configuration.
• Example: some nodes share a slower file system path, or some have slower memory, or there is an asymmetric network topology.

Good load-balancing strategies must respect algorithmic constraints and hardware realities.

Metrics for Load Balancing

To reason about and quantify load balance, several simple metrics are commonly used.

Load balance ratio

For $P$ PEs with execution times $T_i$ and maximum load $T_{\max} = \max_i T_i$:

• Ideal parallel time (if all PEs were perfectly balanced) would be approximately:
  $$T_{\text{ideal}} \approx \frac{1}{P} \sum_{i=1}^P T_i$$
• Load balance ratio:
  $$L = \frac{T_{\text{ideal}}}{T_{\max}}$$

Values:

• $L = 1$ means perfect balance (in practice, rarely reached).
• Lower $L$ means worse imbalance. For example, $L = 0.7$ means you are effectively using only 70% of the aggregate computing power.

Idle time and utilization

• Idle time for PE $i$:
  $$I_i = T_{\max} - T_i$$
• Total idle time:
  $$I_{\text{total}} = \sum_{i=1}^P I_i$$

High idle time indicates that PEs finished early and waited for others (or for communication).

• Utilization can be defined as:
  $$U = \frac{\sum_i T_i}{P \cdot T_{\max}} = L$$

So load balance and utilization are tightly coupled.

Relation to parallel efficiency

Parallel efficiency (introduced in the general parallel concepts chapter) is:

$$E = \frac{T_{\text{serial}}}{P \cdot T_{\text{parallel}}}$$

A common decomposition separates efficiency losses into:

• Algorithmic and overhead effects (communication, synchronization, extra work)
• Load imbalance

Even if communication and overhead were ideal, poor balance alone could cap $E$ by the load balance ratio $L$.

Static Load-Balancing Techniques

Static techniques decide the work distribution before or at program startup and do not adapt later.

They are suitable when:

• Work per task is predictable;
• Data and its structure are known and stable;
• Overhead of rebalancing at runtime would be too high.

Simple data partitioning

Many shared- and distributed-memory codes parallelize loops over arrays or grids. Common static schemes:

• Block partitioning (contiguous blocks)
• Each PE gets a contiguous block of indices or data.
• Easy to implement and often cache-friendly.
• Example: with $N$ iterations and $P$ PEs, PE $k$ gets:
  $$\text{indices } i \in \left[\left\lfloor\frac{kN}{P}\right\rfloor, \left\lfloor\frac{(k+1)N}{P}\right\rfloor - 1\right]$$
• Works well when each index has similar cost.
• Cyclic partitioning
• Indices assigned in round-robin fashion:
• PE $k$ gets iterations $i$ such that $i \equiv k \pmod P$.
• Helps when loop iterations differ in cost with some regular pattern.
• Block-cyclic partitioning
• Combine both ideas: assign small contiguous blocks in a cyclic pattern.
• Controls granularity: smaller block size improves balance but costs more overhead.

These patterns appear both in shared-memory scheduling (e.g. OpenMP) and in distributed-memory domain decompositions.

Geometric domain decomposition

For structured grids (e.g. regular meshes), a common approach is to decompose the spatial domain:

• 1D/2D/3D decomposition
• Divide the spatial domain into subdomains, each assigned to a PE.
• Shapes can be slabs, pencils, or blocks, depending on PDE stencil patterns and communication requirements.

Static geometric partitions:

• Aim to give each PE the same number of grid points;
• Attempt to minimize the surface area between subdomains (to reduce communication).

When the computational cost per grid point is uniform, this can give very good balance with low overhead.

Graph and hypergraph partitioning (conceptual overview)

For irregular problems (unstructured meshes, sparse matrices, graphs), pure geometric cuts are often suboptimal.

Conceptually:

• Model computation as a graph:
• Vertices represent units of work (cells, nodes, unknowns).
• Edges represent dependencies or communications.
• Partition the graph into $P$ parts:
• Each part has roughly equal total vertex weight (work).
• Edge cuts (communication between parts) are minimized.

Hypergraphs extend this idea to better capture communication patterns (e.g., collective communication of multiple neighbors).

Static graph/hypergraph partitioning is common in:

• Finite element codes
• Sparse linear algebra
• Network and social graph analytics

Dynamic Load-Balancing Techniques

Dynamic methods adjust the work distribution during runtime, reacting to imbalance as it arises.

They are valuable when:

• Work per task is data-dependent or changes over time;
• The problem evolves (adaptive mesh refinement, changing active regions);
• You cannot predict load accurately up front.

Dynamic task scheduling

In shared-memory environments, a simple and powerful approach is to break work into many fine-grained tasks and assign them dynamically.

Concepts:

• Task queues
• Tasks (e.g. loop chunks, small independent jobs) are inserted into a queue.
• Threads repeatedly dequeue a task, execute it, and fetch the next one.
• When some threads finish early, they simply take more tasks.
• Work stealing
• Each worker (thread or PE) maintains its own deque of tasks.
• When a worker runs out of tasks, it attempts to “steal” tasks from others.
• Reduces contention on a single global queue and adapts to unpredictable workloads.

Key trade-offs:

• Many small tasks improve balance but increase overhead (task creation, scheduling).
• Larger tasks reduce overhead but can cause imbalance.

Adaptive repartitioning and load migration

In distributed-memory systems, dynamic balancing often involves moving data and associated work between processes.

Examples:

• Adaptive mesh refinement (AMR)
• Regions of interest in a simulation are refined (more grid points).
• Subdomains that become too large or too active are split or migrated to less-loaded processes.
• Particle and agent simulations
• Particles or agents move around the domain, accumulating in some regions.
• Load balancers periodically redistribute regions or particle ownership.

The typical cycle:

1. Measure current load (e.g. number of elements, time per step) per process.
2. Decide a new partition (possibly using approximate heuristics or incremental graph partitioning).
3. Migrate data (send elements, update ghost zones, reassign tasks).
4. Resume computation with improved balance.

Dynamic repartitioning has nontrivial communication cost and complexity; it must be used judiciously.

Work stealing in distributed memory (conceptual)

The work-stealing idea extends to distributed memory, but with added complexity:

• Idle processes send requests for more work to others.
• Donor processes send tasks or subdomains.
• Requires careful design to avoid excessive communication and synchronization.

Such systems are more common in runtime systems for irregular applications (graph analytics, tree searches) than in traditional bulk-synchronous PDE solvers.

Sources of Load Imbalance in Common HPC Workloads

Understanding where imbalance comes from in typical HPC applications helps in designing appropriate remedies.

Spatially varying physics

• In many simulations, some regions are more active:
• Combustion in a small flame zone vs. mostly inert surroundings.
• Strong turbulence in specific subregions.
• If each subdomain nominally has the same number of cells, but some cells need far more work (e.g. complex chemistry), subdomains covering active regions become overloaded.

Convergence variability

• Iterative methods (e.g. nonlinear solvers, local relaxation) may converge at different rates in different regions.
• Multigrid methods or domain decomposition preconditioners can show:
• Some subdomains needing many iterations;
• Others converging quickly.
• Per-subdomain work becomes highly uneven.

Branching and adaptivity

• Algorithms with strong branching:
• Ray tracing where some rays traverse many objects, others terminate early.
• Monte Carlo methods where paths can terminate quickly or continue for many steps.
• Adaptive methods:
• Refinement of particles or cells only where needed.
• Dynamic adjustment of time steps or model complexity.

These fundamentally produce variable amounts of work per basic element.

I/O and auxiliary tasks

• Some PEs may perform extra tasks:
• Writing checkpoints or output;
• Doing additional diagnostics or post-processing;
• Acting as “masters” or coordinators in certain algorithms.

If not carefully designed, these extra roles create systemic imbalance.

Load Balancing in Shared vs Distributed Memory

How you implement load balancing depends on whether parallelism is within a node or across nodes.

Shared-memory environments

In shared-memory programming models (like OpenMP):

• Loop scheduling is the primary tool:
• Static, dynamic, guided chunking strategies.
• Tasks allow fine-grained and irregular parallelism with flexible scheduling.
• Load balancing is relatively easy to implement:
• All threads can see shared task queues and data;
• Task or chunk reassignment is cheap compared with distributed-memory migration.

However, you must also:

• Avoid creating too many tiny tasks (overhead, cache effects).
• Minimize contention on shared queues or locks.

Distributed-memory environments

In MPI-like models:

• Data is partitioned across processes, usually with a fixed mapping to nodes.
• Balancing load often requires redistributing data:
• Changing ownership of cells, particles, matrix rows, etc.
• Updating mappings, communicators, and neighbor lists.

Challenges include:

• Extra communication volume during repartitioning.
• Complexity of updating data structures and communication patterns.
• Ensuring that the cost of rebalancing does not exceed the performance gained.

Hybrid models (e.g. MPI + OpenMP) can combine both:

• Use static or semi-static distribution across nodes.
• Use flexible, dynamic scheduling within each node.

Trade-offs and Costs of Load Balancing

Load balancing is never free. It introduces overheads in:

• Decision making (computing how to redistribute work).
• Data movement (migrating tasks or data).
• Synchronization and task-management costs.

When balancing helps vs hurts

Balancing is beneficial when:

• The cost of imbalance dominates runtime (large idle times).
• The problem is large and long-running, so amortized gains are substantial.
• Structural imbalance is persistent (not just a transient fluctuation).

Conversely, aggressive balancing can be counterproductive if:

• The imbalance is minor or short-lived.
• Rebalancing is extremely expensive (e.g. moving large data structures across the network).
• Overhead of fine-grained scheduling destroys cache locality and increases synchronization.

Choosing granularity

A key design parameter is granularity:

• Coarse-grained work units
• Less overhead (fewer tasks or migrations).
• More potential for imbalance.
• Good for regular problems where cost per unit is predictable.
• Fine-grained work units
• Better load balance: easier to redistribute small chunks.
• More overhead: task scheduling, communication, and bookkeeping.
• Good for highly irregular or unpredictable workloads.

A practical strategy is often:

• Start with moderate granularity;
• Measure imbalance and overhead;
• Adjust task size or partitioning accordingly.

Practical Strategies and Heuristics

In real HPC projects, load balancing is rarely “perfect”. Simple, robust heuristics are often more productive than complex optimal schemes.

Over-decomposition

Instead of having one large chunk of work per PE, over-decompose the problem into more subdomains or tasks than PEs:

• Example:
• 4,000 blocks of work for 400 PEs (10 blocks per PE on average).
• Allow a runtime system or simple scheduler to:
• Distribute these blocks initially;
• Redistribute some blocks if imbalance appears.

Over-decomposition:

• Increases flexibility for both static and dynamic strategies.
• Enables basic work stealing or load stealing between PEs.

Periodic measurement and rebalancing

Implement a simple loop in time-stepping simulations:

1. Measure per-PE work (e.g. time per step, number of elements).
2. If imbalance exceeds a chosen threshold (say, 20–30%):
• Trigger a rebalance step.
3. Adjust threshold and frequency based on observed benefit.

This avoids constant small migrations and focuses on correcting real issues.

Role specialization vs distributed responsibilities

When some tasks are inherently centralized (I/O, coordination):

• Option 1: Dedicated role
• Assign them to a subset of PEs; accept some imbalance.
• But try to keep extra work small relative to main computation.
• Option 2: Distributed responsibilities
• Spread I/O or control tasks among many PEs to avoid single-PE bottlenecks.
• Increases code complexity but may improve scalability.

Choosing between them depends on the relative cost and frequency of these auxiliary operations.

Recognizing Load Imbalance in Practice

Even before using sophisticated profiling tools, a few observations can often indicate load imbalance.

Observable symptoms

• Some PEs finish much earlier:
• In job logs or runtime prints, some ranks finish iterations or phases significantly faster.
• Profiling timelines show gaps:
• Many PEs idle in barrier or wait states while a few are still running.
• Scaling stalls
• Increasing the number of PEs no longer improves speedup as expected.
• Profiling reveals that a small subset of PEs dominates the runtime.

Simple diagnostics

Basic strategies:

• Measure per-PE time:
• e.g., each process prints its local step time or total runtime.
• Compute mean and maximum; derive an approximate load balance ratio.
• Count work units:
• Track counts of processed grid cells, particles, tasks, etc. per PE.
• If there is a large spread, but work units should be similar in cost, you likely have imbalance.
• Investigate communication patterns:
• If some PEs send or receive far more messages than others, their load may be communication-heavy rather than compute-heavy.

Summary

Load balancing is about distributing work so that all processing elements are kept busy, minimizing idle time and maximizing efficiency. Important points:

• Parallel runtime is dictated by the most heavily loaded PE.
• Imbalance arises from algorithmic structure, data irregularity, adaptivity, and auxiliary roles like I/O.
• Static techniques (block, cyclic, geometric, graph partitioning) are suitable for predictable workloads.
• Dynamic techniques (task-based scheduling, work stealing, adaptive repartitioning) address unpredictable or evolving workloads.
• Load balancing introduces overhead; its benefits must outweigh its costs.
• Practical strategies rely on moderate granularity, over-decomposition, periodic measurement, and targeted rebalancing.

Understanding and managing load balance is essential for achieving good strong and weak scaling on modern HPC systems.