forked from taskflow/taskflow
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathchapter3.html
More file actions
145 lines (143 loc) · 20.7 KB
/
chapter3.html
File metadata and controls
145 lines (143 loc) · 20.7 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.3.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('chapter3.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">C3: Dynamic Tasking </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="C3_CreateASubflow"></a>
Create 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, emplace a callable that takes an 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 and forwarded to the execution context of the task. All methods you find in <a class="el" href="classtf_1_1Taskflow.html" title="the class to create a task dependency graph ">tf::Taskflow</a> are applicable for <a class="el" href="classtf_1_1Subflow.html" title="The building blocks of dynamic tasking. ">tf::Subflow</a>.</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: <a class="code" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div><div class="line"> 3:</div><div class="line"> 4: <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"> 5: <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"> 6: <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"> 7:</div><div class="line"> 8: <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"> 9: <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">10: <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">11: <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">12: 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">13: 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">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: executor.<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 a DOT format</span></div></div><!-- fragment --><div class="image">
<object type="image/svg+xml" data="subflow_join.svg" width="35%">subflow_join.svg</object>
</div>
<p>Debrief: </p><ul>
<li>Line 1-2 creates a taskflow and an executor </li>
<li>Line 4-6 creates three tasks, A, C, and D </li>
<li>Line 8-14 creates a task B that spawns a task dependency graph of three tasks B1, B2, and B3 </li>
<li>Line 16-19 adds dependencies among A, B, C, and D </li>
<li>Line 21 submits the graph to an executor and waits until it finishes </li>
<li>Line 22 dumps the entire task dependency graph</li>
</ul>
<p>Line 8-14 is the main 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 to spawn the graph and then call <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">
<object type="image/svg+xml" data="subflow_detach.svg" width="45%">subflow_detach.svg</object>
</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">
<object type="image/svg+xml" data="nested_subflow.svg" width="55%">nested_subflow.svg</object>
</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>