<!-- iframe showing the search results (closed by default) -->
<divid="MSearchResultsWindow">
<iframesrc="javascript:void(0)" frameborder="0"
name="MSearchResults" id="MSearchResults">
</iframe>
</div>
<divclass="header">
<divclass="headertitle">
<divclass="title">C4: Create a Parallel Reduction Graph </div></div>
</div><!--header-->
<divclass="contents">
<divclass="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>
<p><aclass="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>
<p><aclass="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><aclass="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. <aclass="el" href="classtf_1_1Taskflow.html" title="the class to create a task dependency graph ">Taskflow</a> provides a method, <aclass="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>
<divclass="fragment"><divclass="line"> 1: <aclass="codeRef" doxygen="/home/twhuang/PhD/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 = <spanclass="stringliteral">"12345678"</span>;</div><divclass="line"> 2: <spanclass="keywordtype">int</span> sum {0};</div><divclass="line"> 3:</div><divclass="line"> 4: <spanclass="keyword">auto</span> [S, T] = taskflow.<aclass="code" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef">transform_reduce</a>(str.begin(), str.end(), sum,</div><divclass="line"> 5: [] (<spanclass="keywordtype">int</span> a, <spanclass="keywordtype">int</span> b) {</div><divclass="line"> 6: <spanclass="keywordflow">return</span> a + b;</div><divclass="line"> 7: }, </div><divclass="line"> 8: [] (<spanclass="keywordtype">char</span> c) -> <spanclass="keywordtype">int</span> {</div><divclass="line"> 9: <spanclass="keywordflow">return</span> c - <spanclass="charliteral">'0'</span>;</div><divclass="line">10: } </div><divclass="line">11: ); </div><divclass="line">12:</div><divclass="line">13: <spanclass="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><aclass="el" href="classtf_1_1Taskflow.html" title="the class to create a task dependency graph ">Taskflow</a> has another overload <aclass="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>
<divclass="fragment"><divclass="line"> 1: <aclass="codeRef" doxygen="/home/twhuang/PhD/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 = <spanclass="stringliteral">"12345678"</span>;</div><divclass="line"> 2:</div><divclass="line"> 3: <spanclass="keywordtype">double</span> sum {0};</div><divclass="line"> 4:</div><divclass="line"> 5: <spanclass="keyword">auto</span> [S, T] = taskflow.<aclass="code" href="classtf_1_1FlowBuilder.html#a08d669f2286cb90fd5ba7dade1e93fef">transform_reduce</a>(str.begin(), str.end(), sum,</div><divclass="line"> 6: [] (<spanclass="keywordtype">double</span> a, <spanclass="keywordtype">double</span> b) {</div><divclass="line"> 7: <spanclass="keywordflow">return</span> a + b;</div><divclass="line"> 8: }, </div><divclass="line"> 9: [] (<spanclass="keywordtype">double</span> a, <spanclass="keywordtype">char</span> c) -> <spanclass="keywordtype">double</span> {</div><divclass="line">10: <spanclass="keywordflow">return</span> a + (c - <spanclass="charliteral">'0'</span>);</div><divclass="line">11: }, </div><divclass="line">12: [] (<spanclass="keywordtype">char</span> c) -> <spanclass="keywordtype">double</span> {</div><divclass="line">13: <spanclass="keywordflow">return</span><spanclass="keyword">static_cast<</span><spanclass="keywordtype">double</span><spanclass="keyword">></span>(c - <spanclass="charliteral">'0'</span>);</div><divclass="line">14: } </div><divclass="line">15: ); </div><divclass="line">16:</div><divclass="line">17: <spanclass="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><aclass="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 <aclass="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>
<divclass="fragment"><divclass="line"> 1: #include <taskflow/taskflow.hpp></div><divclass="line"> 2:</div><divclass="line"> 3: <spanclass="keywordtype">int</span> main() {</div><divclass="line"> 4:</div><divclass="line"> 5: <aclass="code" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div><divclass="line"> 6:</div><divclass="line"> 7: <aclass="codeRef" doxygen="/home/twhuang/PhD/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><divclass="line"> 8: <spanclass="keywordtype">int</span><aclass="codeRef" doxygen="/home/twhuang/PhD/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> = <aclass="codeRef" doxygen="/home/twhuang/PhD/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><divclass="line"> 9:</div><divclass="line">10: taskflow.<aclass="code" href="classtf_1_1FlowBuilder.html#a06b06b57f8ec8bb060951fc71dd375fb">reduce</a>(items.begin(), items.end(), min, [] (<spanclass="keywordtype">int</span> a, <spanclass="keywordtype">int</span> b) {</div><divclass="line">11: <spanclass="keywordflow">return</span><aclass="codeRef" doxygen="/home/twhuang/PhD/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><divclass="line">12: });</div><divclass="line">13:</div><divclass="line">14: <aclass="code" href="classtf_1_1Executor.html">tf::Executor</a>().<aclass="code" href="classtf_1_1Executor.html#a81f35d5b0a20ac0646447eb80d97c0aa">run</a>(taskflow).get();</div><divclass="line">15:</div><divclass="line">16: <aclass="codeRef" doxygen="/home/twhuang/PhD/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; <spanclass="comment">// 1</span></div><divclass="line">17:</div><divclass="line">18: <spanclass="keywordflow">return</span> 0;</div><divclass="line">19: }</div></div><!-- fragment --><p>Similarly, the example below finds the maximum element in a data set.</p>
<p>The <aclass="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>
<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><aclass="anchor" id="Chapter4Example3"></a>
Example 3: Find the Minimum L1-norm</h1>
<p>The example below applies the method <aclass="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>