Dynamic Load Balancing is the runtime distribution and redistribution of workload across parallel processing elements to minimize idle time and maximize throughput, addressing the fundamental challenge that in many parallel applications, work per task is unknown or variable, making static (compile-time) work division suboptimal.

Load imbalance is one of the primary reasons parallel applications fail to achieve ideal speedup: if one processor takes 2x longer than others on its assigned work, parallel efficiency drops to 50% regardless of the number of processors.

Load Balancing Strategies:

Work Stealing: Each processor maintains a local deque (double-ended queue) of tasks. Processors execute tasks from the bottom of their own deque (LIFO for cache locality). When a processor's deque is empty, it randomly selects a victim processor and steals tasks from the top of the victim's deque (FIFO — steals the largest undivided task). Theoretical guarantee: work stealing achieves optimal O(T_1/p + T_inf) completion time with O(p * T_inf) total stolen tasks (where T_1 is serial work, T_inf is critical path length). Implemented in: Intel TBB, Cilk, Java ForkJoinPool, Tokio (Rust).

Centralized vs. Distributed: Centralized (single task queue) — simple, optimal balance, but the queue becomes a bottleneck at >16-32 workers. Distributed (per-worker queues with stealing or migration) — scales to thousands of workers but may have transient imbalance during migration. Hierarchical — centralized within NUMA nodes, distributed across nodes — matches hardware topology.

Diffusion-Based Balancing: Each processor periodically exchanges load information with neighbors. If a neighbor is less loaded, transfer work proportional to the load difference. Converges to balanced state in O(diameter * log(n/epsilon)) iterations. Well-suited for iterative applications (PDE solvers, particle simulations) where load changes gradually between iterations.

Metrics and Detection: Load imbalance ratio = max_load / avg_load (ideal = 1.0, typical threshold > 1.1 triggers rebalancing). Idle time fraction = total idle time / (p * makespan). Monitoring overhead must be smaller than imbalance cost — lightweight sampling (periodic load queries) rather than continuous monitoring.

Practical Considerations: Granularity tradeoff — finer tasks enable better balance but increase scheduling overhead (optimal: execution time per task >> scheduling overhead, typically >10 microseconds per task); data locality — moving work to a different processor may invalidate caches or require data migration, partially offsetting the balance benefit; determinism — non-deterministic load balancing complicates debugging and reproducibility.

Dynamic load balancing transforms the theoretical promise of parallel speedup into practical reality — without it, irregular applications like adaptive mesh refinement, graph analytics, and tree search would achieve a fraction of their potential parallel performance.