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
177 lines (175 loc) · 27.4 KB
/
chapter4.html
File metadata and controls
177 lines (175 loc) · 27.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
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
<!-- 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('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: Create a Parallel Reduction Graph </div> </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><p>Parallel tasks normally produce some quantity that needs to be combined or <em>reduced</em> through particular operations, for instance, sum. In this chapter, we are going to demonstrate how to use Cpp-Taskflow to parallelize a reduction workload.</p>
<h1><a class="anchor" id="ReduceARangeOfItemsToASingleResult"></a>
Reduce a Range of Items to a Single Result</h1>
<p><a class="el" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb" title="construct a task dependency graph of parallel reduction ">tf::Taskflow::reduce(I beg, I end, T& result, B&& bop)</a> is the most common reduction method to create a task dependency graph that reduces a range of items to a single result through a binary operator.</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="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/container/vector.html">std::vector<int></a> items {1, 2, 3, 4, 5, 6, 7, 8};</div><div class="line"> 4: <span class="keywordtype">int</span> sum {0};</div><div class="line"> 5:</div><div class="line"> 6: <span class="keyword">auto</span> [S, T] = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb">reduce</a>(items.begin(), items.end(), sum, [] (<span class="keywordtype">int</span> a, <span class="keywordtype">int</span> b) {</div><div class="line"> 7: <span class="keywordflow">return</span> a + b;</div><div class="line"> 8: });</div><div class="line"> 9:</div><div class="line">10: S.<a class="code" href="classtf_1_1Task.html#a08ada0425b490997b6ff7f310107e5e3">name</a>(<span class="stringliteral">"S"</span>);</div><div class="line">11: T.<a class="code" href="classtf_1_1Task.html#a08ada0425b490997b6ff7f310107e5e3">name</a>(<span class="stringliteral">"T"</span>);</div><div class="line">12:</div><div class="line">13: <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">14:</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">"sum = "</span> << sum << <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/manip/endl.html">std::endl</a>; <span class="comment">// 36</span></div></div><!-- fragment --><p>Debrief:</p>
<ul>
<li>Line 1 creates a taskflow object </li>
<li>Line 3 creates a vector of integers </li>
<li>Line 4 declares an integer variable <code>sum</code> and initializes it to zero </li>
<li>Line 6-8 constructs a reduction graph that sums up all integer itmes and stores the final result in <code>sum</code> </li>
<li>Line 10-11 names the two synchronization points </li>
<li>Line 13 dispatches the graph for execution </li>
<li>Line 15 prints out the final reduction value</li>
</ul>
<p>The task dependency graph of this example is shown below:</p>
<div class="image">
<img src="reduce1.png" alt="reduce1.png" width="60%"/>
</div>
<p><a class="el" href="classtf_1_1Taskflow.html" title="the class to create a task dependency graph ">Taskflow</a> partitions and distributes the workload evenly across all workers for all reduction methods. In this example, each internal node sums up two integers and the target node <code>T</code> combine all results returned by the internal nodes to a single value.</p>
<h1><a class="anchor" id="TransformAndReduce"></a>
Transform and Reduce</h1>
<p>It is common to transform each item into a new data type and then perform reduction on the transformed sequences. <a class="el" href="classtf_1_1Taskflow.html" title="the class to create a task dependency graph ">Taskflow</a> provides a method, <a class="el" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef" title="constructs a task dependency graph of parallel transformation and reduction ">tf::Taskflow::transform_reduce(I beg, I end, T& result, B&& bop, U&& uop)</a>, that fuses these two operators together to save memory reads and writes. The example below takes a string and transforms each digit to an integer number, and then applies reduction to sum up all integer numbers.</p>
<div class="fragment"><div class="line"> 1: <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/string/basic_string.html">std::string</a> str = <span class="stringliteral">"12345678"</span>;</div><div class="line"> 2: <span class="keywordtype">int</span> sum {0};</div><div class="line"> 3:</div><div class="line"> 4: <span class="keyword">auto</span> [S, T] = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef">transform_reduce</a>(str.begin(), str.end(), sum,</div><div class="line"> 5: [] (<span class="keywordtype">int</span> a, <span class="keywordtype">int</span> b) {</div><div class="line"> 6: <span class="keywordflow">return</span> a + b;</div><div class="line"> 7: }, </div><div class="line"> 8: [] (<span class="keywordtype">char</span> c) -> <span class="keywordtype">int</span> {</div><div class="line"> 9: <span class="keywordflow">return</span> c - <span class="charliteral">'0'</span>;</div><div class="line">10: } </div><div class="line">11: ); </div><div class="line">12:</div><div class="line">13: <span class="comment">// sum will be 36 after execution</span></div></div><!-- fragment --><p>Debrief:</p>
<ul>
<li>Line 1 creates a string of eight digits </li>
<li>Line 2 declares an integer variables and initializes it to zero </li>
<li>Line 4-11 constructs a reduction graph that converts each character of the string into an integer and computes the sum of all integers</li>
</ul>
<p><a class="el" href="classtf_1_1Taskflow.html" title="the class to create a task dependency graph ">Taskflow</a> has another overload <a class="el" href="classtf_1_1FlowBuilder.html#a9b81ad3b206a63adff8b8bc423f8c425" title="constructs a task dependency graph of parallel transformation and reduction ">tf::Taskflow::transform_reduce(I beg, I end, T& result, B&& bop1, P&& bop2, U&& uop)</a> that takes an additional binary operator <code>bop2</code> to combine the result of <code>uop</code> and the dereferencing of an input iterator to a data type that is acceptable as input to <code>bop1</code>. This is useful when extra computation is required during the reduction process.</p>
<div class="fragment"><div class="line"> 1: <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/string/basic_string.html">std::string</a> str = <span class="stringliteral">"12345678"</span>;</div><div class="line"> 2:</div><div class="line"> 3: <span class="keywordtype">double</span> sum {0};</div><div class="line"> 4:</div><div class="line"> 5: <span class="keyword">auto</span> [S, T] = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef">transform_reduce</a>(str.begin(), str.end(), sum,</div><div class="line"> 6: [] (<span class="keywordtype">double</span> a, <span class="keywordtype">double</span> b) {</div><div class="line"> 7: <span class="keywordflow">return</span> a + b;</div><div class="line"> 8: }, </div><div class="line"> 9: [] (<span class="keywordtype">double</span> a, <span class="keywordtype">char</span> c) -> <span class="keywordtype">double</span> {</div><div class="line">10: <span class="keywordflow">return</span> a + (c - <span class="charliteral">'0'</span>);</div><div class="line">11: }, </div><div class="line">12: [] (<span class="keywordtype">char</span> c) -> <span class="keywordtype">double</span> {</div><div class="line">13: <span class="keywordflow">return</span> <span class="keyword">static_cast<</span><span class="keywordtype">double</span><span class="keyword">></span>(c - <span class="charliteral">'0'</span>);</div><div class="line">14: } </div><div class="line">15: ); </div><div class="line">16:</div><div class="line">17: <span class="comment">// sum will be 36 after execution</span></div></div><!-- fragment --><p>Debrief:</p>
<ul>
<li>Line 1 creates a string of eight digits </li>
<li>Line 3 declares an integer variable and initializes it to zero </li>
<li>Line 5 constructs a reduction graph that represents the reduction workload </li>
<li>Line 6-8 takes a binary operator to combine two transformed data </li>
<li>Line 9-11 takes a binary operator to combine one raw data together with a transformed data </li>
<li>Line 12-14 takes a unary operator to transform one raw data to the reduced data type</li>
</ul>
<p>The difference between the two overloads appears in the second binary operator. Instead of converting every item to the reduced data type, this binary operator provides a more fine-grained control over reduction.</p>
<h1><a class="anchor" id="Chapter4Example1"></a>
Example 1: Find the Min/Max Element</h1>
<p>One common workload of using reduce is to find the minimum or the maximum element in a range of items. This example demonstrates how to use the method <a class="el" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb" title="construct a task dependency graph of parallel reduction ">tf::Taskflow::reduce</a> to find the minimum element in a data set.</p>
<div class="fragment"><div class="line"> 1: #include <taskflow/taskflow.hpp></div><div class="line"> 2:</div><div class="line"> 3: <span class="keywordtype">int</span> main() {</div><div class="line"> 4:</div><div class="line"> 5: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"> 6:</div><div class="line"> 7: <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/container/vector.html">std::vector<int></a> items {4, 2, 1, 3, 7, 8, 6, 5};</div><div class="line"> 8: <span class="keywordtype">int</span> <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/algorithm/min.html">min</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/types/numeric_limits/max.html">std::numeric_limits<int>::max</a>();</div><div class="line"> 9:</div><div class="line">10: taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb">reduce</a>(items.begin(), items.end(), min, [] (<span class="keywordtype">int</span> a, <span class="keywordtype">int</span> b) {</div><div class="line">11: <span class="keywordflow">return</span> <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/algorithm/min.html">std::min</a>(a, b);</div><div class="line">12: });</div><div class="line">13:</div><div class="line">14: <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">15:</div><div class="line">16: <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> << min << std::endl; <span class="comment">// 1</span></div><div class="line">17:</div><div class="line">18: <span class="keywordflow">return</span> 0;</div><div class="line">19: }</div></div><!-- fragment --><p>Similarly, the example below finds the maximum element in a data set.</p>
<div class="fragment"><div class="line"> 1: #include <taskflow/taskflow.hpp></div><div class="line"> 2:</div><div class="line"> 3: <span class="keywordtype">int</span> main() {</div><div class="line"> 4:</div><div class="line"> 5: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"> 6:</div><div class="line"> 7: <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/container/vector.html">std::vector<int></a> items {4, 2, 1, 3, 7, 8, 6, 5};</div><div class="line"> 8: <span class="keywordtype">int</span> <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/algorithm/max.html">max</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/types/numeric_limits/min.html">std::numeric_limits<int>::min</a>();</div><div class="line"> 9:</div><div class="line">10: taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb">reduce</a>(items.begin(), items.end(), max, [] (<span class="keywordtype">int</span> a, <span class="keywordtype">int</span> b) {</div><div class="line">11: <span class="keywordflow">return</span> <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/algorithm/max.html">std::max</a>(a, b);</div><div class="line">12: });</div><div class="line">13:</div><div class="line">14: <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">15:</div><div class="line">16: <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> << max << std::endl; <span class="comment">// 8</span></div><div class="line">17:</div><div class="line">18: <span class="keywordflow">return</span> 0;</div><div class="line">19: }</div></div><!-- fragment --><h1><a class="anchor" id="Chapter4Example2"></a>
Example 2: Pipeline a Reduction Graph</h1>
<p>The <a class="el" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb" title="construct a task dependency graph of parallel reduction ">tf::Taskflow::reduce</a> method returns a task pair as two synchronization points of the reduction graph which can be used to pipeline with other tasks. The example below demonstrates how to pipeline a reduction graph with other tasks.</p>
<div class="fragment"><div class="line"> 1: #include <taskflow/taskflow.hpp></div><div class="line"> 2:</div><div class="line"> 3: <span class="keywordtype">int</span> main() {</div><div class="line"> 4:</div><div class="line"> 5: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"> 6:</div><div class="line"> 7: <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/container/vector.html">std::vector<int></a> items{1024};</div><div class="line"> 8: <span class="keywordtype">int</span> min = <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/types/numeric_limits/max.html">std::numeric_limits<int>::max</a>();</div><div class="line"> 9:</div><div class="line">10: <a class="code" href="classtf_1_1Task.html">tf::Task</a> T1 = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([&] () { <span class="comment">// modifier task</span></div><div class="line">11: <span class="keywordflow">for</span>(<span class="keyword">auto</span>& item : items) {</div><div class="line">12: item = ::rand();</div><div class="line">13: }</div><div class="line">14: });</div><div class="line">15:</div><div class="line">16: <span class="keyword">auto</span> [S, T] = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb">reduce</a>(items.begin(), items.end(), min, [] (<span class="keywordtype">int</span> a, <span class="keywordtype">int</span> b) {</div><div class="line">17: <span class="keywordflow">return</span> <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/algorithm/min.html">std::min</a>(a, b);</div><div class="line">18: });</div><div class="line">19:</div><div class="line">20: <a class="code" href="classtf_1_1Task.html">tf::Task</a> T2 = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([&] () { <span class="comment">// printer task</span></div><div class="line">21: <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">"min is "</span> << min << std::endl;</div><div class="line">22: });</div><div class="line">23:</div><div class="line">24: T1.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(S); <span class="comment">// modifier task precedes the reducer</span></div><div class="line">25: T.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(T2); <span class="comment">// reducer precedes the printer task</span></div><div class="line">26:</div><div class="line">27: <a class="code" href="classtf_1_1Executor.html">tf::Executor</a>().<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow);</div><div class="line">28:</div><div class="line">29: <span class="keywordflow">return</span> 0;</div><div class="line">30: }</div></div><!-- fragment --><p>Debrief: </p><ul>
<li>Line 5 creates a taskflow object with four worker threads </li>
<li>Line 7 creates a vector of 1024 uninitialized integers </li>
<li>Line 8 creates an integer value and initializes it to the maximum representable value of <code>int</code> </li>
<li>Line 10-14 creates a modifier task that initializes the vector to random integer values </li>
<li>Line 16-18 creates a reduction graph to find the minimum element in the vector </li>
<li>Line 20-22 creates a task that prints the minimum value found after the reduction finishes </li>
<li>Line 24-25 adds two dependency links to implement our control flow </li>
<li>Line 27 dispatches the task dependency graph to threads and waits until the execution completes</li>
</ul>
<p>In the reduction graph, each worker thread applies the give reduce operator to a partition of 1024/4 = 512 items. The final minimum value is stored in the variable <code>min</code>. Since the variable <code>min</code> participates in the reduction process, it is users' responsibility to initialize it to a proper value.</p>
<h1><a class="anchor" id="Chapter4Example3"></a>
Example 3: Find the Minimum L1-norm</h1>
<p>The example below applies the method <a class="el" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef" title="constructs a task dependency graph of parallel transformation and reduction ">tf::Taskflow::transform_reduce</a> to find the minimum L1-norm out of a point set.</p>
<div class="fragment"><div class="line"> 1: #include <taskflow/taskflow.hpp></div><div class="line"> 2: </div><div class="line"> 3: <span class="keyword">struct </span>Point {</div><div class="line"> 4: <span class="keywordtype">int</span> x1 {::rand() % 10 - 5}; <span class="comment">// random value</span></div><div class="line"> 5: <span class="keywordtype">int</span> x2 {::rand() % 10 - 5}; <span class="comment">// random value</span></div><div class="line"> 6: };</div><div class="line"> 7: </div><div class="line"> 8: <span class="keywordtype">int</span> main() {</div><div class="line"> 9: </div><div class="line">10: <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line">11: </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/container/vector.html">std::vector<Point></a> points {1024};</div><div class="line">13: <span class="keywordtype">int</span> min = <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/types/numeric_limits/max.html">std::numeric_limits<int>::max</a>();</div><div class="line">14: </div><div class="line">15: taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef">transform_reduce</a>(points.begin(), points.end(), min,</div><div class="line">16: [] (<span class="keywordtype">int</span> a, <span class="keywordtype">int</span> b) {</div><div class="line">17: <span class="keywordflow">return</span> <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/algorithm/min.html">std::min</a>(a, b);</div><div class="line">18: },</div><div class="line">19: [] (<span class="keyword">const</span> Point& point) -> <span class="keywordtype">int</span> { <span class="comment">// Find the L1-norm of the point</span></div><div class="line">20: <span class="keywordflow">return</span> std::abs(point.x1) + std::abs(point.x2);</div><div class="line">21: }</div><div class="line">22: );</div><div class="line">23: </div><div class="line">24: <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">25: </div><div class="line">26: <span class="keywordflow">return</span> 0;</div><div class="line">27: }</div></div><!-- fragment --><p>Debrief: </p><ul>
<li>Line 3-6 declares a point struct at 2D plane </li>
<li>Line 10 creates a taskflow object with four worker threads </li>
<li>Line 12 creates a vector of 1024 randomly initialized points </li>
<li>Line 13 creates an integer value and initializes it to the maximum representable value of <code>int</code> </li>
<li>Line 15-22 applies transform-reduce operation to find the point with the minimum L1 distance </li>
<li>Line 24 dispatches the task dependency graph to threads and waits until the execution completes </li>
</ul>
</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>