You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
<li><ahref="#ImplementIfElseControlFlow">Implement If-Else Control Flow</a></li>
<li><ahref="#ImplementSwitchControlFlow">Implement Switch Control Flow</a></li>
<li><ahref="#ImplementDoWhileLoopControlFlow">Implement Do-While-Loop Control Flow</a></li>
<li><ahref="#ImplementWhileLoopControlFlow">Implement While-Loop Control Flow</a></li>
</ul>
</li>
<li><ahref="#CreateAMultiConditionTask">Create a Multi-condition Task</a></li>
</ul>
</nav>
<p>Parallel workloads often require making control-flow decisions across dependent tasks. Taskflow supports a very efficient interface of conditional tasking for users to implement general control flow such as dynamic flow, cycles and conditionals that are otherwise difficult to do with existing frameworks.</p><sectionid="CreateAConditionTask"><h2><ahref="#CreateAConditionTask">Create a Condition Task</a></h2><p>A condition task evaluates a set of instructions and returns an integer index of the next successor task to execute. The index is defined with respect to the order of its successor construction. The following example creates an if-else block using a single condition task.</p><preclass="m-code"><spanclass="w"></span><spanclass="mi">1</span><spanclass="o">:</span><spanclass="w"></span><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Taskflow</span><spanclass="w"></span><spanclass="n">taskflow</span><spanclass="p">;</span>
</div><p>Line 5 creates a condition task <code>cond</code> and line 11 creates two dependencies from <code>cond</code> to two other tasks, <code>yes</code> and <code>no</code>. With this order, when <code>cond</code> returns 0, the execution moves on to task <code>yes</code>. When <code>cond</code> returns 1, the execution moves on to task <code>no</code>.</p><asideclass="m-note m-warning"><h4>Attention</h4><p>It is your responsibility to ensure the return of a condition task goes to a correct successor task. If the return falls beyond the range of the successors, the executor will not schedule any tasks.</p></aside><p>Condition task can go cyclic to describe <em>iterative</em> control flow. The example below implements a simple yet commonly used feedback loop through a condition task (line 7-10) that returns a random binary value. If the return value from <code>cond</code> is <code>0</code>, it loops back to itself, or otherwise to <code>stop</code>.</p><preclass="m-code"><spanclass="w"></span><spanclass="mi">1</span><spanclass="o">:</span><spanclass="w"></span><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Taskflow</span><spanclass="w"></span><spanclass="n">taskflow</span><spanclass="p">;</span>
<spanclass="w"></span><spanclass="mi">6</span><spanclass="o">:</span><spanclass="w"></span><spanclass="c1">// creates a condition task that returns 0 or 1</span>
<spanclass="w"></span><spanclass="mi">8</span><spanclass="o">:</span><spanclass="w"></span><spanclass="n">std</span><spanclass="o">::</span><spanclass="n">cout</span><spanclass="w"></span><spanclass="o"><<</span><spanclass="w"></span><spanclass="s">"flipping a coin</span><spanclass="se">\n</span><spanclass="s">"</span><spanclass="p">;</span>
<spanclass="mi">14</span><spanclass="o">:</span><spanclass="w"></span><spanclass="n">cond</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">cond</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">stop</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// returns 0 to 'cond' or 1 to 'stop'</span>
</div><p>A taskflow of complex control flow often just takes a few lines of code to implement, and different control flow blocks may run in parallel. The code below creates another taskflow with three condition tasks.</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Taskflow</span><spanclass="w"></span><spanclass="n">taskflow</span><spanclass="p">;</span>
<spanclass="n">cond_1</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">B</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">E</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// return 0 to 'B' or 1 to 'E'</span>
<spanclass="n">cond_2</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">G</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">H</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// return 0 to 'G' or 1 to 'H'</span>
<spanclass="n">cond_3</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">cond_3</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">L</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// return 0 to 'cond_3' or 1 to 'L'</span>
<spanclass="n">taskflow</span><spanclass="p">.</span><spanclass="n">dump</span><spanclass="p">(</span><spanclass="n">std</span><spanclass="o">::</span><spanclass="n">cout</span><spanclass="p">);</span></pre><p>The above code creates three condition tasks: (1) a condition task <code>cond_1</code> that loops back to <code>B</code> on returning <code>0</code>, or proceeds to <code>E</code> on returning <code>1</code>, (2) a condition task <code>cond_2</code> that goes to <code>G</code> on returning <code>0</code>, or <code>H</code> on returning <code>1</code>, (3) a condition task <code>cond_3</code> that loops back to itself on returning <code>0</code>, or proceeds to <code>L</code> on returning <code>1</code></p><divclass="m-graph"><svgstyle="width: 81.000rem; height: 19.200rem;" viewBox="0.00 0.00 809.74 192.00">
</div><p>You can use condition tasks to create cycles as long as the graph does not introduce task race during execution. However, cycles are not allowed in non-condition tasks.</p><asideclass="m-note m-warning"><h4>Attention</h4><p>Conditional tasking lets you make in-task control-flow decisions to enable <em>end-to-end</em> parallelism, instead of resorting to client-side partition or synchronizing your task graph at the decision points of control flow.</p></aside></section><sectionid="TaskSchedulingPolicy"><h2><ahref="#TaskSchedulingPolicy">Understand our Task-level Scheduling</a></h2><p>In order to understand how an executor schedules condition tasks, we define two dependency types, <em>strong dependency</em> and <em>weak dependency</em>. A strong dependency is a preceding link from a non-condition task to another task. A weak dependency is a preceding link from a condition task to another task. The number of dependencies of a task is the sum of strong dependency and weak dependency. The table below lists the strong dependency and weak dependency numbers of each task in the previous example.</p><tableclass="m-table"><thead><tr><th>task</th><th>strong dependency</th><th>weak dependency</th><th>dependencies</th></tr></thead><tbody><tr><td>A</td><td>0</td><td>0</td><td>0</td></tr><tr><td>B</td><td>1</td><td>1</td><td>2</td></tr><tr><td>C</td><td>1</td><td>0</td><td>1</td></tr><tr><td>D</td><td>1</td><td>0</td><td>1</td></tr><tr><td>E</td><td>0</td><td>1</td><td>1</td></tr><tr><td>F</td><td>1</td><td>0</td><td>1</td></tr><tr><td>G</td><td>0</td><td>1</td><td>1</td></tr><tr><td>H</td><td>0</td><td>1</td><td>1</td></tr><tr><td>I</td><td>1</td><td>0</td><td>1</td></tr><tr><td>K</td><td>1</td><td>0</td><td>1</td></tr><tr><td>L</td><td>0</td><td>1</td><td>1</td></tr><tr><td>M</td><td>1</td><td>0</td><td>1</td></tr><tr><td>cond_1</td><td>1</td><td>0</td><td>1</td></tr><tr><td>cond_2</td><td>1</td><td>0</td><td>1</td></tr><tr><td>cond_3</td><td>1</td><td>1</td><td>2</td></tr></tbody></table><p>You can query the number of strong dependencies, the number of weak dependencies, and the number of dependencies of a task.</p><preclass="m-code"><spanclass="mi">1</span><spanclass="o">:</span><spanclass="w"></span><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Taskflow</span><spanclass="w"></span><spanclass="n">taskflow</span><spanclass="p">;</span>
<spanclass="mi">9</span><spanclass="o">:</span><spanclass="w"></span><spanclass="n">std</span><spanclass="o">::</span><spanclass="n">cout</span><spanclass="w"></span><spanclass="o"><<</span><spanclass="w"></span><spanclass="n">task</span><spanclass="p">.</span><spanclass="n">num_weak_dependencies</span><spanclass="p">()</span><spanclass="w"></span><spanclass="o"><<</span><spanclass="w"></span><spanclass="sc">'\n'</span><spanclass="p">;</span></pre><p>When you submit a task to an executor, the scheduler starts with tasks of <em>zero dependencies</em> (both zero strong and weak dependencies) and continues to execute successive tasks whenever their <em>strong dependencies</em> are met. However, the scheduler skips this rule when executing a condition task and jumps directly to its successors indexed by the return value.</p><divclass="m-graph"><svgstyle="width: 60.800rem; height: 34.600rem;" viewBox="0.00 0.00 607.80 346.00">
<texttext-anchor="middle" x="188.96" y="-88.5" font-family="Helvetica,sans-Serif" font-size="10.00">decrement strong dependencies of each successor of T by one</text>
<texttext-anchor="middle" x="188.96" y="-15.5" font-family="Helvetica,sans-Serif" font-size="10.00">enqueue successors of zero strong dependencies</text>
</div><p>Each task has an <em>atomic</em> join counter to keep track of strong dependencies that are met at runtime. When a task completes, the join counter is restored to the task's strong dependency number in the graph, such that the subsequent execution can reuse the counter again.</p><sectionid="TaskLevelSchedulingExample"><h3><ahref="#TaskLevelSchedulingExample">Example</a></h3><p>Let's take a look at an example to understand how task-level scheduling works. Suppose we have the following taskflow of one condition task <code>cond</code> that forms a loop to itself on returning <code>0</code> and moves on to <code>stop</code> on returning <code>1</code>:</p><divclass="m-graph"><svgstyle="width: 26.300rem; height: 7.300rem;" viewBox="0.00 0.00 262.60 73.00">
</div><p>The scheduler starts with <code>init</code> task because it has no dependencies (both strong and weak dependencies). Then, the scheduler moves on to the condition task <code>cond</code>. If <code>cond</code> returns <code>0</code>, the scheduler enqueues <code>cond</code> and runs it again. If <code>cond</code> returns <code>1</code>, the scheduler enqueues <code>stop</code> and then moves on.</p></section></section><sectionid="AvoidCommonPitfalls"><h2><ahref="#AvoidCommonPitfalls">Avoid Common Pitfalls</a></h2><p>Condition tasks are handy in creating dynamic and cyclic control flows, but they are also easy to make mistakes. It is your responsibility to ensure a taskflow is properly conditioned. Top things to avoid include <em>no source tasks</em> to start with and <em>task race</em>. The figure below shows common pitfalls and their remedies.</p><divclass="m-graph"><svgstyle="width: 91.000rem; height: 26.100rem;" viewBox="0.00 0.00 910.00 261.00">
</div><p>In the <code>error1</code> scenario, there is no source task for the scheduler to start with, and the simplest fix is to add a task <code>S</code> that has no dependencies. In the <code>error2</code> scenario, <code>D</code> might be scheduled twice by <code>E</code> through the strong dependency and <code>C</code> through the weak dependency (on returning <code>1</code>). To fix this problem, you can add an auxiliary task <code>D-aux</code> to break the mixed use of strong dependency and weak dependency. In the risky scenario, task <code>X</code> may be raced by <code>M</code> and <code>P</code> if <code>M</code> returns <code>0</code> and P returns <code>1</code>.</p><asideclass="m-note m-warning"><h4>Attention</h4><p>It is your responsibility to ensure a written taskflow graph is properly conditioned. We suggest that you <ahref="#TaskSchedulingPolicy" class="m-doc">Understand our Task-level Scheduling</a> and infer if task race exists in the execution of your graph.</p></aside></section><sectionid="ImplementControlFlowGraphs"><h2><ahref="#ImplementControlFlowGraphs">Implement Control-flow Graphs</a></h2><sectionid="ImplementIfElseControlFlow"><h3><ahref="#ImplementIfElseControlFlow">Implement If-Else Control Flow</a></h3><p>You can use conditional tasking to implement if-else control flow. The following example creates a nested if-else control flow diagram that executes three condition tasks to check the range of <code>i</code>.</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Taskflow</span><spanclass="w"></span><spanclass="n">taskflow</span><spanclass="p">;</span>
<spanclass="n">cond1</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">equl1</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">cond2</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// goes to cond2 if i>1</span>
<spanclass="n">cond2</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">equl2</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">cond3</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// goes to cond3 if i>2</span>
<spanclass="n">cond3</span><spanclass="p">.</span><spanclass="n">precede</span><spanclass="p">(</span><spanclass="n">equl3</span><spanclass="p">,</span><spanclass="w"></span><spanclass="n">grtr3</span><spanclass="p">);</span><spanclass="w"></span><spanclass="c1">// goes to grtr3 if i>3</span></pre><divclass="m-graph"><svgstyle="width: 81.100rem; height: 15.200rem;" viewBox="0.00 0.00 811.47 152.00">
</div></section><sectionid="ImplementSwitchControlFlow"><h3><ahref="#ImplementSwitchControlFlow">Implement Switch Control Flow</a></h3><p>You can use conditional tasking to implement <em>switch</em> control flow. The following example creates a switch control flow diagram that executes one of the three cases at random using four condition tasks.</p><preclass="m-code"><spanclass="n">tf</span><spanclass="o">::</span><spanclass="n">Taskflow</span><spanclass="w"></span><spanclass="n">taskflow</span><spanclass="p">;</span>
</div><p>Assuming <code>swcond</code> returns 1, the program outputs:</p><preclass="m-console"><spanclass="go">source</span>
<spanclass="go">switch</span>
<spanclass="go">case 2</span>
<spanclass="go">target</span></pre><p>Keep in mind, both switch and case tasks must be described as condition tasks. The following implementation is a common mistake in which case tasks are not described as condition tasks.</p><preclass="m-code"><spanclass="c1">// wrong implementation of switch control flow using only one condition task</span>
<spanclass="w"></span><spanclass="p">[](){</span><spanclass="w"></span><spanclass="n">std</span><spanclass="o">::</span><spanclass="n">cout</span><spanclass="w"></span><spanclass="o"><<</span><spanclass="w"></span><spanclass="s">"target</span><spanclass="se">\n</span><spanclass="s">"</span><spanclass="p">;</span><spanclass="w"></span><spanclass="p">}</span><spanclass="w"></span><spanclass="c1">// target has three strong dependencies</span>