cpp-taskflow/docs/chapter3.html at cpp14 · ogsdave/cpp-taskflow

History

163 lines (161 loc) · 23.7 KB

Raw

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

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<head>

<title>Cpp-Taskflow</title>

$(document).ready(initResizable);

</script>

$(document).ready(function() { init_search(); });

</script>

</head>

<body>

<tbody>

<div id="projectname"><a href="https://github.com/cpp-taskflow/cpp-taskflow">Cpp-Taskflow</a>

</div>

</td>

<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">

</span>

</div>

</td>

</tr>

</tbody>

</table>

</div>

var searchBox = new SearchBox("searchBox", "search",false,'Search');

</script>

</div>

</div>

<div id="splitbar" style="-moz-user-select:none;"

class="ui-resizable-handle">

</div>

$(document).ready(function(){initNavTree('chapter3.html','');});

</script>

<div id="MSearchSelectWindow"

onmouseover="return searchBox.OnSearchSelectShow()"

onmouseout="return searchBox.OnSearchSelectHide()"

onkeydown="return searchBox.OnSearchSelectKey(event)">

</div>

name="MSearchResults" id="MSearchResults">

</iframe>

</div>

<div class="title">C3: Create a Parallel For-loop Graph </div> </div>

</div>

<div class="textblock"><p>Running a for-loop in parallel is the most fundamental building block in parallel programming. In this chapter, we are going to demonstrate how to use Cpp-Taskflow to create a task dependency graph of parallel for-loop.</p>

Range-based For-loop</h1>

<p>Cpp-Taskflow has a STL-style method <a class="el" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b" title="constructs a task dependency graph of range-based parallel_for ">tf::Taskflow::parallel_for(I beg, I end, C&& callable, size_t partitions)</a> that partitions a range of items and applies a callable to each item in the partition in parallel. The method constructs a task dependency graph representing this workload and returns a task pair as two synchronization points to this task graph.</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:</div><div class="line"> 5: <span class="keyword">auto</span> [S, T] = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(items.begin(), items.end(), [] (<span class="keywordtype">int</span> item) {</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> << <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/thread/get_id.html">std::this_thread::get_id</a>() << <span class="stringliteral">" runs "</span> << item << <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>;</div><div class="line"> 7: });</div><div class="line"> 8:</div><div class="line"> 9: S.work([](){ <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">"S\n"</span>; }).name(<span class="stringliteral">"S"</span>);</div><div class="line">10: T.work([](){ <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">"T\n"</span>; }).name(<span class="stringliteral">"T"</span>);</div><div class="line">11:</div><div class="line">12: 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><p>The above code generates the following task dependency graph. The label 0x56* represents an internal task node to execute the callable object. By default (<code>partitions=0</code>), Cpp-Taskflow evenly partitions and distributes the workload across the maximum hardware concurrency. Suppose our example has four logical cores, each internal node corresponds to a partition taking two items (eight tasks in total).</p>

</div>

<p>Debrief: </p><ul>

<li>Line 1 creates a taskflow object of four worker threads </li>

<li>Line 3 creates a vector container of eight items </li>

<li>Line 5-7 creates a parallel execution graph using the method <code>parallel_for</code> </li>

<li>Line 9-10 names the synchronization tasks <code>S</code> and <code>T</code> </li>

<li>Line 12 dumps the graph to a dot format which can be visualized through <a href="https://dreampuf.github.io/GraphvizOnline/">GraphViz Online</a></li>

</ul>

<p>Here is one possible output of this program:</p>

Partition the Workload Explicitly</h1>

<p>By default, Cpp-Taskflow partitions the workload evenly across the workers. In some cases, it is useful to disable this feature and apply user-specified partition. The method <code>parallel_for</code> tasks an unsigned integer <code>partitions</code> as the number of partitions over the items.</p>

<div class="fragment"><div class="line"><span class="keyword">auto</span> [S, T] = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(items.begin(), items.end(), [] (<span class="keywordtype">int</span> item) {</div><div class="line"> <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> << <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/thread/get_id.html">std::this_thread::get_id</a>() << <span class="stringliteral">" runs "</span> << item << <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>;</div><div class="line">}, 8);</div></div><p>The above example will force each of the eight partitions to run exactly one item. This can be useful when you have unbalanced workload per item and would like to enable more efficient parallelization.</p>

</div>

<p>Again, you can leave the partition variable to 0 to use our default partition strategy.</p>

Construct the Graph Explicitly</h1>

<p>You can explicitly construct a dependency graph that represents a parallel execution of a for-loop using only the basic methods <a class="el" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c" title="creates a task from a given callable object ">tf::Taskflow::emplace</a> and <a class="el" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588" title="adds precedence links from this to other tasks ">tf::Task::precede</a>.</p>

<div class="fragment"><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> S = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([](){}).name(<span class="stringliteral">"S"</span>);</div><div class="line"><a class="code" href="classtf_1_1Task.html">tf::Task</a> T = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([](){}).name(<span class="stringliteral">"T"</span>);</div><div class="line"></div><div class="line"><span class="keywordflow">for</span>(<span class="keyword">auto</span> item : items) {</div><div class="line"> <a class="code" href="classtf_1_1Task.html">tf::Task</a> task = taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a4d52a7fe2814b264846a2085e931652c">emplace</a>([item] () {</div><div class="line"> <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> << <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/thread/get_id.html">std::this_thread::get_id</a>() << <span class="stringliteral">" runs "</span> << item << <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>;</div><div class="line"> });</div><div class="line"> S.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(task);</div><div class="line"> task.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(T);</div><div class="line">}</div></div><h1><a class="anchor" id="IndexBasedForLoop"></a>

