work stealing scheduler

**Work-Stealing Schedulers** are **dynamic load-balancing runtimes that distribute fine-grained parallel tasks across worker threads using per-worker double-ended queues (deques) — achieving provably optimal load balance through randomized victim selection while maintaining cache locality for the common case of local task execution**. **Work-Stealing Protocol:** - **Deque Operations**: each worker thread maintains a local deque; new tasks are pushed onto the bottom (LIFO order); the worker pops tasks from its own bottom — local operations require no synchronization (single-thread access to the hot end) - **Stealing**: when a worker's deque is empty, it becomes a thief; the thief randomly selects a victim worker and steals a task from the top (FIFO end) of the victim's deque using an atomic CAS operation — stealing is the uncommon case, requiring synchronization only when it occurs - **LIFO Local / FIFO Steal**: local consumption in LIFO order processes the most recently spawned (smallest) tasks first, preserving cache locality and stack-like memory behavior; stealing in FIFO order takes the oldest (largest) tasks first, maximizing the useful work transferred per steal **Theoretical Guarantees:** - **Space Bound**: work-stealing uses O(P·S₁) stack space where P is the number of workers and S₁ is the sequential stack depth — each worker's stack grows only from local execution, not from stolen tasks - **Time Bound**: expected completion time is T₁/P + O(T∞) where T₁ is total work (sequential time) and T∞ is critical path length (span); the O(T∞) term accounts for stealing overhead and is optimal up to constant factors - **Steal Frequency**: expected number of steals is O(P·T∞) — for computations with high parallelism (T₁/T∞ ≫ P), steals are rare and most time is spent executing local tasks with full cache locality - **Randomized Analysis**: random victim selection provides probabilistic load balance; each thief steals from one of P-1 potential victims with equal probability; analysis relies on potential function arguments showing quick convergence to balanced state **Implementations:** - **Cilk/Cilk Plus**: the original work-stealing system; cilk_spawn and cilk_sync create tasks from parallel recursive decompositions; THE protocol handles deque synchronization with minimal overhead for the non-stealing case - **Intel TBB**: task_group and parallel_for/parallel_reduce use work-stealing internally; TBB adds task affinity hints and task priority features beyond basic work-stealing - **Java ForkJoinPool**: work-stealing executor for recursive decomposition tasks; RecursiveTask/RecursiveAction classes mirror Cilk's spawn/sync model with JVM garbage collection integration - **Tokio/Rayon (Rust)**: Rayon provides data-parallel iterators with work-stealing backend; Tokio uses work-stealing for async task scheduling — both leverage Rust's ownership model to prevent data races at compile time **Engineering Considerations:** - **Task Granularity**: tasks too small (<1 μs) create deque management overhead exceeding useful work; tasks too large (>10 ms) limit load-balancing responsiveness; sequential cutoff (switching to sequential algorithm below threshold size) tunes granularity - **Memory Allocation**: rapid task creation/destruction requires efficient allocators; per-worker memory pools avoid contention on global heap; task objects are often stack-allocated through continuation-stealing rather than child-stealing - **NUMA Awareness**: pure random stealing ignores memory locality; NUMA-aware policies prefer stealing from same-socket workers before cross-socket; hierarchical stealing reduces cross-socket memory traffic by 2-5× - **Cache Pollution**: stolen tasks execute on a different core with cold caches; for data-intensive tasks, the cache warm-up cost may exceed the load-balancing benefit — affinity-based scheduling variants preserve locality at the cost of potential imbalance Work-stealing schedulers are **the gold standard for dynamic task-parallel load balancing — combining provably optimal theoretical guarantees with practical efficiency, they power the runtime systems of Cilk, TBB, Java ForkJoinPool, and modern parallel programming frameworks**.