Load Balancing Of Tasks
A parallel job finishes only when its slowest worker finishes. If work is spread unevenly, fast workers sit idle while one straggler grinds on. Load balancing keeps every worker productive.
Static versus dynamic
- Static balancing splits the work up front. It has no runtime overhead but assumes you can predict each piece accurately.
- Dynamic balancing assigns work as workers become free, adapting to unpredictable task costs at the price of coordination.
Work stealing
A popular dynamic scheme is work stealing. Each worker keeps its own queue of tasks. When a worker empties its queue it steals a task from a busy worker, usually from the opposite end of that worker queue:
- Local pushes and pops stay cheap.
- Steals are rare once load is balanced.
- Idle workers find work without a central bottleneck.
This is the backbone of many fork join runtimes and keeps cores busy even when task durations are wildly uneven.
Key idea
A job ends with its slowest worker, so dynamic schemes like work stealing keep idle cores busy and shrink the finish time.