load balancing parallel
**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**:
| Strategy | When to Use | Overhead | Balance Quality |
|----------|-----------|---------|----------------|
| **Static equal partitioning** | Uniform work per element | None | Poor if non-uniform |
| **Block-cyclic** | Moderate variation | None | Good for random variation |
| **Work stealing** | Irregular, fine-grained | Low-medium | Excellent |
| **Centralized queue** | Coarse tasks, few workers | Low (bottleneck risk) | Excellent |
| **Diffusion-based** | Iterative, changing load | Medium | Good, gradual |
| **Space-filling curves** | Spatial locality needed | Low | Good |
**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.**