florian/mesytec-mnode
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
mesytec-mnode/external/taskflow-3.8.0/docs/TaskParallelPipelineWithTokenDependencies.html

299 lines
53 KiB
HTML
Raw Permalink Normal View History

add taskflow-3.8.0
2025-01-04 01:25:05 +01:00
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>Taskflow Algorithms &raquo; Task-parallel Pipeline with Token Dependencies | Taskflow QuickStart</title>
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Source+Sans+Pro:400,400i,600,600i%7CSource+Code+Pro:400,400i,600" />
<link rel="stylesheet" href="m-dark+documentation.compiled.css" />
<link rel="icon" href="favicon.ico" type="image/vnd.microsoft.icon" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="theme-color" content="#22272e" />
</head>
<body>
<header><nav id="navigation">
<div class="m-container">
<div class="m-row">
<span id="m-navbar-brand" class="m-col-t-8 m-col-m-none m-left-m">
<a href="https://taskflow.github.io"><img src="taskflow_logo.png" alt="" />Taskflow</a> <span class="m-breadcrumb">|</span> <a href="index.html" class="m-thin">QuickStart</a>
</span>
<div class="m-col-t-4 m-hide-m m-text-right m-nopadr">
<a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
<path id="m-doc-search-icon-path" d="m6 0c-3.31 0-6 2.69-6 6 0 3.31 2.69 6 6 6 1.49 0 2.85-0.541 3.89-1.44-0.0164 0.338 0.147 0.759 0.5 1.15l3.22 3.79c0.552 0.614 1.45 0.665 2 0.115 0.55-0.55 0.499-1.45-0.115-2l-3.79-3.22c-0.392-0.353-0.812-0.515-1.15-0.5 0.895-1.05 1.44-2.41 1.44-3.89 0-3.31-2.69-6-6-6zm0 1.56a4.44 4.44 0 0 1 4.44 4.44 4.44 4.44 0 0 1-4.44 4.44 4.44 4.44 0 0 1-4.44-4.44 4.44 4.44 0 0 1 4.44-4.44z"/>
</svg></a>
<a id="m-navbar-show" href="#navigation" title="Show navigation"></a>
<a id="m-navbar-hide" href="#" title="Hide navigation"></a>
</div>
<div id="m-navbar-collapse" class="m-col-t-12 m-show-m m-col-m-none m-right-m">
<div class="m-row">
<ol class="m-col-t-6 m-col-m-none">
<li><a href="pages.html">Handbook</a></li>
<li><a href="namespaces.html">Namespaces</a></li>
</ol>
<ol class="m-col-t-6 m-col-m-none" start="3">
<li><a href="annotated.html">Classes</a></li>
<li><a href="files.html">Files</a></li>
<li class="m-show-m"><a href="#search" class="m-doc-search-icon" title="Search" onclick="return showSearch()"><svg style="height: 0.9rem;" viewBox="0 0 16 16">
<use href="#m-doc-search-icon-path" />
</svg></a></li>
</ol>
</div>
</div>
</div>
</div>
</nav></header>
<main><article>
<div class="m-container m-container-inflatable">
<div class="m-row">
<div class="m-col-l-10 m-push-l-1">
<h1>
<span class="m-breadcrumb"><a href="Algorithms.html">Taskflow Algorithms</a> &raquo;</span>
Task-parallel Pipeline with Token Dependencies
</h1>
<nav class="m-block m-default">
<h3>Contents</h3>
<ul>
<li><a href="#DeferredPipelineTokenDependencies">Understand Token Dependencies</a></li>
<li><a href="#DeferredPipelineResolveTokenDependencies">Resolve Token Dependencies</a></li>
<li><a href="#DeferredPipelineIncludeHeaderFile">Include the Header</a></li>
<li><a href="#CreateADeferredPipelineModuleTask">Create a Deferred Pipeline Module Task</a></li>
<li><a href="#CreateADeferredScalablePipelineModuleTask">Create a Deferred Scalable Pipeline Module Task</a></li>
<li><a href="#ParalleliDeferredScalablePipelineLearnMore">Learn More about Taskflow Pipeline</a></li>
</ul>
</nav>
<p>Taskflow pipeline allows you to defer the execution of a token to future tokens. This deferral introduces a dependency from a future token to the current token, particularly suitable for many video encoding applications. We recommend reading <a href="TaskParallelPipeline.html" class="m-doc">Task-parallel Pipeline</a> first before learning this interface.</p><section id="DeferredPipelineTokenDependencies"><h2><a href="#DeferredPipelineTokenDependencies">Understand Token Dependencies</a></h2><p>Token dependencies establish the order in which data tokens should execute in a task-parallel pipeline. When token <code>t1</code> completes before <code>t2</code> starts, there is a dependency from <code>t1</code> to <code>t2</code>. We categorize token dependencies into two types:</p><ul><li>forward token dependencies (FTD): dependencies from earlier to future tokens</li><li>backward token dependencies (BTD): dependencies from future to earlier tokens The following figure illustrates a sample token dependency diagram and its token execution sequence. Edge pointing from token 2 to 5 is FTD, and those from 8 to 2 and 5 and 9 to 5 are BTDs. Based on the dependencies, the tokens execute in the corresponding execution sequence.</li></ul><img class="m-image" src="token_dependencies.png" alt="Image" style="width: 60%;" /></section><section id="DeferredPipelineResolveTokenDependencies"><h2><a href="#DeferredPipelineResolveTokenDependencies">Resolve Token Dependencies</a></h2><p>To resolve the token dependencies, the basic idea is to defer the execution of a token with unresolved dependencies and save the token in a data structure until its dependencies are resolved. To implement the idea, we leverage three data structures, deferred_tokens (DT), token_dependencies (TD), and ready_tokens (RT). DT and TD are associative containers and RT is a queue. DT stores deferred tokens and their dependents by which the deferred tokens are deferred. TD stores a dependent and its related deferred tokens. RT stores the tokens that were deferred tokens and now are ready because their dependencies are resolved. The following image illustrates the usages of the three data structures to resolve the token dependencies and get the corresponding serial execution sequence exemplified in <a href="#DeferredPipelineTokenDependencies" class="m-doc">Understand Token Dependencies</a>.</p><img class="m-image" src="deferred_three_data_structures.png" alt="Image" style="width: 90%;" /><p>The whole process has the following steps:</p><ol><li>Token 1 is not a deferred token and then 1 is finished. Now the execution sequence is {1}.</li><li>Token 2 defers to 8. We insert DT[2]={8} and TD[8]={2}. The black circle 2 in the above image illustrates this step.</li><li>Token 3 is not a deferred token and then 3 is finished. Now the execution sequence is {1,3}.</li><li>Token 4 is not a deferred token and then 4 is finished. Now the execution sequence is {1,3,4}.</li><li>Token 5 defers to 2 and 7. We insert DT[5]={2,7}, TD[2]={5}, and TD[7]={5}. The black circle 5 in the above image illustrates this step.</li><li>Token 6 is not a deferred token and then 6 is finished. Now the execution sequence is {1,3,4,6}.</li><li>Token 7 is not a deferred token and then 7 is finished. Now the execution sequence is {1,3,4,6,7}. Since TD[7]={5}, we directly remove 7 from DT[5]. The black circle 7 in the above image illustrates this step.</li><li>Token 8 is not a deferred token and then 8 is finished. Now the execution sequence is {1,3,4,6,7,8}. Since TD[8]={2}, we directly remove 8 from DT[2] and find out DT[2] is empty. Now token 2 is no longer a deferred token and we move 2 to RT. The black circle 8 in the above image illustrates this step.</li><li>RT is not empty and has a token 2. Then we finish running 2. Now the execution sequence is {1,3,4,6,7,8,2}. Since TD[2]={5}, we directly remove 2 from DT[5] and find out DT[5] is empty. Now token 5 is no longer a deferred token and we move 5 to RT. The black circle 9 in the above image illustrates this step.</li><li>RT is not empty and has a token
<span class="w"> </span><span class="mi">2</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Executor</span><span class="w"> </span><span class="n">executor</span><span class="p">;</span>
<span class="w"> </span><span class="mi">3</span><span class="o">:</span>
<span class="w"> </span><span class="mi">4</span><span class="o">:</span><span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="kt">size_t</span><span class="w"> </span><span class="n">num_lines</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">4</span><span class="p">;</span>
<span class="w"> </span><span class="mi">5</span><span class="o">:</span>
<span class="w"> </span><span class="mi">6</span><span class="o">:</span><span class="w"> </span><span class="c1">// the pipeline consists of three pipes (serial-serial-serial)</span>
<span class="w"> </span><span class="mi">7</span><span class="o">:</span><span class="w"> </span><span class="c1">// and up to four concurrent scheduling tokens</span>
<span class="w"> </span><span class="mi">8</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeline</span><span class="w"> </span><span class="n">pl</span><span class="p">(</span><span class="n">num_lines</span><span class="p">,</span>
<span class="w"> </span><span class="mi">9</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Pipe</span><span class="p">{</span><span class="n">tf</span><span class="o">::</span><span class="n">PipeType</span><span class="o">::</span><span class="n">SERIAL</span><span class="p">,</span><span class="w"> </span><span class="p">[](</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="w"> </span><span class="n">pf</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">10</span><span class="o">:</span><span class="w"> </span><span class="c1">// stop at 11 scheduling tokens</span>
<span class="mi">11</span><span class="o">:</span><span class="w"> </span><span class="k">if</span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">11</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">12</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">stop</span><span class="p">();</span>
<span class="mi">13</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">14</span><span class="o">:</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span>
<span class="mi">15</span><span class="o">:</span><span class="w"> </span><span class="c1">// Token 5 is deferred</span>
<span class="mi">16</span><span class="o">:</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">5</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">17</span><span class="o">:</span><span class="w"> </span><span class="k">switch</span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">num_deferrals</span><span class="p">())</span><span class="w"> </span><span class="p">{</span>
<span class="mi">18</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">0</span><span class="o">:</span>
<span class="mi">19</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span>
<span class="mi">20</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;1st-time: Token %zu is deferred by 2</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">21</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">7</span><span class="p">);</span>
<span class="mi">22</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;1st-time: Token %zu is deferred by 7</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">23</span><span class="o">:</span><span class="w"> </span><span class="k">return</span><span class="p">;</span><span class="w"> </span>
<span class="mi">24</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">25</span><span class="o">:</span>
<span class="mi">26</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">1</span><span class="o">:</span>
<span class="mi">27</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">9</span><span class="p">);</span>
<span class="mi">28</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;2nd-time: Token %zu is deferred by 9</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">29</span><span class="o">:</span><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<span class="mi">30</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">31</span><span class="o">:</span>
<span class="mi">32</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">2</span><span class="o">:</span>
<span class="mi">33</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;3rd-time: Tokens 2, 7 and 9 resolved dependencies \</span>
<span class="s"> for token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">34</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">35</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">36</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">37</span><span class="o">:</span><span class="w"> </span><span class="c1">// token 2 is deferred</span>
<span class="mi">38</span><span class="o">:</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">39</span><span class="o">:</span><span class="w"> </span><span class="k">switch</span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">num_deferrals</span><span class="p">())</span><span class="w"> </span><span class="p">{</span>
<span class="mi">40</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">0</span><span class="o">:</span>
<span class="mi">41</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">8</span><span class="p">);</span>
<span class="mi">42</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;1st-time: Token %zu is deferred by 8</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">43</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">44</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">1</span><span class="o">:</span>
<span class="mi">45</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;2nd-time: Token 8 resolved dependencies for token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span>
<span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">46</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">47</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">48</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">49</span><span class="o">:</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span>
<span class="mi">50</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;stage 1: Non-deferred token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">51</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">52</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">53</span><span class="o">:</span><span class="w"> </span><span class="p">}},</span>
<span class="mi">54</span><span class="o">:</span>
<span class="mi">55</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Pipe</span><span class="p">{</span><span class="n">tf</span><span class="o">::</span><span class="n">PipeType</span><span class="o">::</span><span class="n">SERIAL</span><span class="p">,</span><span class="w"> </span><span class="p">[](</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="w"> </span><span class="n">pf</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">56</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;stage 2: input token %zu (deferrals=%zu)</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span>
<span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">(),</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">num_deferrals</span><span class="p">());</span>
<span class="mi">57</span><span class="o">:</span><span class="w"> </span><span class="p">}},</span>
<span class="mi">58</span><span class="o">:</span>
<span class="mi">59</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Pipe</span><span class="p">{</span><span class="n">tf</span><span class="o">::</span><span class="n">PipeType</span><span class="o">::</span><span class="n">SERIAL</span><span class="p">,</span><span class="w"> </span><span class="p">[](</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="w"> </span><span class="n">pf</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">60</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;stage 3: input token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">61</span><span class="o">:</span><span class="w"> </span><span class="p">}}</span>
<span class="mi">62</span><span class="o">:</span><span class="w"> </span><span class="p">);</span>
<span class="mi">63</span><span class="o">:</span><span class="w"> </span>
<span class="mi">64</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">task</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">composed_of</span><span class="p">(</span><span class="n">pl</span><span class="p">);</span>
<span class="mi">65</span><span class="o">:</span>
<span class="mi">66</span><span class="o">:</span><span class="w"> </span><span class="c1">// run the pipeline</span>
<span class="mi">67</span><span class="o">:</span><span class="w"> </span><span class="n">executor</span><span class="p">.</span><span class="n">run</span><span class="p">(</span><span class="n">taskflow</span><span class="p">).</span><span class="n">wait</span><span class="p">();</span></pre><p>Debrief:</p><ul><li>Line 8 defines the number of lines in the pipeline</li><li>Lines 9-52 define the first serial pipe, which will stop the pipeline scheduling at the 11th token</li><li>Lines 15-30 define the token dependencies for token 5</li><li>Lines 37-48 define the token dependencies for token 2</li><li>Lines 55-57 define the second serial pipe</li><li>Lines 59-61 define the third serial pipe</li><li>Line 64 defines the pipeline taskflow graph using composition</li><li>Line 67 executes the taskflow</li></ul><p>The following is one of the possible outcomes of the example.</p><pre class="m-code">stage <span class="m">1</span>: Non-deferred token <span class="m">0</span>
stage <span class="m">2</span>: input token <span class="m">0</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">0</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">1</span>
stage <span class="m">2</span>: input token <span class="m">1</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">1</span>
1st-time: Token <span class="m">2</span> is deferred by <span class="m">8</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">3</span>
stage <span class="m">2</span>: input token <span class="m">3</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">3</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">4</span>
stage <span class="m">2</span>: input token <span class="m">4</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">4</span>
1st-time: Token <span class="m">5</span> is deferred by <span class="m">2</span>
1st-time: Token <span class="m">5</span> is deferred by <span class="m">7</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">6</span>
stage <span class="m">2</span>: input token <span class="m">6</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">7</span>
stage <span class="m">2</span>: input token <span class="m">7</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">8</span>
stage <span class="m">3</span>: input token <span class="m">6</span>
stage <span class="m">3</span>: input token <span class="m">7</span>
stage <span class="m">2</span>: input token <span class="m">8</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">8</span>
2nd-time: Token <span class="m">8</span> resolved dependencies <span class="k">for</span> token <span class="m">2</span>
stage <span class="m">2</span>: input token <span class="m">2</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">1</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">2</span>
2nd-time: Token <span class="m">5</span> is deferred by <span class="m">9</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">9</span>
stage <span class="m">2</span>: input token <span class="m">9</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">9</span>
3rd-time: Tokens <span class="m">2</span>, <span class="m">7</span> and <span class="m">9</span> resolved dependencies <span class="k">for</span> token <span class="m">5</span>
stage <span class="m">2</span>: input token <span class="m">5</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">2</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">5</span>
stage <span class="m">1</span>: Non-deferred token <span class="m">10</span>
stage <span class="m">2</span>: input token <span class="m">10</span> <span class="o">(</span><span class="nv">deferrals</span><span class="o">=</span><span class="m">0</span><span class="o">)</span>
stage <span class="m">3</span>: input token <span class="m">10</span></pre><aside class="m-note m-info"><h4>Note</h4><p>You can only specify the token dependencies at the first pipe to get the serial execution of tokens.</p></aside></section><section id="CreateADeferredScalablePipelineModuleTask"><h2><a href="#CreateADeferredScalablePipelineModuleTask">Create a Deferred Scalable Pipeline Module Task</a></h2><p>In addition to task-parallel pipeline (<a href="classtf_1_1Pipeline.html" class="m-doc">tf::<wbr />Pipeline</a>), you can specify token dependencies on top of a task-parallel scalable pipeline (<a href="classtf_1_1ScalablePipeline.html" class="m-doc">tf::<wbr />ScalablePipeline</a>). We recommend reading <a href="TaskParallelScalablePipeline.html" class="m-doc">Task-parallel Scalable Pipeline</a> first before learning this interface.</p><p>To create a deferred scalable pipeline application, there are four steps, which are identical to the steps described in <a href="#CreateADeferredPipelineModuleTask" class="m-doc">Create a Deferred Pipeline Module Task</a>. They are:</p><ol><li>Define the pipeline structure (e.g., pipe type, pipe callable, stopping rule, line count)</li><li>Define the token dependencies <strong>at the first pipe</strong></li><li>Define the data storage and layout, if needed for the application</li><li>Define the pipeline taskflow graph using composition</li></ol><p>The following code creates a deferred scalable pipeline that uses four parallel lines to schedule tokens through two serial pipes in the given vector, then resetting that pipeline to three serial pipes. The three pipe callables are identical to the pipe callables demonstrated in the code snippet in <a href="#CreateADeferredPipelineModuleTask" class="m-doc">Create a Deferred Pipeline Module Task</a>. The token dependencies are exemplified in <a href="#DeferredPipelineTokenDependencies" class="m-doc">Understand Token Dependencies</a>.</p><pre class="m-code"><span class="w"> </span><span class="mi">1</span><span class="o">:</span><span class="w"> </span><span class="c1">// create a vector of three pipes</span>
<span class="w"> </span><span class="mi">2</span><span class="o">:</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o">&lt;</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Pipe</span><span class="o">&lt;</span><span class="n">std</span><span class="o">::</span><span class="n">function</span><span class="o">&lt;</span><span class="kt">void</span><span class="p">(</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="p">)</span><span class="o">&gt;&gt;</span><span class="w"> </span><span class="o">&gt;</span><span class="w"> </span><span class="n">pipes</span><span class="p">;</span>
<span class="w"> </span><span class="mi">3</span><span class="o">:</span><span class="w"> </span>
<span class="w"> </span><span class="mi">4</span><span class="o">:</span><span class="w"> </span><span class="c1">// define pipe callables</span>
<span class="w"> </span><span class="mi">5</span><span class="o">:</span><span class="w"> </span><span class="c1">// first_pipe_callable is same as lines 15-53 in the above code snippet </span>
<span class="w"> </span><span class="mi">6</span><span class="o">:</span><span class="w"> </span><span class="k">auto</span><span class="w"> </span><span class="n">first_pipe_callable</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">[](</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="w"> </span><span class="n">pf</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="mi">7</span><span class="o">:</span><span class="w"> </span><span class="c1">// stop at 11 scheduling tokens</span>
<span class="w"> </span><span class="mi">8</span><span class="o">:</span><span class="w"> </span><span class="k">if</span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">11</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="w"> </span><span class="mi">9</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">stop</span><span class="p">();</span>
<span class="mi">10</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">11</span><span class="o">:</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span>
<span class="mi">12</span><span class="o">:</span><span class="w"> </span><span class="c1">// Token 5 is deferred</span>
<span class="mi">13</span><span class="o">:</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">5</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">14</span><span class="o">:</span><span class="w"> </span><span class="k">switch</span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">num_deferrals</span><span class="p">())</span><span class="w"> </span><span class="p">{</span>
<span class="mi">15</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">0</span><span class="o">:</span>
<span class="mi">16</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span>
<span class="mi">17</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;1st-time: Token %zu is deferred by 2</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">18</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">7</span><span class="p">);</span>
<span class="mi">19</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;1st-time: Token %zu is deferred by 7</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">20</span><span class="o">:</span><span class="w"> </span><span class="k">return</span><span class="p">;</span><span class="w"> </span>
<span class="mi">21</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">22</span><span class="o">:</span>
<span class="mi">23</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">1</span><span class="o">:</span>
<span class="mi">24</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">9</span><span class="p">);</span>
<span class="mi">25</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;2nd-time: Token %zu is deferred by 9</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">26</span><span class="o">:</span><span class="w"> </span><span class="k">return</span><span class="p">;</span>
<span class="mi">27</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">28</span><span class="o">:</span>
<span class="mi">29</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">2</span><span class="o">:</span>
<span class="mi">30</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;3rd-time: Tokens 2, 7 and 9 resolved dependencies for token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span>
<span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">31</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">32</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">33</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">34</span><span class="o">:</span><span class="w"> </span><span class="c1">// token 2 is deferred</span>
<span class="mi">35</span><span class="o">:</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">()</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="mi">2</span><span class="p">)</span><span class="w"> </span><span class="p">{</span>
<span class="mi">36</span><span class="o">:</span><span class="w"> </span><span class="k">switch</span><span class="p">(</span><span class="n">pf</span><span class="p">.</span><span class="n">num_deferrals</span><span class="p">())</span><span class="w"> </span><span class="p">{</span>
<span class="mi">37</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">0</span><span class="o">:</span>
<span class="mi">38</span><span class="o">:</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">defer</span><span class="p">(</span><span class="mi">8</span><span class="p">);</span>
<span class="mi">39</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;1st-time: Token %zu is deferred by 8</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">40</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">41</span><span class="o">:</span><span class="w"> </span><span class="k">case</span><span class="w"> </span><span class="mi">1</span><span class="o">:</span>
<span class="mi">42</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;2nd-time: Token 8 resolved dependencies for token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span>
<span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">43</span><span class="o">:</span><span class="w"> </span><span class="k">break</span><span class="p">;</span>
<span class="mi">44</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">45</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">46</span><span class="o">:</span><span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="p">{</span>
<span class="mi">47</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;stage 1: Non-deferred token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">48</span><span class="o">:</span><span class="w"> </span><span class="p">}</span>
<span class="mi">49</span><span class="o">:</span><span class="w"> </span><span class="p">};</span>
<span class="mi">50</span><span class="o">:</span>
<span class="mi">51</span><span class="o">:</span><span class="w"> </span><span class="c1">// second_pipe_callable is same as lines 55-57 in the above code snippet</span>
<span class="mi">52</span><span class="o">:</span><span class="w"> </span><span class="k">auto</span><span class="w"> </span><span class="n">second_pipe_callable</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">[](</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="w"> </span><span class="n">pf</span><span class="p">){</span>
<span class="mi">53</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;stage 2: input token %zu (deferrals=%zu)</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span>
<span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">(),</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">num_deferrals</span><span class="p">());</span>
<span class="mi">54</span><span class="o">:</span><span class="w"> </span><span class="p">};</span>
<span class="mi">55</span><span class="o">:</span>
<span class="mi">56</span><span class="o">:</span><span class="w"> </span><span class="c1">// third_pipe_callable is same as lines 59-61 in the above code snippet</span>
<span class="mi">57</span><span class="o">:</span><span class="w"> </span><span class="k">auto</span><span class="w"> </span><span class="n">third_pipe_callable</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">[](</span><span class="n">tf</span><span class="o">::</span><span class="n">Pipeflow</span><span class="o">&amp;</span><span class="w"> </span><span class="n">pf</span><span class="p">){</span>
<span class="mi">58</span><span class="o">:</span><span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">&quot;stage 3: input token %zu</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="w"> </span><span class="n">pf</span><span class="p">.</span><span class="n">token</span><span class="p">());</span>
<span class="mi">59</span><span class="o">:</span><span class="w"> </span><span class="p">};</span>
<span class="mi">60</span><span class="o">:</span>
<span class="mi">61</span><span class="o">:</span><span class="w"> </span><span class="n">pipes</span><span class="p">.</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">tf</span><span class="o">::</span><span class="n">PipeType</span><span class="o">::</span><span class="n">SERIAL</span><span class="p">,</span><span class="w"> </span><span class="n">first_pipe_callable</span><span class="p">);</span>
<span class="mi">62</span><span class="o">:</span><span class="w"> </span><span class="n">pipes</span><span class="p">.</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">tf</span><span class="o">::</span><span class="n">PipeType</span><span class="o">::</span><span class="n">SERIAL</span><span class="p">,</span><span class="w"> </span><span class="n">second_pipe_callable</span><span class="p">);</span><span class="w"> </span>
<span class="mi">63</span><span class="o">:</span>
<span class="mi">64</span><span class="o">:</span><span class="w"> </span><span class="c1">// create a pipeline of four parallel lines based on the given vector of pipes</span>
<span class="mi">65</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">ScalablePipeline</span><span class="w"> </span><span class="n">pl</span><span class="p">(</span><span class="mi">4</span><span class="p">,</span><span class="w"> </span><span class="n">pipes</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">pipes</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
<span class="mi">66</span><span class="o">:</span>
<span class="mi">67</span><span class="o">:</span><span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">Task</span><span class="w"> </span><span class="n">task</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">taskflow</span><span class="p">.</span><span class="n">composed_of</span><span class="p">(</span><span class="n">pl</span><span class="p">);</span>
<span class="mi">68</span><span class="o">:</span><span class="w"> </span>
<span class="mi">69</span><span class="o">:</span><span class="w"> </span><span class="c1">// run the pipeline</span>
<span class="mi">70</span><span class="o">:</span><span class="w"> </span><span class="n">executor</span><span class="p">.</span><span class="n">run</span><span class="p">(</span><span class="n">taskflow</span><span class="p">).</span><span class="n">wait</span><span class="p">();</span>
<span class="mi">71</span><span class="o">:</span>
<span class="mi">72</span><span class="o">:</span><span class="w"> </span><span class="c1">// reset the pipeline to a new range of three pipes and starts from</span>
<span class="mi">73</span><span class="o">:</span><span class="w"> </span><span class="c1">// the initial state (i.e., token counts from zero)</span>
<span class="mi">74</span><span class="o">:</span><span class="w"> </span><span class="n">pipes</span><span class="p">.</span><span class="n">emplace_back</span><span class="p">(</span><span class="n">tf</span><span class="o">::</span><span class="n">PipeType</span><span class="o">::</span><span class="n">SERIAL</span><span class="p">,</span><span class="w"> </span><span class="n">third_pipe_callable</span><span class="p">);</span>
<span class="mi">75</span><span class="o">:</span><span class="w"> </span><span class="n">pl</span><span class="p">.</span><span class="n">reset</span><span class="p">(</span><span class="n">pipes</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">pipes</span><span class="p">.</span><span class="n">end</span><span class="p">());</span>
<span class="mi">76</span><span class="o">:</span>
<span class="mi">77</span><span class="o">:</span><span class="w"> </span><span class="n">executor</span><span class="p">.</span><span class="n">run</span><span class="p">(</span><span class="n">taskflow</span><span class="p">).</span><span class="n">wait</span><span class="p">();</span></pre><p>Debrief:</p><ul><li>Lines 2 defines the vector of <a href="classtf_1_1Pipe.html" class="m-doc">tf::<wbr />Pipe</a> type</li><li>Lines 6-49 define the first pipe callable</li><li>Lines 52-54 define the second pipe callable</li><li>Lines 57-59 define the third pipe callable</li><li>Lines 61-62 define the vector of two pipe callables</li><li>Line 65 defines the scalable pipeline</li><li>Line 67 defines the pipeline taskflow graph using composition</li><li>Line 70 executes the taskflow for the first run</li><li>Line 74 inserts the third pipe callable in the vector</li><li>Line 75 resets the pipes to three pipe callables</li><li>Line 77 executes the taskflow for the second run</li></ul></section><section id="ParalleliDeferredScalablePipelineLearnMore"><h2><a href="#ParalleliDeferredScalablePipelineLearnMore">Learn More about Taskflow Pipeline</a></h2><p>Visit the following pages to learn more about pipeline:</p><ul><li><a href="TaskParallelPipeline.html" class="m-doc">Task-parallel Pipeline</a></li><li><a href="DataParallelPipeline.html" class="m-doc">Data-parallel Pipeline</a></li><li><a href="TaskParallelScalablePipeline.html" class="m-doc">Task-parallel Scalable Pipeline</a></li><li><a href="TextProcessingPipeline.html" class="m-doc">Text Processing Pipeline</a></li><li><a href="GraphProcessingPipeline.html" class="m-doc">Graph Processing Pipeline</a></li><li><a href="TaskflowProcessingPipeline.html" class="m-doc">Taskflow Processing Pipeline</a></li></ul></section>
</div>
</div>
</div>
</article></main>
<div class="m-doc-search" id="search">
<a href="#!" onclick="return hideSearch()"></a>
<div class="m-container">
<div class="m-row">
<div class="m-col-m-8 m-push-m-2">
<div class="m-doc-search-header m-text m-small">
<div><span class="m-label m-default">Tab</span> / <span class="m-label m-default">T</span> to search, <span class="m-label m-default">Esc</span> to close</div>
<div id="search-symbolcount">&hellip;</div>
</div>
<div class="m-doc-search-content">
<form>
<input type="search" name="q" id="search-input" placeholder="Loading &hellip;" disabled="disabled" autofocus="autofocus" autocomplete="off" spellcheck="false" />
</form>
<noscript class="m-text m-danger m-text-center">Unlike everything else in the docs, the search functionality <em>requires</em> JavaScript.</noscript>
<div id="search-help" class="m-text m-dim m-text-center">
<p class="m-noindent">Search for symbols, directories, files, pages or
modules. You can omit any prefix from the symbol or file path; adding a
<code>:</code> or <code>/</code> suffix lists all members of given symbol or
directory.</p>
<p class="m-noindent">Use <span class="m-label m-dim">&darr;</span>
/ <span class="m-label m-dim">&uarr;</span> to navigate through the list,
<span class="m-label m-dim">Enter</span> to go.
<span class="m-label m-dim">Tab</span> autocompletes common prefix, you can
copy a link to the result using <span class="m-label m-dim">⌘</span>
<span class="m-label m-dim">L</span> while <span class="m-label m-dim">⌘</span>
<span class="m-label m-dim">M</span> produces a Markdown link.</p>
</div>
<div id="search-notfound" class="m-text m-warning m-text-center">Sorry, nothing was found.</div>
<ul id="search-results"></ul>
</div>
</div>
</div>
</div>
</div>
<script src="search-v2.js"></script>
<script src="searchdata-v2.js" async="async"></script>
<footer><nav>
<div class="m-container">
<div class="m-row">
<div class="m-col-l-10 m-push-l-1">
<p>Taskflow handbook is part of the <a href="https://taskflow.github.io">Taskflow project</a>, copyright © <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>, 2018&ndash;2024.<br />Generated by <a href="https://doxygen.org/">Doxygen</a> 1.9.1 and <a href="https://mcss.mosra.cz/">m.css</a>.</p>
</div>
</div>
</div>
</nav></footer>
</body>
</html>
Reference in a new issue Copy permalink