Ivan's wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
# Fork-join model
The **fork-join model** structures parallel execution as a sequence of phases: a single thread **forks** into multiple threads that run a parallel region concurrently, and those threads later **join** back into one before the program continues. It's the model underlying [[openmp]]'s `#pragma omp parallel`, and more generally underlies most task-parallel runtimes (Cilk, Java's `ForkJoinPool`, `std::async`).

```c
// single thread here
#pragma omp parallel        // fork: N threads spawn
{
    do_work(omp_get_thread_num());
}
// implicit join: back to single thread here
```

## Why join is a synchronization point

The join at the end of a parallel region is an implicit barrier: no thread proceeds past it until every thread in that fork has finished. This makes fork-join easy to reason about, code after the join can safely assume every parallel worker's writes are visible and complete, without any explicit lock or [[sync-monitor|condition variable]] needed. The cost is that the whole team is only as fast as its slowest member on that phase; a single thread finishing its share of the work late stalls every other thread already waiting at the join.

## Recursive fork-join

The model composes naturally: a forked thread can itself fork further sub-tasks, forming a tree rather than a flat set, which is the pattern behind divide-and-conquer parallel algorithms like parallel merge sort or a parallel tree traversal.

```c
result_t solve(problem_t p) {
    if (small_enough(p)) return solve_directly(p);
    // fork two subtasks, join before combining
    result_t left, right;
    #pragma omp task shared(left)
    left = solve(split_left(p));
    #pragma omp task shared(right)
    right = solve(split_right(p));
    #pragma omp taskwait          // join
    return combine(left, right);
}
```

## Where it falls short

Fork-join assumes a fairly regular structure, phases of parallel work separated by full synchronization points. Workloads with a persistent pipeline (producer-consumer chains, streaming data) or with irregular, long-lived communication between workers don't fit the model well, since forcing a full join between every exchange would serialize work that could otherwise overlap. Those cases are better served by explicit [[synchronization-primitve|synchronization primitives]] or message passing rather than the fork-join structure.