forked from taskflow/taskflow
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter5.html
More file actions
145 lines (143 loc) · 20.4 KB
/
chapter5.html
File metadata and controls
145 lines (143 loc) · 20.4 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
<!-- 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>Cpp-Taskflow</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>
<script type="text/javascript">
$(document).ready(function() { init_search(); });
</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/cpp-taskflow/cpp-taskflow">Cpp-Taskflow</a>
 <span id="projectnumber">2.2.0</span>
</div>
</td>
<td> <div id="MSearchBox" class="MSearchBoxInactive">
<span class="left">
<img id="MSearchSelect" src="search/mag_sel.png"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
alt=""/>
<input type="text" id="MSearchField" value="Search" accesskey="S"
onfocus="searchBox.OnSearchFieldFocus(true)"
onblur="searchBox.OnSearchFieldFocus(false)"
onkeyup="searchBox.OnSearchFieldChange(event)"/>
</span><span class="right">
<a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
</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>
</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('chapter5.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">C5: Spawn Task Dependency Graphs at Runtime </div> </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>It is very common for a parallel program to spawn task dependency graphs at runtime. In Cpp-Taskflow, we call this <em>dynamic tasking</em>.</p>
<h1><a class="anchor" id="Subflow"></a>
Subflow</h1>
<p>Dynamic tasks are those created during the execution of a graph. These tasks are spawned from a parent task and are grouped together to a <em>subflow</em> dependency graph. Cpp-Taskflow has an unified interface for static and dynamic tasking. To create a subflow for dynamic tasking, emplace a callable that takes one argument of type <a class="el" href="classtf_1_1Subflow.html" title="The building blocks of dynamic tasking. ">tf::Subflow</a>. A <a class="el" href="classtf_1_1Subflow.html" title="The building blocks of dynamic tasking. ">tf::Subflow</a> object will be created during the runtime and passed to the task. All graph building methods you find in taskflow are applicable for a subflow.</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#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"A"</span>); <span class="comment">// static task A</span></div><div class="line"> 4: <a class="code" href="classtf_1_1Task.html">tf::Task</a> C = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"C"</span>); <span class="comment">// static task C</span></div><div class="line"> 5: <a class="code" href="classtf_1_1Task.html">tf::Task</a> D = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"D"</span>); <span class="comment">// static task D</span></div><div class="line"> 6:</div><div class="line"> 7: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] (<a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a>& subflow) { </div><div class="line"> 8: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B1 = subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"B1"</span>); <span class="comment">// dynamic task B1</span></div><div class="line"> 9: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B2 = subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"B2"</span>); <span class="comment">// dynamic task B2</span></div><div class="line">10: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B3 = subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"B3"</span>); <span class="comment">// dynamic task B3</span></div><div class="line">11: B1.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B3); <span class="comment">// B1 runs bofore B3</span></div><div class="line">12: B2.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B3); <span class="comment">// B2 runs before B3</span></div><div class="line">13: }).name(<span class="stringliteral">"B"</span>);</div><div class="line">14:</div><div class="line">15: A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B); <span class="comment">// B runs after A</span></div><div class="line">16: A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(C); <span class="comment">// C runs after A</span></div><div class="line">17: B.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D); <span class="comment">// D runs after B</span></div><div class="line">18: C.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D); <span class="comment">// D runs after C</span></div><div class="line">19:</div><div class="line">20: <a class="code" href="classtf_1_1Executor.html">tf::Executor</a>().<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).get(); <span class="comment">// execute the graph to spawn the subflow</span></div><div class="line">21: taskflow.<a class="code" href="classtf_1_1Taskflow.html#ac433018262e44b12c4cc9f0c4748d758">dump</a>(<a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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="comment">// dump the taskflow to DOT format</span></div></div><!-- fragment --><div class="image">
<img src="subflow_join.png" alt="subflow_join.png" width="30%"/>
</div>
<p>Debrief: </p><ul>
<li>Line 1 creates a taskflow object </li>
<li>Line 3-5 creates three tasks, A, C, and D </li>
<li>Line 7-13 creates a task B that spawns a task dependency graph of three tasks B1, B2, and B3 </li>
<li>Line 15-18 add dependencies among A, B, C, and D </li>
<li>Line 20 dispatches the graph and waits until it finishes </li>
<li>Line 21 dumps the entire task dependency graph</li>
</ul>
<p>Line 7-13 is the main coding block to enable dynamic tasking. Cpp-Taskflow uses a <a href="https://en.cppreference.com/w/cpp/utility/variant">std::variant</a> date type to unify the interface of static tasking and dynamic tasking. The runtime will create a <a class="el" href="classtf_1_1Subflow.html" title="The building blocks of dynamic tasking. ">tf::Subflow</a> passing it to task B, and spawn a dependency graph as described by the associated callable. This new subflow graph will be added to the topology of its parent task B. Due to the property of dynamic tasking, we cannot dump its structure before execution. We will need to run the graph first and call the method <a class="el" href="classtf_1_1Taskflow.html#ac433018262e44b12c4cc9f0c4748d758" title="dumps the taskflow to a std::ostream in DOT format ">tf::Taskflow::dump</a>.</p>
<h1><a class="anchor" id="DetachASubflow"></a>
Detach a Subflow</h1>
<p>By default, a spawned subflow joins its parent task. That is, all nodes of zero outgoing edges in the subflow will precede the parent task. This forces a subflow to follow the dependency constraints after its parent task. Having said that, you can detach a subflow from its parent task, allowing its execution to flow independently.</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#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"A"</span>); <span class="comment">// static task A</span></div><div class="line"> 4: <a class="code" href="classtf_1_1Task.html">tf::Task</a> C = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"C"</span>); <span class="comment">// static task C</span></div><div class="line"> 5: <a class="code" href="classtf_1_1Task.html">tf::Task</a> D = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"D"</span>); <span class="comment">// static task D</span></div><div class="line"> 6:</div><div class="line"> 7: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] (<a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a>& subflow) { </div><div class="line"> 8: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B1 = subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"B1"</span>); <span class="comment">// dynamic task B1</span></div><div class="line"> 9: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B2 = subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"B2"</span>); <span class="comment">// dynamic task B2</span></div><div class="line">10: <a class="code" href="classtf_1_1Task.html">tf::Task</a> B3 = subflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {}).name(<span class="stringliteral">"B3"</span>); <span class="comment">// dynamic task B3</span></div><div class="line">11: B1.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B3); <span class="comment">// B1 runs bofore B3</span></div><div class="line">12: B2.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B3); <span class="comment">// B2 runs before B3</span></div><div class="line">13: subflow.<a class="code" href="classtf_1_1Subflow.html#acfdedc7e9676126e9a38ecf7b5a37864">detach</a>(); <span class="comment">// detach this subflow</span></div><div class="line">14: }).name(<span class="stringliteral">"B"</span>);</div><div class="line">15:</div><div class="line">16: A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B); <span class="comment">// B runs after A</span></div><div class="line">17: A.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(C); <span class="comment">// C runs after A</span></div><div class="line">18: B.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D); <span class="comment">// D runs after B</span></div><div class="line">19: C.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(D); <span class="comment">// D runs after C</span></div><div class="line">20:</div><div class="line">21: <a class="code" href="classtf_1_1Executor.html">tf::Executor</a>().<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).get(); <span class="comment">// execute the graph to spawn the subflow</span></div><div class="line">22: taskflow.<a class="code" href="classtf_1_1Taskflow.html#ac433018262e44b12c4cc9f0c4748d758">dump</a>(<a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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="comment">// dump the taskflow to DOT format</span></div></div><!-- fragment --><p>The figure below demonstrates a detached subflow based on the previous example. A detached subflow will eventually join the topology of its parent task.</p>
<div class="image">
<img src="subflow_detach.png" alt="subflow_detach.png" width="60%"/>
</div>
<h1><a class="anchor" id="NestedSubflow"></a>
Nested Subflow</h1>
<p>A subflow can be nested or recursive. You can create another subflow from the execution of a subflow and so on.</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#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] (<a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a>& sbf){</div><div class="line"> 4: <a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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">"A spawns A1 & subflow A2\n"</span>;</div><div class="line"> 5: <a class="code" href="classtf_1_1Task.html">tf::Task</a> A1 = sbf.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {</div><div class="line"> 6: <a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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">"subtask A1\n"</span>;</div><div class="line"> 7: }).name(<span class="stringliteral">"A1"</span>);</div><div class="line"> 8:</div><div class="line"> 9: <a class="code" href="classtf_1_1Task.html">tf::Task</a> A2 = sbf.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] (<a class="code" href="classtf_1_1Subflow.html">tf::Subflow</a>& sbf2){</div><div class="line">10: <a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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">"A2 spawns A2_1 & A2_2\n"</span>;</div><div class="line">11: <a class="code" href="classtf_1_1Task.html">tf::Task</a> A2_1 = sbf2.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {</div><div class="line">12: <a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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">"subtask A2_1\n"</span>;</div><div class="line">13: }).name(<span class="stringliteral">"A2_1"</span>);</div><div class="line">14: <a class="code" href="classtf_1_1Task.html">tf::Task</a> A2_2 = sbf2.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([] () {</div><div class="line">15: <a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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">"subtask A2_2\n"</span>;</div><div class="line">16: }).name(<span class="stringliteral">"A2_2"</span>);</div><div class="line">17: A2_1.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(A2_2);</div><div class="line">18: }).name(<span class="stringliteral">"A2"</span>);</div><div class="line">19: A1.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(A2);</div><div class="line">20: }).name(<span class="stringliteral">"A"</span>);</div><div class="line">21:</div><div class="line">22: <span class="comment">// execute the graph to spawn the subflow</span></div><div class="line">23: <a class="code" href="classtf_1_1Executor.html">tf::Executor</a>().<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).get();</div><div class="line">24: taskflow.<a class="code" href="classtf_1_1Taskflow.html#ac433018262e44b12c4cc9f0c4748d758">dump</a>(<a class="codeRef" doxygen="/home/tsung-wei/Code/cpp-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 --><div class="image">
<img src="nested_subflow.png" alt="nested_subflow.png" width="45%"/>
</div>
<p>Debrief: </p><ul>
<li>Line 1 creates a taskflow object </li>
<li>Line 3-20 creates a task to spawn a subflow of two tasks A1 and A2 </li>
<li>Line 9-18 spawns another subflow of two tasks A2_1 and A2_2 out of its parent task A2 </li>
<li>Line 23-24 dispatches the graph asynchronously and dump its structure when it finishes</li>
</ul>
<p>Similarly, you can detach a nested subflow from its parent subflow. A detached subflow will run independently and eventually join the topology of its parent subflow. </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="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>