Skip to content
Navigation Menu
{{ message }}
forked from taskflow/taskflow
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPartitioningAlgorithm.html
More file actions
145 lines (142 loc) · 19.9 KB
/
Copy pathPartitioningAlgorithm.html
File metadata and controls
145 lines (142 loc) · 19.9 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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>Taskflow Algorithms » Partitioning Algorithm | 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> »</span>
Partitioning Algorithm
</h1>
<nav class="m-block m-default">
<h3>Contents</h3>
<ul>
<li><a href="#DefineAPartitionerForParallelAlgorithms">Define a Partitioner for Parallel Algorithms</a></li>
<li><a href="#DefineAStaticPartitioner">Define a Static Partitioner</a></li>
<li><a href="#DefineADynamicPartitioner">Define a Dynamic Partitioner</a></li>
<li><a href="#DefineAGuidedPartitioner">Define a Guided Partitioner</a></li>
<li><a href="#DefineAClosureWrapperForAPartitioner">Define a Closure Wrapper for a Partitioner</a></li>
</ul>
</nav>
<p>A partitioning algorithm allows applications to optimize parallel algorithms using different scheduling methods, such as static partitioning, dynamic partitioning, and guided partitioning.</p><section id="DefineAPartitionerForParallelAlgorithms"><h2><a href="#DefineAPartitionerForParallelAlgorithms">Define a Partitioner for Parallel Algorithms</a></h2><p>A partitioner defines how to partition and distribute iterations to different workers when running parallel algorithms in Taskflow, such as <a href="classtf_1_1FlowBuilder.html#aae3edfa278baa75b08414e083c14c836" class="m-doc">tf::<wbr />Taskflow::<wbr />for_each</a> and <a href="classtf_1_1FlowBuilder.html#a97be7ceef6fa4276e3b074c10c13b826" class="m-doc">tf::<wbr />Taskflow::<wbr />transform</a>. The following example shows how to create parallel-iteration tasks with different execution policies:</p><pre class="m-code"><span class="n">std</span><span class="o">::</span><span class="n">vector</span><span class="o"><</span><span class="kt">int</span><span class="o">></span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="p">{</span><span class="mi">1</span><span class="p">,</span><span class="w"> </span><span class="mi">2</span><span class="p">,</span><span class="w"> </span><span class="mi">3</span><span class="p">,</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="p">,</span><span class="w"> </span><span class="mi">6</span><span class="p">,</span><span class="w"> </span><span class="mi">7</span><span class="p">,</span><span class="w"> </span><span class="mi">8</span><span class="p">,</span><span class="w"> </span><span class="mi">9</span><span class="p">,</span><span class="w"> </span><span class="mi">10</span><span class="p">}</span><span class="w"></span>
<span class="c1">// create different partitioners</span>
<span class="n">tf</span><span class="o">::</span><span class="n">GuidedPartitioner</span><span class="w"> </span><span class="n">guided_partitioner</span><span class="p">;</span><span class="w"></span>
<span class="n">tf</span><span class="o">::</span><span class="n">StaticPartitioner</span><span class="w"> </span><span class="n">static_partitioner</span><span class="p">;</span><span class="w"></span>
<span class="n">tf</span><span class="o">::</span><span class="n">RandomPartitioner</span><span class="w"> </span><span class="n">random_partitioner</span><span class="p">;</span><span class="w"></span>
<span class="n">tf</span><span class="o">::</span><span class="n">DynamicPartitioner</span><span class="w"> </span><span class="n">dynamic_partitioner</span><span class="p">;</span><span class="w"></span>
<span class="c1">// create four parallel-iteration tasks from the four execution policies</span>
<span class="n">taskflow</span><span class="p">.</span><span class="n">for_each</span><span class="p">(</span><span class="n">data</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">data</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span><span class="w"> </span><span class="p">[](</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">){},</span><span class="w"> </span><span class="n">guided_partitioner</span><span class="p">);</span><span class="w"></span>
<span class="n">taskflow</span><span class="p">.</span><span class="n">for_each</span><span class="p">(</span><span class="n">data</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">data</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span><span class="w"> </span><span class="p">[](</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">){},</span><span class="w"> </span><span class="n">static_partitioner</span><span class="p">);</span><span class="w"></span>
<span class="n">taskflow</span><span class="p">.</span><span class="n">for_each</span><span class="p">(</span><span class="n">data</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">data</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span><span class="w"> </span><span class="p">[](</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">){},</span><span class="w"> </span><span class="n">random_partitioner</span><span class="p">);</span><span class="w"></span>
<span class="n">taskflow</span><span class="p">.</span><span class="n">for_each</span><span class="p">(</span><span class="n">data</span><span class="p">.</span><span class="n">begin</span><span class="p">(),</span><span class="w"> </span><span class="n">data</span><span class="p">.</span><span class="n">end</span><span class="p">(),</span><span class="w"> </span><span class="p">[](</span><span class="kt">int</span><span class="w"> </span><span class="n">i</span><span class="p">){},</span><span class="w"> </span><span class="n">dynamic_partitioner</span><span class="p">);</span><span class="w"></span></pre><p>Each partitioner has a specific algorithm to partition iterations into a set of <em>chunks</em> and distribute chunks to workers. A chunk is the basic unit of work that will be run by a worker during the execution of parallel iterations. The following figure illustrates the scheduling diagram for three major partitioners, <a href="classtf_1_1StaticPartitioner.html" class="m-doc">tf::<wbr />StaticPartitioner</a>, <a href="classtf_1_1DynamicPartitioner.html" class="m-doc">tf::<wbr />DynamicPartitioner</a>, and <a href="classtf_1_1GuidedPartitioner.html" class="m-doc">tf::<wbr />GuidedPartitioner</a>:</p><img class="m-image" src="parallel_for_partition_algorithms.png" alt="Image" /><p>Depending on applications, partitioning algorithms can impact the performance a lot. For example, if a parallel-iteration workload contains a regular work unit per iteration, <a href="classtf_1_1StaticPartitioner.html" class="m-doc">tf::<wbr />StaticPartitioner</a> may deliver the best performance. On the other hand, if the work unit per iteration is irregular and unbalanced, <a href="classtf_1_1GuidedPartitioner.html" class="m-doc">tf::<wbr />GuidedPartitioner</a> or <a href="classtf_1_1DynamicPartitioner.html" class="m-doc">tf::<wbr />DynamicPartitioner</a> can outperform <a href="classtf_1_1StaticPartitioner.html" class="m-doc">tf::<wbr />StaticPartitioner</a>.</p><aside class="m-note m-info"><h4>Note</h4><p>By default, all parallel algorithms in Taskflow use <a href="namespacetf.html#a66b72776c788898aee9e132b0ea9b405" class="m-doc">tf::<wbr />DefaultPartitioner</a>, which is based on guided scheduling via <a href="classtf_1_1GuidedPartitioner.html" class="m-doc">tf::<wbr />GuidedPartitioner</a>.</p></aside></section><section id="DefineAStaticPartitioner"><h2><a href="#DefineAStaticPartitioner">Define a Static Partitioner</a></h2><p>Static partitioner splits iterations into <code>iter_size/chunk_size</code> chunks and distribute chunks to workers in order. If no chunk size is given (<code>chunk_size</code> is 0), Taskflow will partition iterations into chunks that are approximately equal in size. The following code creates a static partitioner with chunk size equal to 100:</p><pre class="m-code"><span class="n">tf</span><span class="o">::</span><span class="n">StaticPartitioner</span><span class="w"> </span><span class="nf">static_partitioner</span><span class="p">(</span><span class="mi">100</span><span class="p">);</span><span class="w"></span></pre></section><section id="DefineADynamicPartitioner"><h2><a href="#DefineADynamicPartitioner">Define a Dynamic Partitioner</a></h2><p>Dynamic partitioner splits iterations into <code>iter_size/chunk_size</code> chunks and distribute chunks to workers without any specific order. If no chunk size is given (<code>chunk_size</code> is 0), Taskflow will use 1 for the minimum size of a partition. The following code creates a dynamic partitioner with chunk size equal to 2:</p><pre class="m-code"><span class="n">tf</span><span class="o">::</span><span class="n">DynamicPartitioner</span><span class="w"> </span><span class="nf">dynamic_partitioner</span><span class="p">(</span><span class="mi">2</span><span class="p">);</span><span class="w"></span></pre></section><section id="DefineAGuidedPartitioner"><h2><a href="#DefineAGuidedPartitioner">Define a Guided Partitioner</a></h2><p>Guided partitioner dynamically decides the chunk size. The size of a chunk is proportional to the number of unassigned iterations divided by the number of the threads, and the size will gradually decrease to the specified chunk size (default 1). The last chunk may be smaller than the specified chunk size. If no chunk size is given (<code>chunk_size</code> is 0), Taskflow will use 1 for the minimum size of a partition. The following code creates a guided partitioner with chunk size equal to 10:</p><pre class="m-code"><span class="n">tf</span><span class="o">::</span><span class="n">GuidedPartitioner</span><span class="w"> </span><span class="nf">guided_partitioner</span><span class="p">(</span><span class="mi">10</span><span class="p">);</span><span class="w"></span></pre><p>In most situations, guided partitioner can achieve decent performance due to adaptive parallelism, especially for those with irregular and unbalanced workload per iteration. As a result, guided partitioner is used as the default partitioner for our parallel algorithms.</p></section><section id="DefineAClosureWrapperForAPartitioner"><h2><a href="#DefineAClosureWrapperForAPartitioner">Define a Closure Wrapper for a Partitioner</a></h2><p>In addition to partition size, applications can specify a <em>closure wrapper</em> for a partitioner. A closure wrapper allows the application to wrapper a partitioned task, i.e., closure, with a custom function object that performs additional tasks. For example:</p><pre class="m-code"><span class="n">std</span><span class="o">::</span><span class="n">atomic</span><span class="o"><</span><span class="kt">int</span><span class="o">></span><span class="w"> </span><span class="n">count</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="mi">0</span><span class="p">;</span><span class="w"></span>
<span class="n">tf</span><span class="o">::</span><span class="n">Taskflow</span><span class="w"> </span><span class="n">taskflow</span><span class="p">;</span><span class="w"></span>
<span class="n">taskflow</span><span class="p">.</span><span class="n">for_each_index</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="mi">100</span><span class="p">,</span><span class="w"> </span><span class="mi">1</span><span class="p">,</span><span class="w"> </span>
<span class="w"> </span><span class="p">[](){</span><span class="w"> </span>
<span class="w"> </span><span class="n">printf</span><span class="p">(</span><span class="s">"%d</span><span class="se">\n</span><span class="s">"</span><span class="p">,</span><span class="w"> </span><span class="n">i</span><span class="p">);</span><span class="w"> </span>
<span class="w"> </span><span class="p">},</span><span class="w"></span>
<span class="w"> </span><span class="n">tf</span><span class="o">::</span><span class="n">StaticPartitioner</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="w"> </span><span class="p">[](</span><span class="k">auto</span><span class="o">&&</span><span class="w"> </span><span class="n">closure</span><span class="p">){</span><span class="w"></span>
<span class="w"> </span><span class="c1">// do something before invoking the partitioned task</span>
<span class="w"> </span><span class="c1">// ...</span>
<span class="w"> </span>
<span class="w"> </span><span class="c1">// invoke the partitioned task</span>
<span class="w"> </span><span class="n">closure</span><span class="p">();</span><span class="w"></span>
<span class="w"> </span><span class="c1">// do something else after invoking the partitioned task</span>
<span class="w"> </span><span class="c1">// ...</span>
<span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="p">);</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="w"></span></pre><p>Each partitioner uses a default closure wrapper (<a href="structtf_1_1DefaultClosureWrapper.html" class="m-doc">tf::<wbr />DefaultClosureWrapper</a>) that does nothing but simply invokes the given closure to perform the ordinary partitioned task.</p><pre class="m-code"><span class="k">struct</span><span class="w"> </span><span class="nc">DefaultClosureWrapper</span><span class="w"> </span><span class="p">{</span><span class="w"></span>
<span class="w"> </span><span class="k">template</span><span class="w"> </span><span class="o"><</span><span class="k">typename</span><span class="w"> </span><span class="nc">C</span><span class="o">></span><span class="w"></span>
<span class="w"> </span><span class="kt">void</span><span class="w"> </span><span class="k">operator</span><span class="p">()(</span><span class="n">C</span><span class="o">&&</span><span class="w"> </span><span class="n">closure</span><span class="p">)</span><span class="w"> </span><span class="k">const</span><span class="w"> </span><span class="p">{</span><span class="w"> </span><span class="n">std</span><span class="o">::</span><span class="n">forward</span><span class="o"><</span><span class="n">C</span><span class="o">></span><span class="p">(</span><span class="n">closure</span><span class="p">)();</span><span class="w"> </span><span class="p">}</span><span class="w"></span>
<span class="p">};</span><span class="w"></span></pre></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">…</div>
</div>
<div class="m-doc-search-content">
<form>
<input type="search" name="q" id="search-input" placeholder="Loading …" 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">↓</span>
/ <span class="m-label m-dim">↑</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–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>
You can’t perform that action at this time.