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).

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

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 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.

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.

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);
}

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 primitives or message passing rather than the fork-join structure.