<divclass="textblock"><p>We study how to express <em>divide-and-conquer</em> parallelism using Taskflow, using parallel merge sort as a concrete example. Divide-and-conquer is one of the most important parallel programming patterns and appears across sorting, searching, tree traversal, numerical computation, and graph algorithms.</p>
<p>A divide-and-conquer algorithm solves a problem by recursively splitting it into two or more independent subproblems, solving each subproblem separately, and combining the results. The recursive structure is:</p>
<divclass="line"><spanclass="keywordflow">if</span>(P is small enough) <spanclass="keywordflow">return</span> solve_directly(P); <spanclass="comment">// base case</span></div>
</div><!-- fragment --><p>The key observation is that the two recursive calls, <code>solve(P1)</code> and <code>solve(P2)</code>, are <em>independent</em> of each other and can therefore run in parallel. The combine step must wait for both, but no other dependency exists.</p>
<p>Taskflow's <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> provides a natural way to express this: spawn one subproblem asynchronously, solve the other inline (tail optimisation), then call <code>corun</code> to wait cooperatively for the spawned task before combining. Note that <code>corun</code> does not block the calling worker but the program control flow. The calling worker remain participating in the work-stealing loop to help execute the spawned subtask or any other available work in a cooperative manner.</p>
<p>Merge sort is the canonical divide-and-conquer algorithm:</p>
<oltype="1">
<li><b>Divide:</b> split the array at the midpoint</li>
<li><b>Conquer:</b> recursively sort the left and right halves in parallel</li>
<li><b>Combine:</b> merge the two sorted halves</li>
</ol>
<divclass="dotgraph">
<iframescrolling="no" frameborder="0" src="dot_parallel_sort.svg" width="688" height="500"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<divclass="line"><spanclass="keywordflow">if</span>(right - left <= 1) <spanclass="keywordflow">return</span>;</div>
<divclass="line"><spanclass="keywordtype">int</span> mid = left + (right - left) / 2;</div>
<divclass="line"> merge_sort(data, left, mid); <spanclass="comment">// left half</span></div>
<divclass="line"> merge_sort(data, mid, right); <spanclass="comment">// right half</span></div>
<divclass="line"> std::inplace_merge(</div>
<divclass="line"> data.begin() + left,</div>
<divclass="line"> data.begin() + mid,</div>
<divclass="line"> data.begin() + right</div>
<divclass="line"> );</div>
<divclass="line">}</div>
</div><!-- fragment --><h1><aclass="anchor" id="DivideAndConquerParallelMergeSort"></a>
Parallel Merge Sort with TaskGroup</h1>
<p>We parallelise the two recursive calls using <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a>. A task group is created from the executor and provides the same <code>silent_async</code> and <code>corun</code> interface as <aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a>, but can be used from any execution context of a worker. There is no need for the caller to already be a runtime task.</p>
<p>We also apply a <em>cutoff:</em> when the subrange is smaller than a threshold, we fall back to <code>std::sort</code> rather than spawning more tasks. Without a cutoff, the recursion would create far more tasks than there are cores, and the scheduling overhead would dominate the actual computation:</p>
<divclass="ttc" id="aclasstf_1_1Executor_html"><divclass="ttname"><ahref="classtf_1_1Executor.html">tf::Executor</a></div><divclass="ttdoc">class to create an executor</div><divclass="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_a8858a119b9ad697748293c4bb1408853"><divclass="ttname"><ahref="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">tf::Executor::task_group</a></div><divclass="ttdeci">TaskGroup task_group()</div><divclass="ttdoc">creates a task group that executes a collection of asynchronous tasks</div><divclass="ttdef"><b>Definition</b> task_group.hpp:863</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_af960048056f7c6b5bc71f4f526f05df7"><divclass="ttname"><ahref="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">tf::Executor::async</a></div><divclass="ttdeci">auto async(P &&params, F &&func)</div><divclass="ttdoc">creates a parameterized asynchronous task to run the given function</div></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html">tf::TaskGroup</a></div><divclass="ttdoc">class to create a task group from a task</div><divclass="ttdef"><b>Definition</b> task_group.hpp:61</div></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html_acf90acfcaf9468adc56bf647208a9e78"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html#acf90acfcaf9468adc56bf647208a9e78">tf::TaskGroup::silent_async</a></div><divclass="ttdeci">void silent_async(F &&f)</div><divclass="ttdoc">runs the given function asynchronously without returning any future object</div><divclass="ttdef"><b>Definition</b> task_group.hpp:752</div></div>
</div><!-- fragment --><p>Several design choices in this example apply broadly to parallel divide-and-conquer algorithms:</p>
<p>Recursively spawning tasks down to single elements would create O(N) tasks with trivial work each. The cutoff switches to <code>std::sort</code> for small subranges, keeping the task count proportional to the available parallelism rather than the input size. A good rule of thumb is to set the cutoff so that the sequential base case takes at least a few microseconds — typically a few thousand elements for integer sorting.</p>
<p>Only the left half is spawned as an async task; the right half is sorted inline in the current execution context. This halves the number of tasks at every level of the recursion tree and eliminates one level of task-creation overhead per recursive call.</p>
<p>Calling <aclass="el" href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc" title="corun all tasks spawned by this task group with other workers">tf::TaskGroup::corun</a> does not block the calling thread from making progress but only the program control flow (i.e., the program execution will not proceed until <code>corun</code> returns). Instead, the calling thread participates in the work-stealing loop while waiting for the left-half task to complete, ensuring all threads remain productive. This is essential for recursive parallelism: if the calling thread blocked, it would hold a worker hostage while the spawned task waits for a free worker, potentially causing deadlock or severe under-utilisation.</p>
<p>A <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> can only be created by a worker of an executor due to the support for cooperative execution.</p>
<p>The same <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> pattern applies to any divide-and-conquer algorithm. Replace the merge sort specifics with the divide/conquer/combine steps of your algorithm:</p>
<divclass="line"> solve(P1, cutoff); <spanclass="comment">// solve left half asynchronously</span></div>
<divclass="line"> });</div>
<divclass="line"></div>
<divclass="line"> solve(P2, cutoff); <spanclass="comment">// solve right half inline</span></div>
<divclass="line"></div>
<divclass="line"> tg.<aclass="code hl_function" href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">corun</a>(); <spanclass="comment">// wait cooperatively for left half</span></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html_a1f481dc466e3107a08346d1a124677bc"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">tf::TaskGroup::corun</a></div><divclass="ttdeci">void corun()</div><divclass="ttdoc">corun all tasks spawned by this task group with other workers</div><divclass="ttdef"><b>Definition</b> task_group.hpp:721</div></div>
</div><!-- fragment --><p>Examples of divide-and-conquer algorithms that fit this template directly:</p>
<ul>
<li><b>Quicksort:</b> partition around a pivot, recursively sort each partition</li>
<li><b>Binary</b><b>search:</b> recurse into the half that contains the target</li>
<p><aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">Runtime</a> comparison for sorting 1M random integers on a 12-core machine:</p>
</div><p>The speed-up is sub-linear because <code>std::inplace_merge</code> at the top levels of the recursion tree is sequential and dominates as the recursive parallelism collapses. Using a parallel merge step or switching to parallel quicksort (where the combine step is trivial) would push the speed-up closer to the core count. </p>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<divid="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<liclass="navelem"><aclass="el" href="Examples.html">Learning from Examples</a></li>
<liclass="footer">
Maintained by <ahref="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <ahref="https://www.doxygen.org/index.html"><imgclass="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1