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.