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

**[Fork-join model](https://en.wikipedia.org/wiki/Fork%E2%80%93join_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.

## Example

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

```c
// 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;
}
```