Index-based For-loop</h1>

<p>Cpp-Taskflow provides an overload <a class="el" href="classtf_1_1FlowBuilder.html#acfce9d2800a097202bdd4047f205dacf" title="constructs a task dependency graph of index-based parallel_for ">tf::Taskflow::parallel_for(I beg, I end, I step, C&& callable, size_t partitions)</a> to parallelize an index-based for-loop. It takes three numbers <code>beg</code>, <code>end</code>, and <code>step</code> of the same type <code>I</code> and applies <code>callable</code> to each index in the range <code>[beg, end)</code> with the step size <code>step</code>.</p>

<div class="fragment"><div class="line">1: taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(0, 10, 2, [] (<span class="keywordtype">int</span> i) {</div><div class="line">2: <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">"parallel on "</span> << i << <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>;</div><div class="line">3: });</div><div class="line">4: <span class="comment">// print 0, 2, 4, 6, 8</span></div></div><p>It also works on the opposite order with negative step size.</p>

<div class="fragment"><div class="line">1: taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(10, 0, -2, [] (<span class="keywordtype">int</span> i) {</div><div class="line">2: <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">"parallel on "</span> << i << <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>;</div><div class="line">3: });</div><div class="line">4: <span class="comment">// print 10, 8, 6, 4, 2</span></div></div><p>Similarly, you can explicitly specify the partition size:</p>

<div class="fragment"><div class="line">1: taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(0, 10, 2, [] (<span class="keywordtype">int</span> i) {</div><div class="line">2: <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">"parallel on "</span> << i << <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>;</div><div class="line">3: }, 3);</div><div class="line">4: <span class="comment">// print 0, 2, 4, 6, 8 (three partitions {0, 2}, {4, 6}, {8})</span></div></div><p>By default, Cpp-Taskflow performs even partition across the number of available threads if no partition size is given.</p>

Example 1: Parallel Map</h1>

<p>This example demonstrates how to use <a class="el" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b" title="constructs a task dependency graph of range-based parallel_for ">tf::Taskflow::parallel_for</a> to create a parallel map pattern. The map operator modifies each item in the container to one if it is an odd number, or zero if it is an even number.</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">int</span> main() {</div><div class="line"> </div><div class="line"> <a class="code" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div><div class="line"> <a class="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><div class="line"></div><div class="line"> <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"></div><div class="line"> taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(items.begin(), items.end(), [] (<span class="keywordtype">int</span>& item) {</div><div class="line"> item = (item & 1) ? 1 : 0;</div><div class="line"> });</div><div class="line"></div><div class="line"> executor.<a class="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).get();</div><div class="line"></div><div class="line"> <span class="keywordflow">for</span>(<span class="keyword">auto</span> item : items) {</div><div class="line"> <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> << item << <span class="stringliteral">" "</span>;</div><div class="line"> }</div><div class="line"></div><div class="line"> <span class="keywordflow">return</span> 0;</div><div class="line">}</div></div><p>The program outputs the following:</p>

Example 2: Pipeline a Parallel For-loop</h1>

<p>This example demonstrates how to pipeline a parallel-for workload 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: <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/atomic/atomic.html">std::atomic<int></a> sum {0};</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">// create a 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 = 1;</div><div class="line">13: }</div><div class="line">14: }).name(<span class="stringliteral">"Create Items"</span>);</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#a644d7ff0f19ca155a2e7d56b1cdb3a0b">parallel_for</a>(items.begin(), items.end(), [&] (<span class="keywordtype">int</span> item) {</div><div class="line">17: sum.fetch_add(item, std::memory_order_relaxed);</div><div class="line">18: }, 8);</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">// create a output 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">"sum is: "</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>;</div><div class="line">22: }).name(<span class="stringliteral">"Print Sum"</span>);</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 precedes parallel-for</span></div><div class="line">25: T.<a class="code" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(T2); <span class="comment">// parallel-for precedes the output 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><div class="image">

</div>

<p>The output of this programs is:</p>

<div class="fragment"><div class="line">sum is: 1024</div></div><p>Debrief: </p><ul>

<li>Line 5 creates a taskflow object </li>

<li>Line 7 creates a vector of 1024 uninitialized integers </li>

<li>Line 8 creates an atomic integer variable </li>

<li>Line 10-14 creates a task that captures the vector to initialize all items to one </li>

<li>Line 16-18 sums up all items with each thread running on a partition of 1024/8=128 items </li>

<li>Line 20-22 creates a task that outputs the summation value </li>

<li>Line 24-25 pipelines the parallel-for workload with the two tasks </li>

<li>Line 27 dispatches the graph to threads and blocks until the execution completes </li>

</ul>

</div></div>

</div>

<ul>

<li class="footer">Generated by

</ul>

</div>

</body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

chapter3.html

Latest commit

History

chapter3.html

File metadata and controls