Load Balancing
Load balancing distributes work evenly across processors so none sits idle waiting for an overloaded peer; imbalance caps scaling.
The idle-processor problem
A parallel computation finishes only when its slowest processor finishes. If work is unevenly distributed, lightly loaded processors sit idle at synchronization points while heavily loaded ones grind on. This load imbalance is one of the most common reasons real codes fall short of ideal scaling.
Static balancing
When the cost of each work unit is known and stable, work can be partitioned once, up front. Grid-based simulations split the domain into equal-cost pieces; graph partitioners minimize the boundary (communication) while equalizing the interior (computation). Static balancing has no runtime overhead but fails when costs are unpredictable.
Dynamic balancing
- Work queues: idle workers pull the next task from a shared pool
- Work stealing: idle workers take tasks from busy workers' queues
- Repartitioning: periodically redistribute the domain as costs shift
Sources of imbalance
Costs drift for many reasons: adaptive mesh refinement concentrates cells where physics is active; particle methods pile particles into some cells; convergence differs across subdomains; and hardware itself varies. In plasma simulation, turbulence and steep gradients make some regions far costlier than others, so periodic rebalancing is routine.
The cost of balancing
Rebalancing moves data and consumes time, so it is worthwhile only when the imbalance it removes exceeds its own cost. Good frameworks measure imbalance and trigger repartitioning adaptively, seeking the point where processors stay busy without excessive shuffling.