Fork–join model

<h2 id="examples">Examples</h2>
The simple parallel <a href="/facts/Merge_sort/A5jLYfzS">merge sort</a> of <a href="/facts/Introduction_to_Algorithms/o9n7KDsg">CLRS</a> is a fork–join algorithm.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

mergesort(A, lo, hi):
 if lo < hi: // at least one element of input
 mid = ⌊lo + (hi - lo) / 2⌋
 fork mergesort(A, lo, mid) // process (potentially) in parallel with main task
 mergesort(A, mid, hi) // main task handles second recursion
 join
 merge(A, lo, mid, hi)

The first recursive call is "forked off", meaning that its execution may run in parallel (in a separate thread) with the following part of the function, up to the join that causes all threads to synchronize. While the join may look like a <a href="/facts/Barrier_(computer_science)/DUdsRXEP">barrier</a>, it is different because the threads will continue to work after a barrier, while after a join only one thread continues.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>: 88 
The second recursive call is not a fork in the pseudocode above; this is intentional, as forking tasks may come at an expense. If both recursive calls were set up as subtasks, the main task would not have any additional work to perform before being blocked at the join.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="implementations">Implementations</h2>
Implementations of the fork–join model will typically fork tasks, fibers or lightweight threads, not operating-system-level "heavyweight" <a href="/facts/Thread_(computing)/hh8WHyPd">threads</a> or processes, and use a <a href="/facts/Thread_pool/lFJlm6hL">thread pool</a> to execute these tasks: the fork primitive allows the programmer to specify potential parallelism, which the implementation then maps onto actual parallel execution.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> The reason for this design is that creating new threads tends to result in too much overhead.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
The lightweight threads used in fork–join programming will typically have their own scheduler (typically a <a href="/facts/Work_stealing/Kn5xTRpo">work stealing</a> one) that maps them onto the underlying thread pool. This scheduler can be much simpler than a fully featured, <a href="/facts/Preemption_(computing)/wjgIbWel">preemptive</a> operating system scheduler: general-purpose thread <a href="/facts/Scheduling_(computing)/XptmcM1a">schedulers</a> must deal with blocking for <a href="/facts/Lock_(computer_science)/e3a9gnJT">locks</a>, but in the fork–join paradigm, threads only block at the join point.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
Fork–join is the main model of parallel execution in the <a href="/facts/OpenMP/69IpI80o">OpenMP</a> framework, although OpenMP implementations may or may not support nesting of parallel sections.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> It is also supported by the <a href="/facts/Java_concurrency/lX01oEzk">Java concurrency</a> framework,<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> the <a href="/facts/Task_Parallel_Library/bSobG0V4">Task Parallel Library</a> for .NET,<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> and Intel's <a href="/facts/Threading_Building_Blocks/6DChhaHg">Threading Building Blocks</a> (TBB).<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> The <a href="/facts/Cilk/nIftzSWW">Cilk</a> programming language has language-level support for fork and join, in the form of the spawn and sync keywords,<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> or cilk_spawn and cilk_sync in <a href="/facts/Cilk_Plus/nIftzSWW">Cilk Plus</a>.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<h2 id="see-also">See also</h2>
<ul>
<li>Computer programming portal</li></ul>
<ul><li><a href="/facts/MapReduce/KbfxJ5vV">MapReduce</a></li>
<li><a href="/facts/Task_parallelism/z2znIYK1">Task parallelism</a></li>
<li><a href="/facts/Work_stealing/Kn5xTRpo">Work stealing</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3872.pdf">A Primer on Scheduling Fork–Join Parallelism with Work Stealing</a></li>
<li><a href="https://www.blogcyberini.com/2018/07/merge-sort-paralelo-java-fork-join.html">Fork-Join Merge Sort (Java)</a> (in Portuguese)</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Melvin E. Conway (1963). A multiprocessor system design. Fall Join Computer Conference. pp. 139–146. doi:10.1145/1463822.1463838. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Nyman, Linus; Laakso, Mikael (2016). "Notes on the History of Fork and Join". IEEE Annals of the History of Computing. 38 (3). IEEE Computer Society: 84–87. doi:10.1109/MAHC.2016.34. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Doug Lea (2000). A Java fork/join framework (PDF). ACM Conference on Java. <a href="/wiki/Doug_Lea" target="_blank">/wiki/Doug_Lea</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. p. 797. ISBN 0-262-03384-4. <a href="0-262-03384-4" target="_blank">0-262-03384-4</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Doug Lea (2000). A Java fork/join framework (PDF). ACM Conference on Java. <a href="/wiki/Doug_Lea" target="_blank">/wiki/Doug_Lea</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Doug Lea (2000). A Java fork/join framework (PDF). ACM Conference on Java. <a href="/wiki/Doug_Lea" target="_blank">/wiki/Doug_Lea</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Blaise Barney (12 June 2013). "OpenMP". Lawrence Livermore National Laboratory. Retrieved 5 April 2014. <a href="https://computing.llnl.gov/tutorials/openMP/" target="_blank">https://computing.llnl.gov/tutorials/openMP/</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">"Fork/Join". The Java Tutorials. Retrieved 5 April 2014. <a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html" target="_blank">http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Daan Leijen; Wolfram Schulte; Sebastian Burckhardt (2009). The design of a Task Parallel Library. OOPSLA. <a href="/wiki/OOPSLA" target="_blank">/wiki/OOPSLA</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Doug Lea (2000). A Java fork/join framework (PDF). ACM Conference on Java. <a href="/wiki/Doug_Lea" target="_blank">/wiki/Doug_Lea</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Michael McCool; James Reinders; Arch Robison (2013). Structured Parallel Programming: Patterns for Efficient Computation. Elsevier. <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
</ol>

Fork–join model open-in-new

Fork–join model