Fork-Join Pattern — a fundamental parallel programming pattern where a task is recursively divided (forked) into sub-tasks that execute in parallel, then results are combined (joined) when complete.

Structure

            [Main Task]
           /     |     \
     [Fork]   [Fork]   [Fork]     ← Split into parallel sub-tasks
       |        |        |
    [Work]   [Work]   [Work]      ← Execute in parallel
       \       |       /
         [Join/Merge]              ← Combine results
           [Result]

Examples

• Parallel merge sort: Fork to sort halves, join to merge
• Parallel sum: Fork to sum sub-arrays, join to add partial sums
• Web crawler: Fork to crawl linked pages, join to aggregate results

Implementations

• Java ForkJoinPool: Built-in framework with work-stealing scheduler
• Intel TBB: tbb::parallel_invoke, tbb::task_group
• OpenMP: #pragma omp task + #pragma omp taskwait
• C++ std::async: auto f = std::async(task); f.get();

Work Stealing

• Each thread has its own task queue
• When a thread's queue is empty, it steals tasks from another thread's queue
• Provides automatic load balancing without programmer effort
• Used by most fork-join implementations

Granularity Control

• Too fine-grained: Overhead of forking/joining > computation
• Too coarse-grained: Poor load balance
• Solution: Set minimum task size (cutoff) — below cutoff, execute sequentially

Fork-join is the most natural way to parallelize divide-and-conquer algorithms — it maps directly to recursive problem decomposition.