Fork Join Pattern

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.

Fork Join Pattern

Take fork join pattern further