-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathAsyncTasking.html
More file actions
248 lines (246 loc) · 21.5 KB
/
Copy pathAsyncTasking.html
File metadata and controls
248 lines (246 loc) · 21.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
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
<!-- HTML header for doxygen 1.13.1-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.13.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow: A General-purpose Task-parallel Programming System: Asynchronous Tasking</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="cookie.js"></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" />
<link href="custom.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 id="projectrow">
<td id="projectlogo"><img alt="Logo" src="taskflow_logo.png"/></td>
<td id="projectalign">
<div id="projectname"><a href="https://github.com/taskflow/taskflow" style="color:inherit; text-decoration:none;">Taskflow: A General-purpose Task-parallel Programming System</a>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.13.1 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() { codefold.init(0); });
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',true,false,'search.php','Search',true);
$(function() { init_search(); });
});
/* @license-end */
</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">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function(){initNavTree('AsyncTasking.html',''); initResizable(true); });
/* @license-end */
</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">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<div><div class="header">
<div class="headertitle"><div class="title">Asynchronous Tasking</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#WhatIsAnAsyncTask">What is an Async Task?</a>
</li>
<li class="level1">
<a href="#LaunchAsynchronousTasksFromAnExecutor">Launch Async Tasks from an Executor</a>
</li>
<li class="level1">
<a href="#LaunchAsynchronousTasksFromARuntime">Launch Async Tasks from a Runtime</a>
</li>
<li class="level1">
<a href="#LaunchAsynchronousTasksRecursivelyFromARuntime">Launch Async Tasks Recursively from a Runtime</a>
</li>
</ul>
</div>
<div class="textblock"><p>Taskflow provides mechanisms to launch tasks asynchronously, enabling dynamic parallelism that goes beyond static task graphs.</p>
<h1><a class="anchor" id="WhatIsAnAsyncTask"></a>
What is an Async Task?</h1>
<p>An async task is a callable object submitted for execution without being embedded in a pre-defined task graph. Unlike regular taskflow tasks whose dependencies are declared upfront, async tasks are created and dispatched on the fly, making them suitable for dynamic, recursive, or data-dependent parallelism that cannot be fully determined at graph construction time.</p>
<p>The C++ standard library provides <code>std::async</code> for this purpose. However, <code>std::async</code> has fundamental limitations that make it ill-suited for high-performance parallel programs:</p>
<div class="fragment"><div class="line"><span class="comment">// std::async typically spawns a new OS thread for each call</span></div>
<div class="line">std::future<int> f1 = std::async(std::launch::async, []() { <span class="keywordflow">return</span> 1; });</div>
<div class="line">std::future<int> f2 = std::async(std::launch::async, []() { <span class="keywordflow">return</span> 2; });</div>
<div class="line">std::future<int> f3 = std::async(std::launch::async, []() { <span class="keywordflow">return</span> 3; });</div>
<div class="line"><span class="comment">// ... spawning N tasks creates N threads, each with its own stack and</span></div>
<div class="line"><span class="comment">// OS overhead — expensive to create, destroy, and context-switch</span></div>
</div><!-- fragment --><p>The three core problems with <code>std::async</code> are:</p>
<ul>
<li><b>No</b> <b>thread</b> <b>pool:</b> each call to <code>std::async</code> typically creates a brand-new OS thread, incurring significant creation and destruction overhead. Spawning hundreds of async tasks means hundreds of threads competing for CPU time.</li>
<li><b>No</b> <b>scheduler:</b> there is no work-stealing or load balancing between <code>std::async</code> tasks. If one task finishes early, its thread sits idle rather than picking up work from overloaded threads.</li>
<li><b>No</b> <b>task</b> <b>graph</b> <b>integration:</b> <code>std::async</code> tasks are isolated from one another. You cannot express dependencies between them, embed them in a larger task graph, or coordinate them with other parallel work.</li>
</ul>
<p>Taskflow's async tasking addresses all three problems. Async tasks run on the executor's existing thread pool under the same work-stealing scheduler, integrate naturally with taskflows and runtimes, and can be launched from any thread without additional overhead.</p>
<h1><a class="anchor" id="LaunchAsynchronousTasksFromAnExecutor"></a>
Launch Async Tasks from an Executor</h1>
<p><a class="el" href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7" title="creates a parameterized asynchronous task to run the given function">tf::Executor::async</a> runs a callable asynchronously on the thread pool and returns a <code>std::future</code> that will eventually hold the result:</p>
<div class="fragment"><div class="line">std::future<int> future = executor.async([](){ <span class="keywordflow">return</span> 1; });</div>
<div class="line">assert(future.get() == 1);</div>
</div><!-- fragment --><p>If you do not need the return value or do not require a <code>std::future</code> for synchronisation, use <a class="el" href="classtf_1_1Executor.html#a0461cb2c459c9f9473c72af06af9c701" title="similar to tf::Executor::async but does not return a future object">tf::Executor::silent_async</a> instead. It returns nothing and incurs less overhead than <a class="el" href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7" title="creates a parameterized asynchronous task to run the given function">tf::Executor::async</a>, as it avoids the cost of managing a shared state:</p>
<div class="fragment"><div class="line">executor.silent_async([](){});</div>
</div><!-- fragment --><p>Both <a class="el" href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7" title="creates a parameterized asynchronous task to run the given function">tf::Executor::async</a> and <a class="el" href="classtf_1_1Executor.html#a0461cb2c459c9f9473c72af06af9c701" title="similar to tf::Executor::async but does not return a future object">tf::Executor::silent_async</a> are <em>thread-safe</em> and can be called from any thread — including worker threads already running inside the executor and external threads outside of it. The scheduler automatically detects the submission source and applies work-stealing to distribute the task efficiently across workers:</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classtf_1_1Task.html">tf::Task</a> my_task = taskflow.emplace([&]() {</div>
<div class="line"> <span class="comment">// launch an async task from a worker thread inside the executor</span></div>
<div class="line"> executor.async([&]() {</div>
<div class="line"> <span class="comment">// launch another async task from yet another worker thread</span></div>
<div class="line"> executor.async([&]() {});</div>
<div class="line"> });</div>
<div class="line">});</div>
<div class="line">executor.run(taskflow);</div>
<div class="line">executor.wait_for_all();</div>
<div class="ttc" id="aclasstf_1_1Task_html"><div class="ttname"><a href="classtf_1_1Task.html">tf::Task</a></div><div class="ttdoc">class to create a task handle over a taskflow node</div><div class="ttdef"><b>Definition</b> task.hpp:569</div></div>
</div><!-- fragment --><dl class="section note"><dt>Note</dt><dd>Async tasks created from an executor do not belong to any taskflow. Their lifetime is automatically managed by the executor.</dd></dl>
<h1><a class="anchor" id="LaunchAsynchronousTasksFromARuntime"></a>
Launch Async Tasks from a Runtime</h1>
<p><a class="el" href="classtf_1_1Runtime.html#a5688b13034f179c4a8b2b0ebbb215051" title="runs the given callable asynchronously">tf::Runtime::async</a> and <a class="el" href="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05" title="runs the given function asynchronously without returning any future object">tf::Runtime::silent_async</a> let you launch async tasks from within a running task that has access to a <a class="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> object. Like their executor counterparts, both methods are <em>thread-safe</em> and can be called from any context within the runtime's scope.</p>
<p>Unlike executor-level async tasks, tasks created from a runtime belong to that runtime and are implicitly joined at the end of its scope — meaning all async tasks spawned inside a runtime are guaranteed to finish before the runtime completes and control returns to the next task in the graph.</p>
<p>The example below spawns 100 async tasks from a runtime. Because of the implicit join, task <code>B</code> is guaranteed to see <code>counter</code> == 100:</p>
<div class="fragment"><div class="line"><a class="code hl_class" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div>
<div class="line"><a class="code hl_class" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div>
<div class="line">std::atomic<int> counter{0};</div>
<div class="line"> </div>
<div class="line"><a class="code hl_class" href="classtf_1_1Task.html">tf::Task</a> A = taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([&](<a class="code hl_class" href="classtf_1_1Runtime.html">tf::Runtime</a>& rt) {</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i = 0; i < 100; i++) {</div>
<div class="line"> rt.<a class="code hl_function" href="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05">silent_async</a>([&](){ ++counter; });</div>
<div class="line"> }</div>
<div class="line">}); <span class="comment">// implicit join: all 100 tasks finish before A completes</span></div>
<div class="line"> </div>
<div class="line">tf::Task B = taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([&]() {</div>
<div class="line"> assert(counter == 100);</div>
<div class="line">});</div>
<div class="line">A.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(B);</div>
<div class="line"> </div>
<div class="line">executor.<a class="code hl_function" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">run</a>(taskflow).wait();</div>
<div class="ttc" id="aclasstf_1_1Executor_html"><div class="ttname"><a href="classtf_1_1Executor.html">tf::Executor</a></div><div class="ttdoc">class to create an executor</div><div class="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<div class="ttc" id="aclasstf_1_1Executor_html_a519777f5783981d534e9e53b99712069"><div class="ttname"><a href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">tf::Executor::run</a></div><div class="ttdeci">tf::Future< void > run(Taskflow &taskflow)</div><div class="ttdoc">runs a taskflow once</div></div>
<div class="ttc" id="aclasstf_1_1FlowBuilder_html_a4d52a7fe2814b264846a2085e931652c"><div class="ttname"><a href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">tf::FlowBuilder::emplace</a></div><div class="ttdeci">Task emplace(C &&callable)</div><div class="ttdoc">creates a static task</div><div class="ttdef"><b>Definition</b> flow_builder.hpp:1571</div></div>
<div class="ttc" id="aclasstf_1_1Runtime_html"><div class="ttname"><a href="classtf_1_1Runtime.html">tf::Runtime</a></div><div class="ttdoc">class to create a runtime task</div><div class="ttdef"><b>Definition</b> runtime.hpp:47</div></div>
<div class="ttc" id="aclasstf_1_1Runtime_html_a0ce29efa2106c8c5a1432e4a55ab2e05"><div class="ttname"><a href="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05">tf::Runtime::silent_async</a></div><div class="ttdeci">void silent_async(F &&f)</div><div class="ttdoc">runs the given function asynchronously without returning any future object</div><div class="ttdef"><b>Definition</b> runtime.hpp:671</div></div>
<div class="ttc" id="aclasstf_1_1Task_html_a8c78c453295a553c1c016e4062da8588"><div class="ttname"><a href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">tf::Task::precede</a></div><div class="ttdeci">Task & precede(Ts &&... tasks)</div><div class="ttdoc">adds precedence links from this to other tasks</div><div class="ttdef"><b>Definition</b> task.hpp:1258</div></div>
<div class="ttc" id="aclasstf_1_1Taskflow_html"><div class="ttname"><a href="classtf_1_1Taskflow.html">tf::Taskflow</a></div><div class="ttdoc">class to create a taskflow object</div><div class="ttdef"><b>Definition</b> taskflow.hpp:64</div></div>
</div><!-- fragment --><p>Launching async tasks from a runtime is the key enabler for dynamic parallel algorithms — parallel reduction, divide-and-conquer, and recursive patterns — that need to create work at runtime rather than at graph construction time.</p>
<h1><a class="anchor" id="LaunchAsynchronousTasksRecursivelyFromARuntime"></a>
Launch Async Tasks Recursively from a Runtime</h1>
<p>Async tasks spawned from a runtime can themselves accept a <a class="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> reference, allowing them to recursively spawn further async tasks. Combined with <a class="el" href="classtf_1_1Runtime.html#aba54a7cacffb54f5eb133730d256a7c4" title="corun all tasks spawned by this runtime with other workers">tf::Runtime::corun</a>, this enables fork-join style divide-and-conquer parallelism where each level of recursion fans out work to available workers without blocking any thread.</p>
<p>The example below implements parallel Fibonacci using recursive async tasking:</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <taskflow/taskflow.hpp></span></div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">size_t</span> fibonacci(<span class="keywordtype">size_t</span> N, <a class="code hl_class" href="classtf_1_1Runtime.html">tf::Runtime</a>& rt) {</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">if</span>(N < 2) <span class="keywordflow">return</span> N;</div>
<div class="line"> </div>
<div class="line"> <span class="keywordtype">size_t</span> res1, res2;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// spawn the left child asynchronously</span></div>
<div class="line"> rt.<a class="code hl_function" href="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05">silent_async</a>([N, &res1](<a class="code hl_class" href="classtf_1_1Runtime.html">tf::Runtime</a>& rt1) {</div>
<div class="line"> res1 = fibonacci(N-1, rt1);</div>
<div class="line"> });</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// compute the right child inline (tail optimisation)</span></div>
<div class="line"> res2 = fibonacci(N-2, rt);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// wait for all async children without blocking the worker thread</span></div>
<div class="line"> rt.<a class="code hl_function" href="classtf_1_1Runtime.html#aba54a7cacffb54f5eb133730d256a7c4">corun</a>();</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">return</span> res1 + res2;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> </div>
<div class="line"> <a class="code hl_class" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div>
<div class="line"> </div>
<div class="line"> <span class="keywordtype">size_t</span> N = 5, res;</div>
<div class="line"> executor.<a class="code hl_function" href="classtf_1_1Executor.html#a0461cb2c459c9f9473c72af06af9c701">silent_async</a>([N, &res](<a class="code hl_class" href="classtf_1_1Runtime.html">tf::Runtime</a>& rt) {</div>
<div class="line"> res = fibonacci(N, rt);</div>
<div class="line"> });</div>
<div class="line"> executor.<a class="code hl_function" href="classtf_1_1Executor.html#ab9aa252f70e9a40020a1e5a89d485b85">wait_for_all</a>();</div>
<div class="line"> </div>
<div class="line"> std::cout << N << <span class="stringliteral">"-th Fibonacci number is "</span> << res << <span class="charliteral">'\n'</span>;</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclasstf_1_1Executor_html_a0461cb2c459c9f9473c72af06af9c701"><div class="ttname"><a href="classtf_1_1Executor.html#a0461cb2c459c9f9473c72af06af9c701">tf::Executor::silent_async</a></div><div class="ttdeci">void silent_async(P &&params, F &&func)</div><div class="ttdoc">similar to tf::Executor::async but does not return a future object</div></div>
<div class="ttc" id="aclasstf_1_1Executor_html_ab9aa252f70e9a40020a1e5a89d485b85"><div class="ttname"><a href="classtf_1_1Executor.html#ab9aa252f70e9a40020a1e5a89d485b85">tf::Executor::wait_for_all</a></div><div class="ttdeci">void wait_for_all()</div><div class="ttdoc">waits for all tasks to complete</div></div>
<div class="ttc" id="aclasstf_1_1Runtime_html_aba54a7cacffb54f5eb133730d256a7c4"><div class="ttname"><a href="classtf_1_1Runtime.html#aba54a7cacffb54f5eb133730d256a7c4">tf::Runtime::corun</a></div><div class="ttdeci">void corun()</div><div class="ttdoc">corun all tasks spawned by this runtime with other workers</div><div class="ttdef"><b>Definition</b> runtime.hpp:646</div></div>
</div><!-- fragment --><dl class="section note"><dt>Note</dt><dd><code>rt.corun()</code> without arguments waits for all async tasks spawned within the current runtime scope to complete, without blocking the underlying worker thread from executing other work in the meantime. This is what allows the recursive pattern to scale efficiently — a blocked worker can participate in executing the spawned children rather than idling.</dd></dl>
<p>The figure below shows the execution diagram for <code>fibonacci(4)</code>. The suffix <em>_1</em> denotes the left child spawned by its parent runtime:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_fibonacci_4_tail_optimized.svg" width="587" height="374"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- 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">
Maintained by <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1
</li>
</ul>
</div>