Load Balancing
Distributing work evenly across processors or machines so none sits idle while others are overloaded.
Definition
Load balancing divides work across processing units so that each does a roughly equal share, minimizing the time others wait for the slowest. Imbalance wastes resources, since a parallel job is only as fast as its most loaded worker.
Irregular and adaptive workloads, where the cost per unit of work is unknown in advance, are the hard case; here dynamic schemes that reassign work at runtime outperform any fixed partition. The overhead of moving work must stay small relative to the imbalance it corrects.
Balance is easy when work is uniform and known in advance and hard when it is irregular or changes over the course of a computation. Dynamic schemes that redistribute work at runtime handle the difficult cases but add overhead that must stay small relative to the imbalance they correct. Since a parallel job is only as fast as its slowest worker, achieving good balance is often the decisive factor in whether a code scales.
Strategies
- Static: fixed partitioning decided in advance.
- Dynamic: work reassigned at runtime as loads shift.
- Work stealing: idle workers take tasks from busy ones.
Why it matters
Load balancing is essential to scalability: even perfect parallel code scales poorly if work is unevenly distributed. It is challenging when the workload is irregular or changes over the course of a computation.
Fusion connection
When a plasma simulation concentrates activity in one region, dynamic load balancing redistributes mesh subdomains so no processor is left waiting, keeping the whole cluster busy.