Skip to content
Navigation Menu
{{ message }}
forked from taskflow/taskflow
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter4.html
More file actions
169 lines (167 loc) · 20.5 KB
/
Copy pathchapter4.html
File metadata and controls
169 lines (167 loc) · 20.5 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
<!-- HTML header for doxygen 1.8.13-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow Handbook</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<link rel="icon" type="image/x-icon" href="favicon.ico" />
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
$(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr style="height: 56px;">
<td id="projectalign" style="padding-left: 0.5em;">
<div id="projectname"><a href="https://github.com/taskflow/taskflow">Taskflow</a>
 <span id="projectnumber">2.7.0-master-branch</span>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
$(function() {
initMenu('',true,false,'search.php','Search');
$(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('chapter4.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<div class="header">
<div class="headertitle">
<div class="title">C4: Conditional Tasking </div> </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>Parallel workloads often require making control-flow decisions across dependent tasks. Taskflow supports an very efficient interface of conditional tasking for users to implement general control flow such as dynamic flows, cycles, and conditionals that are otherwise difficult to do with existing frameworks.</p>
<h1><a class="anchor" id="C4_CreateAConditionTask"></a>
Create a Condition Task</h1>
<p>A condition task evalutes a set of instructions and returns an integer index of the next immediate successor to execute. The index is defined with respect to the order of its successor construction.</p>
<div class="fragment"><div class="line"> 1: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"> 2: </div><div class="line"> 3: <a class="code" href="classtf_1_1Task.html">tf::Task</a> init = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"init"</span>);</div><div class="line"> 4: <a class="code" href="classtf_1_1Task.html">tf::Task</a> stop = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"stop"</span>);</div><div class="line"> 5:</div><div class="line"> 6: <span class="comment">// creates a condition task that returns 0 or 1</span></div><div class="line"> 7: <a class="code" href="classtf_1_1Task.html">tf::Task</a> cond = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){</div><div class="line"> 8: <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/io/basic_ostream.html">std::cout</a> << <span class="stringliteral">"flipping a coin\n"</span>;</div><div class="line"> 9: <span class="keywordflow">return</span> <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>() % 2;</div><div class="line">10: }).name(<span class="stringliteral">"cond"</span>);</div><div class="line">11:</div><div class="line">12: <span class="comment">// creates a feedback loop</span></div><div class="line">13: init.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(cond);</div><div class="line">14: cond.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(cond, stop); <span class="comment">// cond--0-->cond, cond--1-->stop</span></div><div class="line">15:</div><div class="line">16: executor.<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).wait();</div></div><!-- fragment --><div class="image">
<object type="image/svg+xml" data="conditional-tasking-1.svg" width="45%">conditional-tasking-1.svg</object>
</div>
<p>The example above 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 0, it loops back to itself, or otherwise to <code>stop</code>. Our conditional tasking interface is very neat and expressive. A complex flow control often just takes a few lines of code to implement. The code below creates another taskflow with three condition tasks.</p>
<div class="fragment"><div class="line"> 1: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"> 2:</div><div class="line"> 3: <a class="code" href="classtf_1_1Task.html">tf::Task</a> A = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"A"</span>);</div><div class="line"> 4: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"B"</span>);</div><div class="line"> 5: <a class="code" href="classtf_1_1Task.html">tf::Task</a> C = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"C"</span>);</div><div class="line"> 6: <a class="code" href="classtf_1_1Task.html">tf::Task</a> D = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"D"</span>);</div><div class="line"> 7: <a class="code" href="classtf_1_1Task.html">tf::Task</a> E = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"E"</span>);</div><div class="line"> 8: <a class="code" href="classtf_1_1Task.html">tf::Task</a> F = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"F"</span>);</div><div class="line"> 9: <a class="code" href="classtf_1_1Task.html">tf::Task</a> G = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"G"</span>);</div><div class="line">10: <a class="code" href="classtf_1_1Task.html">tf::Task</a> H = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"H"</span>);</div><div class="line">11: <a class="code" href="classtf_1_1Task.html">tf::Task</a> I = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"I"</span>);</div><div class="line">12: <a class="code" href="classtf_1_1Task.html">tf::Task</a> K = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"K"</span>);</div><div class="line">13: <a class="code" href="classtf_1_1Task.html">tf::Task</a> L = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"L"</span>);</div><div class="line">14: <a class="code" href="classtf_1_1Task.html">tf::Task</a> M = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){}).name(<span class="stringliteral">"M"</span>);</div><div class="line">15: <a class="code" href="classtf_1_1Task.html">tf::Task</a> cond_1 = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; }).name(<span class="stringliteral">"cond_1"</span>);</div><div class="line">16: <a class="code" href="classtf_1_1Task.html">tf::Task</a> cond_2 = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; }).name(<span class="stringliteral">"cond_2"</span>);</div><div class="line">17: <a class="code" href="classtf_1_1Task.html">tf::Task</a> cond_3 = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){ <span class="keywordflow">return</span> <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/numeric/random/rand.html">std::rand</a>()%2; }).name(<span class="stringliteral">"cond_3"</span>);</div><div class="line">18:</div><div class="line">19: A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B, F);</div><div class="line">20: B.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(C);</div><div class="line">21: C.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D);</div><div class="line">22: D.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(cond_1);</div><div class="line">23: E.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(K);</div><div class="line">24: F.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(cond_2);</div><div class="line">25: H.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(I);</div><div class="line">26: I.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(cond_3);</div><div class="line">27: L.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(M);</div><div class="line">28:</div><div class="line">29: cond_1.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B, E);</div><div class="line">30: cond_2.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(G, H);</div><div class="line">31: cond_3.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(cond_3, L);</div><div class="line">32:</div><div class="line">33: taskflow.<a class="code" href="classtf_1_1Taskflow.html#ac433018262e44b12c4cc9f0c4748d758">dump</a>(<a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/io/basic_ostream.html">std::cout</a>);</div></div><!-- fragment --><p>Debrief: </p><ul>
<li>Line 29 creates a condition task that loops back to B on return 0, and proceeds to E on return 1 </li>
<li>Line 30 creates a condition task that goes to G and H on return 0 and 1, respectively </li>
<li>Line 31 creates a condition task that loops back to itself on return 0, and proceeds to L on return 1</li>
</ul>
<div class="image">
<object type="image/svg+xml" data="conditional-tasking-2.svg" width="100%">conditional-tasking-2.svg</object>
</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>
<h1><a class="anchor" id="C4_StrongDependencyVSWeakDependency"></a>
Strong Dependency vs Weak Dependency</h1>
<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 dependents 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>
<div align="center"> <table class="doxtable">
<tr>
<th align="center">task </th><th align="center">strong dependency </th><th align="center">weak dependency </th><th>dependents </th></tr>
<tr>
<td align="center">A </td><td align="center">0 </td><td align="center">0 </td><td>0 </td></tr>
<tr>
<td align="center">B </td><td align="center">1 </td><td align="center">1 </td><td>2 </td></tr>
<tr>
<td align="center">C </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">D </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">E </td><td align="center">0 </td><td align="center">1 </td><td>1 </td></tr>
<tr>
<td align="center">F </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">G </td><td align="center">0 </td><td align="center">1 </td><td>1 </td></tr>
<tr>
<td align="center">H </td><td align="center">0 </td><td align="center">1 </td><td>1 </td></tr>
<tr>
<td align="center">I </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">K </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">L </td><td align="center">0 </td><td align="center">1 </td><td>1 </td></tr>
<tr>
<td align="center">M </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">cond_1 </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">cond_2 </td><td align="center">1 </td><td align="center">0 </td><td>1 </td></tr>
<tr>
<td align="center">cond_3 </td><td align="center">1 </td><td align="center">1 </td><td>2 </td></tr>
</table>
</div><p>You can query the number of strong dependents, the number of weak dependents, and the number of dependents of a task.</p>
<div class="fragment"><div class="line">1: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line">2: </div><div class="line">3: <a class="code" href="classtf_1_1Task.html">tf::Task</a> task = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a796e29175380f70246cf2a5639adc437">emplace</a>([](){});</div><div class="line">4: </div><div class="line">5: <span class="comment">// ... add more tasks and preceding links</span></div><div class="line">6:</div><div class="line">7: <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/io/basic_ostream.html">std::cout</a> << task.<a class="code" href="classtf_1_1Task.html#a974dc1d738b62b829ad261beeafbd67c">num_dependents</a>() << <span class="charliteral">'\n'</span>;</div><div class="line">8: <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/io/basic_ostream.html">std::cout</a> << task.<a class="code" href="classtf_1_1Task.html#ad49a92e8858c3c298bed0215e341b66b">num_strong_dependents</a>() << <span class="charliteral">'\n'</span>; </div><div class="line">9: <a class="codeRef" doxygen="/home/tsung-wei/Code/taskflow/doxygen/cppreference-doxygen-web.tag.xml:http://en.cppreference.com/w/" href="http://en.cppreference.com/w/cpp/io/basic_ostream.html">std::cout</a> << task.<a class="code" href="classtf_1_1Task.html#af3bf886291af7f39957d43d17083fe07">num_weak_dependents</a>() << <span class="charliteral">'\n'</span>;</div></div><!-- fragment --><p>When you submit a task to an executor, the scheduler starts with tasks of <em>zero dependents</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>
<div class="image">
<object type="image/svg+xml" data="conditional-tasking-rules.svg" width="100%">conditional-tasking-rules.svg</object>
</div>
<p>Each task has an <em>atomic</em> join counter to keep track of strong dependents 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>
<h1><a class="anchor" id="C4_CommonPitfalls"></a>
Common Pitfalls</h1>
<p>Condition tasks are handy in creasing 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>
<div class="image">
<object type="image/svg+xml" data="conditional-tasking-pitfalls.svg" width="100%">conditional-tasking-pitfalls.svg</object>
</div>
<p>In the error1 scenario, there is no source task for the scheduler to start with, and the simplest fix is to add a task S that has no dependents. In the error2 scenario, D might be scheduled twice by E through the strong dependency and C through the weak dependency (on return 1). To fix this problem, you can add an auxiliary task D-aux to break the mixed use of strong dependency and weak dependency. In the risky scenario, task X may not be raced if P and M is exclusively branching to X.</p>
<p>A good practice for avoiding mistakes of conditional tasking is to infer the execution flow of your graphs based on our scheduling rules. Make sure there is no task race. </p>
</div></div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="Cookbook.html">Cookbook</a></li>
<li class="footer">Generated by
<a href="http://www.doxygen.org/index.html">
<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.13 </li>
</ul>
</div>
</body>
</html>
You can’t perform that action at this time.