Load Imbalance
Load imbalance is uneven work across processes; at each synchronization point everyone waits for the slowest, wasting the difference.
The slowest sets the pace
In a bulk-synchronous parallel program, processes compute and then synchronize (a collective or barrier). At each synchronization point, every process waits for the last to arrive, so the phase takes as long as the slowest process. If work is unevenly distributed, faster processes idle while the busiest finishes. That idle time is pure waste, and it grows with the imbalance and with the number of synchronization points.
Where imbalance comes from
Imbalance arises whenever equal partitions do not mean equal work. Adaptive meshes refine some regions more than others; particle methods cluster particles unevenly; physics that varies in space (more collisions here, more chemistry there) makes some cells costlier; and irregular data structures give some processes more elements. It can also be dynamic, drifting as the simulation evolves, so a partition that was balanced at the start becomes unbalanced later.
- A synchronized phase costs as much as its slowest participant.
- Equal data does not imply equal computational work.
- Imbalance can be static (fixed by geometry) or dynamic (evolving).
- Barrier and collective wait time measures the imbalance directly.
Remedies
Static imbalance is addressed by weighting the partition: assign fewer mesh cells to a process that owns expensive cells so wall-clock work is even. Dynamic imbalance needs dynamic load balancing: periodically repartition and migrate work, or use a task-based runtime whose work stealing lets idle workers pull tasks from busy ones automatically. Overpartitioning (more subdomains than processes) also helps a scheduler even out the load.
In practice
A Hyperion run with an adaptively refined mesh concentrates cells, and cost, in regions of steep gradients. Partitioning by cell count alone would overload the ranks owning those regions; partitioning by an estimated per-cell cost, and repartitioning as refinement moves, keeps the ranks finishing together and cuts the wait time that dominates poorly balanced runs.