Fork-join model

Fork-join model structures parallel execution as phases: a single thread forks into multiple threads that run concurrently, then join back into one before proceeding. It underlies OpenMP's #pragma omp parallel, Cilk, and many task-parallel runtimes. The join point is an implicit barrier—no thread proceeds until all forked threads finish and their writes become visible.

The model composes naturally for divide-and-conquer algorithms but doesn't fit persistent pipelines or long-lived inter-thread communication.

This example demonstrates fork-join with parallel divide-and-conquer sorting.

// compile: gcc -fopenmp -O2 -o forkjoin forkjoin.c
// run: ./forkjoin
// description: fork-join parallelism for parallel merge sort
 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <omp.h>
 
void merge(int* arr, int left, int mid, int right) {
    int n1 = mid - left + 1, n2 = right - mid;
    int* L = malloc(n1 * sizeof(int));
    int* R = malloc(n2 * sizeof(int));
 
    memcpy(L, &arr[left], n1 * sizeof(int));
    memcpy(R, &arr[mid + 1], n2 * sizeof(int));
 
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        arr[k++] = L[i] < R[j] ? L[i++] : R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
 
    free(L);
    free(R);
}
 
void mergesort(int* arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        #pragma omp task
        mergesort(arr, left, mid);
        #pragma omp task
        mergesort(arr, mid + 1, right);
        #pragma omp taskwait
        merge(arr, left, mid, right);
    }
}
 
int main() {
    int n = 1024;
    int* arr = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) arr[i] = rand();
 
    #pragma omp parallel
    #pragma omp single
    mergesort(arr, 0, n - 1);
 
    printf("Sorted %d elements\n", n);
    free(arr);
    return 0;
}