Structured Parallel Programming

Chapter 8

Fork–Join

When you come to a fork in the road, take it.

(Yogi Berra, 1925-)

This chapter describes the fork–join pattern and gives several examples, including its use to implement other patterns such as map, reduce, recurrence, and scan. Applied recursively, fork–join can generate a high degree of potential parallelism. This can, in turn, be efficiently scheduled onto actual parallelism mechanisms by the Cilk Plus and Intel Threading Building Blocks (TBB) work-stealing schedulers.

Many serial divide-and-conquer algorithms lend themselves to parallelization via fork–join. However, the limits on speedup noted in Section 2.5 need to be taken into account. In particular, most of the work should be pushed as deep into the recursion as possible, ...