task parallelism model
**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.