fork join pattern
**Fork-Join Pattern** — a fundamental parallel programming pattern where a task is recursively divided (forked) into sub-tasks that execute in parallel, then results are combined (joined) when complete.
**Structure**
```
[Main Task]
/ | \
[Fork] [Fork] [Fork] ← Split into parallel sub-tasks
| | |
[Work] [Work] [Work] ← Execute in parallel
\ | /
[Join/Merge] ← Combine results
[Result]
```
**Examples**
- Parallel merge sort: Fork to sort halves, join to merge
- Parallel sum: Fork to sum sub-arrays, join to add partial sums
- Web crawler: Fork to crawl linked pages, join to aggregate results
**Implementations**
- **Java ForkJoinPool**: Built-in framework with work-stealing scheduler
- **Intel TBB**: `tbb::parallel_invoke`, `tbb::task_group`
- **OpenMP**: `#pragma omp task` + `#pragma omp taskwait`
- **C++ std::async**: `auto f = std::async(task); f.get();`
**Work Stealing**
- Each thread has its own task queue
- When a thread's queue is empty, it steals tasks from another thread's queue
- Provides automatic load balancing without programmer effort
- Used by most fork-join implementations
**Granularity Control**
- Too fine-grained: Overhead of forking/joining > computation
- Too coarse-grained: Poor load balance
- Solution: Set minimum task size (cutoff) — below cutoff, execute sequentially
**Fork-join** is the most natural way to parallelize divide-and-conquer algorithms — it maps directly to recursive problem decomposition.