Task Parallelism and Work-Stealing Schedulers are the parallel programming model and runtime system where computation is decomposed into discrete tasks (units of work) that are dynamically scheduled across available processor cores — using work-stealing to automatically balance load by allowing idle cores to "steal" tasks from busy cores' queues, achieving near-optimal load balance without programmer intervention.

Task vs. Data Parallelism

Data parallelism applies the same operation to different data (SIMD, GPU kernels). Task parallelism applies different operations to potentially different data — a producer-consumer pipeline, recursive divide-and-conquer, or independent computations with complex dependencies. Task parallelism is essential for irregular workloads where data parallelism alone cannot extract all available concurrency.

The Fork-Join Model

The dominant task-parallel abstraction: 1. Fork: A task spawns child tasks that can execute in parallel. 2. Compute: Parent and children execute concurrently on different cores. 3. Join (Sync): The parent waits for all children to complete before proceeding.

Recursive algorithms (merge sort, tree traversal, graph search) naturally map to fork-join: each recursive call becomes a spawned task.

Work-Stealing Scheduler

• Each worker thread maintains a double-ended queue (deque) of ready tasks.
• A thread pushes new (spawned) tasks onto its local deque and pops tasks from the same end (LIFO — exploiting temporal locality).
• When a thread's deque is empty, it becomes a thief: it randomly selects another thread and steals a task from the opposite end (FIFO) of that thread's deque.
• Why FIFO stealing works: Older tasks (near the bottom of the deque) are typically larger (closer to the root of the recursion), generating more sub-tasks when executed — giving the thief substantial work.

Theoretical Guarantees

Cilk's work-stealing scheduler provides a provable bound: for a computation with T₁ total work and T∞ critical path length (span), execution on P processors completes in expected time T₁/P + O(T∞). This is within a constant factor of optimal for any scheduler. The number of steal operations is O(P × T∞), meaning communication is proportional to the span, not the total work.

Implementations

• Cilk/OpenCilk: The academic progenitor — cilk_spawn and cilk_sync keywords extend C/C++ with fork-join parallelism. The compiler and runtime handle scheduling.
• Intel TBB (Threading Building Blocks): C++ template library with parallel_for, parallel_reduce, parallel_pipeline, and task_group. Work-stealing runtime underneath.
• Java ForkJoinPool: Java's standard work-stealing executor for recursive tasks. Used internally by parallel streams.
• Rust Rayon: Data parallelism library backed by a work-stealing thread pool. par_iter() parallelizes iterators automatically.

Task Parallelism with Work-Stealing is the dynamic, adaptive approach to parallel execution — letting the runtime discover and exploit parallelism that the programmer expresses structurally, without requiring the programmer to manually partition work across cores or predict load imbalance.