<li><ahref="#CreateADynamicTaskGraph">Create a Dynamic Task Graph</a></li>
<li><ahref="#SpecifyARagneOfDependentAsyncTasks">Specify a Range of Dependent Async Tasks</a></li>
<li><ahref="#UnderstandTheLifeTimeOfADependentAsyncTask">Understand the Lifetime of a Dependent-async Task</a></li>
<li><ahref="#CreateADynamicTaskGraphByMultipleThreads">Create a Dynamic Task Graph by Multiple Threads</a></li>
<li><ahref="#QueryTheComppletionStatusOfDependentAsyncTasks">Query the Completion Status of Dependent Async Tasks</a></li>
</ul>
</nav>
<p>This chapters discusses how to create a task graph dynamically using dependent asynchronous (dependent-async) tasks, which is extremely beneficial for workloads that want to (1) explore task graph parallelism out of dynamic control flow or (2) overlap task graph creation time with individual task execution time. We recommend that you first read <ahref="AsyncTasking.html" class="m-doc">Asynchronous Tasking</a> before digesting this chapter.</p><sectionid="CreateADynamicTaskGraph"><h2><ahref="#CreateADynamicTaskGraph">Create a Dynamic Task Graph</a></h2><p>When the construct-and-run model of a task graph is not possible in your application, you can use <ahref="classtf_1_1Executor.html#aee02b63d3a91ad5ca5a1c0e71f3e128f" class="m-doc">tf::<wbr/>Executor::<wbr/>dependent_async</a> and <ahref="classtf_1_1Executor.html#a0e2d792f28136b8227b413d0c27d5c7f" class="m-doc">tf::<wbr/>Executor::<wbr/>silent_dependent_async</a> to create a task graph on the fly. This style of execution is commonly referred to as dynamic task graph parallelism and provides greater flexibility in expressing parallelism that adapts to runtime conditions. The example below dynamically creates a task graph of four dependent-async tasks, <code>A</code>, <code>B</code>, <code>C</code>, and <code>D</code>, where <code>A</code> runs before <code>B</code> and <code>C</code> and <code>D</code> runs after <code>B</code> and <code>C:</code></p><divclass="m-graph"><svgstyle="width: 24.200rem; height: 9.800rem;" viewBox="0.00 0.00 242.00 98.00">
<spanclass="n">fuD</span><spanclass="p">.</span><spanclass="n">get</span><spanclass="p">();</span><spanclass="w"></span><spanclass="c1">// wait for D to finish, which in turn means A, B, C have finished</span></pre><p>Both <ahref="classtf_1_1Executor.html#aee02b63d3a91ad5ca5a1c0e71f3e128f" class="m-doc">tf::<wbr/>Executor::<wbr/>dependent_async</a> and <ahref="classtf_1_1Executor.html#a0e2d792f28136b8227b413d0c27d5c7f" class="m-doc">tf::<wbr/>Executor::<wbr/>silent_dependent_async</a> create a dependent-async task of type <ahref="classtf_1_1AsyncTask.html" class="m-doc">tf::<wbr/>AsyncTask</a> to run the given function asynchronously. Additionally, <ahref="classtf_1_1Executor.html#aee02b63d3a91ad5ca5a1c0e71f3e128f" class="m-doc">tf::<wbr/>Executor::<wbr/>dependent_async</a> returns a <ahref="https://en.cppreference.com/w/cpp/thread/future">std::<wbr/>future</a> that eventually holds the result of the execution. When returning from both calls, the executor has scheduled a worker to run the task whenever its dependencies are met. That is, task execution happens <em>simultaneously</em> with the creation of the task graph, which is different from constructing a Taskflow and running it from an executor, illustrated in the figure below:</p><imgclass="m-image" src="dependent_async_execution_diagram.png" alt="Image" /><p>Since this model only allows relating a dependency from the current task to a previously created task, you need a correct topological order of graph expression. In our example, there are only two possible topological orderings, either <code>ABCD</code> or <code>ACBD</code>. The code below shows another feasible order of expressing this dynamic task graph parallelism:</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Executor</span><spanclass="w"></span><spanclass="n">executor</span><spanclass="p">;</span>
<spanclass="n">fuD</span><spanclass="p">.</span><spanclass="n">get</span><spanclass="p">();</span><spanclass="w"></span><spanclass="c1">// wait for D to finish, which in turn means A, B, C have finished</span></pre><p>In addition to using <ahref="https://en.cppreference.com/w/cpp/thread/future">std::<wbr/>future</a> to synchronize the execution at a particular task point, you can use <ahref="classtf_1_1Executor.html#ab9aa252f70e9a40020a1e5a89d485b85" class="m-doc">tf::<wbr/>Executor::<wbr/>wait_for_all</a> to wait for all scheduled tasks to finish:</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Executor</span><spanclass="w"></span><spanclass="n">executor</span><spanclass="p">;</span>
<spanclass="n">executor</span><spanclass="p">.</span><spanclass="n">wait_for_all</span><spanclass="p">();</span></pre></section><sectionid="SpecifyARagneOfDependentAsyncTasks"><h2><ahref="#SpecifyARagneOfDependentAsyncTasks">Specify a Range of Dependent Async Tasks</a></h2><p>Both <ahref="classtf_1_1Executor.html#aee02b63d3a91ad5ca5a1c0e71f3e128f" class="m-doc">tf::<wbr/>Executor::<wbr/>dependent_async</a> and <ahref="classtf_1_1Executor.html#a0e2d792f28136b8227b413d0c27d5c7f" class="m-doc">tf::<wbr/>Executor::<wbr/>silent_dependent_async</a> accept an arbitrary number of tasks in the dependency list. If the number of task dependencies (i.e., predecessors) is unknown at programming time, such as those relying on runtime variables, you can use the following two overloads to specify predecessor tasks in an iterable range <code>[first, last)</code>:</p><ul><li><ahref="classtf_1_1Executor.html#a01e51e564f5def845506bcf6b4bb1664" class="m-doc">tf::<wbr/>Executor::<wbr/>dependent_async(F&& func, I first, I last)</a></li><li><ahref="classtf_1_1Executor.html#aa9b08e47e68ae1e568f18aa7104cb9b1" class="m-doc">tf::<wbr/>Executor::<wbr/>silent_dependent_async(F&& func, I first, I last)</a></li></ul><p>The range must be an input iterator whose deferenced type is convertible to <ahref="classtf_1_1AsyncTask.html" class="m-doc">tf::<wbr/>AsyncTask</a>. The following example creates a dependent-async task that depends on <code>N</code> previously created dependent-async tasks stored in a vector, where <code>N</code> is a runtime variable:</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Executor</span><spanclass="w"></span><spanclass="n">executor</span><spanclass="p">;</span>
<spanclass="k">for</span><spanclass="p">(</span><spanclass="kt">size_t</span><spanclass="w"></span><spanclass="n">i</span><spanclass="o">=</span><spanclass="mi">0</span><spanclass="p">;</span><spanclass="w"></span><spanclass="n">i</span><spanclass="o"><</span><spanclass="n">N</span><spanclass="p">;</span><spanclass="w"></span><spanclass="n">i</span><spanclass="o">++</span><spanclass="p">)</span><spanclass="w"></span><spanclass="p">{</span><spanclass="w"></span><spanclass="c1">// N is a runtime variable</span>
<spanclass="c1">// wait for the above N+1 dependent-async tasks to finish</span>
<spanclass="n">executor</span><spanclass="p">.</span><spanclass="n">wait_for_all</span><spanclass="p">();</span></pre></section><sectionid="UnderstandTheLifeTimeOfADependentAsyncTask"><h2><ahref="#UnderstandTheLifeTimeOfADependentAsyncTask">Understand the Lifetime of a Dependent-async Task</a></h2><p><ahref="classtf_1_1AsyncTask.html" class="m-doc">tf::<wbr/>AsyncTask</a> is a lightweight handle that retains <em>shared</em> ownership of a dependent-async task created by an executor. This shared ownership ensures that the async task remains alive when adding it to the dependency list of another async task, thus avoiding the classical <ahref="https://en.wikipedia.org/wiki/ABA_problem">ABA problem</a>.</p><preclass="m-code"><spanclass="c1">// main thread retains shared ownership of async task A</span>
<spanclass="n">assert</span><spanclass="p">(</span><spanclass="n">A</span><spanclass="p">.</span><spanclass="n">use_count</span><spanclass="p">()</span><spanclass="w"></span><spanclass="o">>=</span><spanclass="w"></span><spanclass="mi">1</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// main thread holds a shared ownership to A</span>
<spanclass="c1">// task A remains alive (i.e., at least one ref count by the main thread) </span>
<spanclass="c1">// when being added to the dependency list of async task B</span>
<spanclass="n">assert</span><spanclass="p">(</span><spanclass="n">B</span><spanclass="p">.</span><spanclass="n">use_count</span><spanclass="p">()</span><spanclass="w"></span><spanclass="o">>=</span><spanclass="w"></span><spanclass="mi">1</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// main thread holds a shared ownership to B</span></pre><p>Currently, <ahref="classtf_1_1AsyncTask.html" class="m-doc">tf::<wbr/>AsyncTask</a> is implemented based on C++ smart pointer (<ahref="http://en.cppreference.com/w/cpp/memory/shared_ptr.html" class="m-doc-external">std::<wbr/>shared_ptr</a>) and is considered cheap to copy or move as long as only a handful of objects own it. When a worker completes a dependent-async task, it will remove the task from the executor, decrementing the number of shared owners by one. If that counter reaches zero, the task is destroyed.</p></section><sectionid="CreateADynamicTaskGraphByMultipleThreads"><h2><ahref="#CreateADynamicTaskGraphByMultipleThreads">Create a Dynamic Task Graph by Multiple Threads</a></h2><p>You can use multiple threads to create a dynamic task graph as long as the order of simultaneously creating tasks is topologically correct. The example below uses creates a dynamic task graph using three threads (including the main thread), where task <code>A</code> runs before task <code>B</code> and task <code>C:</code></p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Executor</span><spanclass="w"></span><spanclass="n">executor</span><spanclass="p">;</span>
<spanclass="c1">// main thread creates a dependent-async task A</span>
<spanclass="n">t2</span><spanclass="p">.</span><spanclass="n">join</span><spanclass="p">();</span></pre><p>Regardless of whether <code>t1</code> runs before or after <code>t2</code>, the resulting topological order remains valid with respect to the graph definition. In this example, either <code>ABC</code> or <code>ACB</code> is a correct ordering.</p></section><sectionid="QueryTheComppletionStatusOfDependentAsyncTasks"><h2><ahref="#QueryTheComppletionStatusOfDependentAsyncTasks">Query the Completion Status of Dependent Async Tasks</a></h2><p>When you create a dependent-async task, you can query its completion status using <ahref="classtf_1_1AsyncTask.html#aefeefa30d7cafdfbb7dc8def542e8e51" class="m-doc">tf::<wbr/>AsyncTask::<wbr/>is_done</a>, which returns <code>true</code> if the task has completed its execution, or <code>false</code> otherwise. A task is considered completed once a worker has finished executing its associated callable.</p><preclass="m-code"><spanclass="c1">// create a dependent-async task that returns 100</span>
<spanclass="n">assert</span><spanclass="p">(</span><spanclass="n">fu</span><spanclass="p">.</span><spanclass="n">get</span><spanclass="p">()</span><spanclass="w"></span><spanclass="o">==</span><spanclass="w"></span><spanclass="mi">100</span><spanclass="p">);</span></pre><p><ahref="classtf_1_1AsyncTask.html#aefeefa30d7cafdfbb7dc8def542e8e51" class="m-doc">tf::<wbr/>AsyncTask::<wbr/>is_done</a> is useful when you need to wait on the result of a dependent-async task before moving onto the next program instruction. Often, <ahref="classtf_1_1AsyncTask.html" class="m-doc">tf::<wbr/>AsyncTask</a> is used together with <ahref="classtf_1_1Executor.html#a0fc6eb19f168dc4a9cd0a7c6187c1d2d" class="m-doc">tf::<wbr/>Executor::<wbr/>corun_until</a> to keep a worker awake in its work-stealing loop to avoid deadlock (see <ahref="ExecuteTaskflow.html#ExecuteATaskflowFromAnInternalWorker" class="m-doc">Execute a Taskflow from an Internal Worker Cooperatively</a> for more details). For instance, the code below implements the famous Fibonacci sequence using recursive dependent-async tasking:</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Executor</span><spanclass="w"></span><spanclass="n">executor</span><spanclass="p">;</span>
<spanclass="n">assert</span><spanclass="p">(</span><spanclass="n">fib11</span><spanclass="w"></span><spanclass="o">==</span><spanclass="w"></span><spanclass="mi">89</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// the 11-th Fibonacci number is 89</span></pre></section>
</div>
</div>
</div>
</article></main>
<divclass="m-doc-search" id="search">
<ahref="#!" onclick="return hideSearch()"></a>
<divclass="m-container">
<divclass="m-row">
<divclass="m-col-m-8 m-push-m-2">
<divclass="m-doc-search-header m-text m-small">
<div><spanclass="m-label m-default">Tab</span> / <spanclass="m-label m-default">T</span> to search, <spanclass="m-label m-default">Esc</span> to close</div>