Fork-join¶

Category: Parallelism · Status: stub · Lessons: chapter 07, Parallelism

One line: Split a task into subtasks, run them in parallel, wait for all of them and combine their results — recursively, until the pieces are small enough to do directly.

Also called: divide and conquer in parallel, ForkJoinPool.

How it connects¶

flowchart LR
  n_fork_join["Fork-join"]
  n_join["Join"]
  n_task_parallelism["Task parallelism"]
  n_work_stealing["Work stealing"]
  n_fork_join -->|is a| n_task_parallelism
  n_fork_join -->|uses| n_join
  n_fork_join -->|uses| n_work_stealing
  classDef center stroke-width:3px
  class n_fork_join center
  classDef outside stroke-dasharray: 4 3
  class n_join,n_task_parallelism,n_work_stealing outside

Is a kind of: Task parallelism
Is built on: Join, Work stealing
See also: Map-reduce, Parallel algorithms

In each language¶


Rust	Rayon's `join` ↗ runs two closures, potentially in parallel, and returns both results
Java	`ForkJoinPool` ↗ runs `ForkJoinTask`s, whose `fork` and `join` split and rejoin the work
C#	`Parallel.Invoke` ↗ runs actions in parallel and returns when all have completed

Where to read more¶

In the books: Pro TBB, Michael Voss, Rafael Asenjo, James Reinders — ch. 8, 'Mapping Parallel Patterns to TBB' → 'Fork-Join Pattern'
In the books: Programming Concurrency on the JVM, Venkat Subramaniam — ch. 4, 'Scalability and Thread Safety' → 'Java 7 Fork-Join API'
In the books: Programming Rust, Jim Blandy, Jason Orendorff, Leonora F. S. Tindall — ch. 19, 'Concurrency' → 'Fork-Join Parallelism'
In the books: Modern Java in Action, Raoul-Gabriel Urma, Mario Fusco, Alan Mycroft — ch. 7, 'Parallel data processing and performance' → 'The fork/join framework'
In the books: Functional and Concurrent Programming, Michel Charpentier — ch. 27, 'Minimizing Thread Blocking' → 'Fork/Join Pools'
In the books: Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein — ch. 26, 'Parallel Algorithms' → 'The basics of fork-join parallelism'
Reference: Wikipedia: Fork–join model ↗