load balancing parallel

**Load Balancing** — distributing computational work evenly across parallel processors/threads so that no processor is idle while others are still working. **The Problem** - Total parallel time = time of the SLOWEST processor - If one core gets 60% of work and three cores share 40%, the speedup is only 1.7x instead of 4x - Load imbalance is the most common reason parallel speedup disappoints **Static Load Balancing** - Divide work equally upfront - Works well for regular, predictable workloads - Example: Matrix multiplication — split rows evenly among threads **Dynamic Load Balancing** - Assign work in small chunks; idle threads grab more work - Better for irregular or unpredictable workloads - Techniques: - **Work Queue**: Central queue, threads pull tasks when ready - **Work Stealing**: Idle threads steal from busy threads' queues (used in TBB, Java ForkJoinPool, Go runtime) - **Guided Scheduling**: Start with large chunks, decrease over time (OpenMP: `schedule(guided)`) **Measuring Imbalance** - $Imbalance = \frac{T_{max} - T_{avg}}{T_{avg}} \times 100\%$ - Target: < 10% imbalance **Key Insight** - More fine-grained tasks → better balance but more scheduling overhead - Optimal granularity balances load distribution against overhead costs **Load balancing** is essential at every scale — from threads in an application to jobs across data center servers.