<!-- 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.14"/><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">/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */$(document).ready(initResizable);/* @license-end */</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" /></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.4-master-branch</span></div></td></tr></tbody></table></div><!-- end header part --><!-- Generated by Doxygen 1.8.14 --><script type="text/javascript">/* @license magnet:?xt=urn:btih:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */var searchBox = new SearchBox("searchBox", "search",false,'Search');/* @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:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */$(function() {initMenu('',true,false,'search.php','Search');$(document).ready(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:cf05388f2679ee054f2beb29a391d25f4e673ac3&dn=gpl-2.0.txt GPL-v2 */$(document).ready(function(){initNavTree('wavefront.html','');});/* @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"><iframe src="javascript:void(0)" frameborder="0"name="MSearchResults" id="MSearchResults"></iframe></div><div class="header"><div class="headertitle"><div class="title">Wavefront Parallelism </div> </div></div><!--header--><div class="contents"><div class="textblock"><p>We study the wavefront parallelism, which is a common pattern in dynamic programming to sweep elements in a diagonal direction.</p><h1><a class="anchor" id="WavefrontComputingFormulation"></a>Problem Formulation</h1><p>The computation starts at a singular point at a corner of a data plan (e.g., grid) and propagates its effect diagonally to other elements. This sweep of computation is known as <em>wavefront</em>. Each point in the wavefront can be computed in parallel. The following example shows a wavefront parallelism in a 2D matrix.</p><div class="image"><img src="wavefront_1.png" alt="wavefront_1.png" width="50%"/></div><p>We partition the 9x9 grid into a 3x3 block and assign a task to one block. The wavefront propagates task dependencies from the top-left block all the way to the bottom-right block. Each task precedes two tasks, one to the right and another below.</p><h1><a class="anchor" id="WavefrontTaskGraph"></a>Wavefront Task Graph</h1><p>We can describe the wavefront parallelism in a simple two-level loop. Since we need to address the two tasks upper and left to a task when creating its dependencies, we use a 2D vector to pre-allocate all tasks via <a class="el" href="classtf_1_1FlowBuilder.html#acab0b4ac82260f47fdb36a3244ee3aaf" title="creates an empty task ">tf::Taskflow::placeholder</a>.</p><div class="fragment"><div class="line"><span class="keywordtype">void</span> wavefront() {</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="/Users/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<std::vector<tf::Task></a>> node(num_blocks);</div><div class="line"> </div><div class="line"> <span class="comment">// create num_blocks*num_blocks placeholder tasks</span></div><div class="line"> <span class="keywordflow">for</span>(<span class="keyword">auto</span> &n : node){</div><div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i=0; i<num_blocks; i++){</div><div class="line"> n.emplace_back(taskflow.<a class="code" href="classtf_1_1FlowBuilder.html#acab0b4ac82260f47fdb36a3244ee3aaf">placeholder</a>());</div><div class="line"> } </div><div class="line"> }</div><div class="line"> </div><div class="line"> <span class="comment">// scan each block and create dependencies</span></div><div class="line"> <span class="keywordflow">for</span>( <span class="keywordtype">int</span> i=num_blocks; --i>=0; ) { </div><div class="line"> <span class="keywordflow">for</span>( <span class="keywordtype">int</span> j=num_blocks; --j>=0; ) { </div><div class="line"> <span class="comment">// deferred task assignment</span></div><div class="line"> node[i][j].work([=]() { block_computation(i, j); }); </div><div class="line"> </div><div class="line"> <span class="comment">// wavefront dependency</span></div><div class="line"> <span class="keywordflow">if</span>(j+1 < num_blocks) node[i][j].precede(node[i][j+1]);</div><div class="line"> <span class="keywordflow">if</span>(i+1 < num_blocks) node[i][j].precede(node[i+1][j]);</div><div class="line"> } </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).wait();</div><div class="line"></div><div class="line"> <span class="comment">// dump the taskflow</span></div><div class="line"> taskflow.<a class="code" href="classtf_1_1Taskflow.html#ac433018262e44b12c4cc9f0c4748d758">dump</a>(<a class="codeRef" doxygen="/Users/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>);</div><div class="line">}</div></div><!-- fragment --><p>The taskflow below depicts the wavefront parallelism in a 3x3 grid.</p><div class="image"><object type="image/svg+xml" data="wavefront_2.svg" width="80%">wavefront_2.svg</object></div><p>Wavefront parallelism has many variations in different applications, for instance, Smith-Waterman sequencing, video encoding algorithms, and image analysis. The key parallel pattern is to traverse data in a diagonal direction. </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="navelem"><a class="el" href="Examples.html">Learning from Examples</a></li><li class="footer">Generated by<a href="http://www.doxygen.org/index.html"><img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.14 </li></ul></div></body></html>
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。