taskflow/docs/PartitioningAlgorithm.html at master · stdexception/taskflow · GitHub

History

205 lines (203 loc) · 16.6 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

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

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

<head>

<title>Taskflow: A General-purpose Task-parallel Programming System: Partitioning Algorithm</title>

</head>

<body>

<tbody>

<div id="projectname"><a href="https://github.com/taskflow/taskflow" style="color:inherit; text-decoration:none;">Taskflow: A General-purpose Task-parallel Programming System</a>

</div>

</td>

</tr>

</tbody>

</table>

</div>

/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */

var searchBox = new SearchBox("searchBox", "search/",'.html');

/* @license-end */

</script>

/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */

$(function() { codefold.init(0); });

/* @license-end */

</script>

/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */

$(function() {

initMenu('',true,false,'search.php','Search',true);

$(function() { init_search(); });

});

/* @license-end */

</script>

</div>

</div>

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

class="ui-resizable-handle">

</div>

/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */

$(function(){initNavTree('PartitioningAlgorithm.html',''); initResizable(true); });

/* @license-end */

</script>

<div id="MSearchSelectWindow"

onmouseover="return searchBox.OnSearchSelectShow()"

onmouseout="return searchBox.OnSearchSelectHide()"

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

</div>

<div class="SRStatus" id="Loading">Loading...</div>

<div class="SRStatus" id="Searching">Searching...</div>

<div class="SRStatus" id="NoMatches">No Matches</div>

</div>

<div class="headertitle"><div class="title">Partitioning Algorithm</div></div>

</div>

<div class="toc"><h3>Table of Contents</h3>

<ul>

<a href="#DefineAPartitionerForParallelAlgorithms">Define a Partitioner for Parallel Algorithms</a>

</li>

<a href="#DefineAStaticPartitioner">Define a Static Partitioner</a>

</li>

<a href="#DefineADynamicPartitioner">Define a Dynamic Partitioner</a>

</li>

<a href="#DefineAGuidedPartitioner">Define a Guided Partitioner</a>

</li>

<a href="#DefineAClosureWrapperForAPartitioner">Define a Closure Wrapper for a Partitioner</a>

</li>

</ul>

</div>

<div class="textblock"><p>A partitioning algorithm allows applications to optimize parallel algorithms using different scheduling methods, such as static partitioning, dynamic partitioning, and guided partitioning.</p>

Define a Partitioner for Parallel Algorithms</h1>

<p>A partitioner defines how to partition and distribute iterations to different workers when running parallel algorithms in Taskflow, such as <a class="el" href="classtf_1_1FlowBuilder.html#aae3edfa278baa75b08414e083c14c836" title="constructs an STL-styled parallel-for task">tf::Taskflow::for_each</a> and <a class="el" href="classtf_1_1FlowBuilder.html#a058c250de62b9d1e4305b8ddf03906ee" title="constructs a parallel-transform task">tf::Taskflow::transform</a>. The following example shows how to create parallel-iteration tasks with different execution policies:</p>

<div class="fragment"><div class="line">std::vector<int> data = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}</div>

<div class="line"><span class="comment">// create different partitioners</span></div>

<div class="line"><a class="code hl_class" href="classtf_1_1GuidedPartitioner.html">tf::GuidedPartitioner</a> guided_partitioner;</div>

<div class="line"><a class="code hl_class" href="classtf_1_1StaticPartitioner.html">tf::StaticPartitioner</a> static_partitioner;</div>

<div class="line"><a class="code hl_class" href="classtf_1_1RandomPartitioner.html">tf::RandomPartitioner</a> random_partitioner;</div>

<div class="line"><a class="code hl_class" href="classtf_1_1DynamicPartitioner.html">tf::DynamicPartitioner</a> dynamic_partitioner;</div>

<div class="line"><span class="comment">// create four parallel-iteration tasks from the four execution policies</span></div>

<div class="line">taskflow.for_each(data.begin(), data.end(), [](<span class="keywordtype">int</span> i){}, guided_partitioner);</div>

<div class="line">taskflow.for_each(data.begin(), data.end(), [](<span class="keywordtype">int</span> i){}, static_partitioner);</div>

<div class="line">taskflow.for_each(data.begin(), data.end(), [](<span class="keywordtype">int</span> i){}, random_partitioner);</div>

<div class="line">taskflow.for_each(data.begin(), data.end(), [](<span class="keywordtype">int</span> i){}, dynamic_partitioner);</div>

<div class="ttc" id="aclasstf_1_1DynamicPartitioner_html"><div class="ttname"><a href="classtf_1_1DynamicPartitioner.html">tf::DynamicPartitioner</a></div><div class="ttdoc">class to create a dynamic partitioner for scheduling parallel algorithms</div><div class="ttdef"><b>Definition</b> partitioner.hpp:567</div></div>

<div class="ttc" id="aclasstf_1_1GuidedPartitioner_html"><div class="ttname"><a href="classtf_1_1GuidedPartitioner.html">tf::GuidedPartitioner</a></div><div class="ttdoc">class to create a guided partitioner for scheduling parallel algorithms</div><div class="ttdef"><b>Definition</b> partitioner.hpp:402</div></div>

<div class="ttc" id="aclasstf_1_1RandomPartitioner_html"><div class="ttname"><a href="classtf_1_1RandomPartitioner.html">tf::RandomPartitioner</a></div><div class="ttdoc">class to construct a random partitioner for scheduling parallel algorithms</div><div class="ttdef"><b>Definition</b> partitioner.hpp:691</div></div>

<div class="ttc" id="aclasstf_1_1StaticPartitioner_html"><div class="ttname"><a href="classtf_1_1StaticPartitioner.html">tf::StaticPartitioner</a></div><div class="ttdoc">class to construct a static partitioner for scheduling parallel algorithms</div><div class="ttdef"><b>Definition</b> partitioner.hpp:262</div></div>

</div><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 class="el" href="classtf_1_1StaticPartitioner.html" title="class to construct a static partitioner for scheduling parallel algorithms">tf::StaticPartitioner</a>, <a class="el" href="classtf_1_1DynamicPartitioner.html" title="class to create a dynamic partitioner for scheduling parallel algorithms">tf::DynamicPartitioner</a>, and <a class="el" href="classtf_1_1GuidedPartitioner.html" title="class to create a guided partitioner for scheduling parallel algorithms">tf::GuidedPartitioner</a>:</p>

<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 class="el" href="classtf_1_1StaticPartitioner.html" title="class to construct a static partitioner for scheduling parallel algorithms">tf::StaticPartitioner</a> may deliver the best performance. On the other hand, if the work unit per iteration is irregular and unbalanced, <a class="el" href="classtf_1_1GuidedPartitioner.html" title="class to create a guided partitioner for scheduling parallel algorithms">tf::GuidedPartitioner</a> or <a class="el" href="classtf_1_1DynamicPartitioner.html" title="class to create a dynamic partitioner for scheduling parallel algorithms">tf::DynamicPartitioner</a> can outperform <a class="el" href="classtf_1_1StaticPartitioner.html" title="class to construct a static partitioner for scheduling parallel algorithms">tf::StaticPartitioner</a>.</p>

<dl class="section note"><dt>Note</dt><dd>By default, all parallel algorithms in Taskflow use <a class="el" href="namespacetf.html#ace2c5adcd5039483eebb6dbdbb6f33e3" title="default partitioner set to tf::GuidedPartitioner">tf::DefaultPartitioner</a>, which is based on guided scheduling via <a class="el" href="classtf_1_1GuidedPartitioner.html" title="class to create a guided partitioner for scheduling parallel algorithms">tf::GuidedPartitioner</a>.</dd></dl>

Define a Static Partitioner</h1>

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

<div class="fragment"><div class="line"><a class="code hl_class" href="classtf_1_1StaticPartitioner.html">tf::StaticPartitioner</a> static_partitioner(100);</div>

</div><h1><a class="anchor" id="DefineADynamicPartitioner"></a>

Define a Dynamic Partitioner</h1>

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

<div class="fragment"><div class="line"><a class="code hl_class" href="classtf_1_1DynamicPartitioner.html">tf::DynamicPartitioner</a> dynamic_partitioner(2);</div>

</div><h1><a class="anchor" id="DefineAGuidedPartitioner"></a>

Define a Guided Partitioner</h1>

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

<div class="fragment"><div class="line"><a class="code hl_class" href="classtf_1_1GuidedPartitioner.html">tf::GuidedPartitioner</a> guided_partitioner(10);</div>

</div><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>

Define a Closure Wrapper for a Partitioner</h1>

<p>In addition to partition size, applications can specify a <em>closure wrapper</em> for a partitioner. A closure wrapper allows the application to wrap a partitioned task, i.e., closure, with a custom function object that performs additional tasks. For example:</p>

<div class="fragment"><div class="line">std::atomic<int> count = 0;</div>

<div class="line"><a class="code hl_class" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow;</div>

<div class="line">taskflow.<a class="code hl_function" href="classtf_1_1FlowBuilder.html#a3b132bd902331a11b04b4ad66cf8bf77">for_each_index</a>(0, 100, 1, </div>

<div class="line"> printf(<span class="stringliteral">"%d\n"</span>, i); </div>

<div class="line"> <a class="code hl_class" href="classtf_1_1StaticPartitioner.html">tf::StaticPartitioner</a>(0, [](<span class="keyword">auto</span>&& closure){</div>

<div class="line"> <span class="comment">// do something before invoking the partitioned task</span></div>

<div class="line"> <span class="comment">// invoke the partitioned task</span></div>

<div class="line"> closure();</div>

<div class="line"> <span class="comment">// do something else after invoking the partitioned task</span></div>

<div class="line">executor.run(taskflow).wait();</div>

<div class="ttc" id="aclasstf_1_1FlowBuilder_html_a3b132bd902331a11b04b4ad66cf8bf77"><div class="ttname"><a href="classtf_1_1FlowBuilder.html#a3b132bd902331a11b04b4ad66cf8bf77">tf::FlowBuilder::for_each_index</a></div><div class="ttdeci">Task for_each_index(B first, E last, S step, C callable, P part=P())</div><div class="ttdoc">constructs an index-based parallel-for task</div></div>

<div class="ttc" id="aclasstf_1_1Taskflow_html"><div class="ttname"><a href="classtf_1_1Taskflow.html">tf::Taskflow</a></div><div class="ttdoc">class to create a taskflow object</div><div class="ttdef"><b>Definition</b> taskflow.hpp:64</div></div>

</div><p>Each partitioner uses a default closure wrapper (<a class="el" href="classtf_1_1DefaultClosureWrapper.html" title="class to create a default closure wrapper">tf::DefaultClosureWrapper</a>) that does nothing but simply invokes the given closure to perform the ordinary partitioned task.</p>

<div class="fragment"><div class="line"><span class="keyword">struct </span>DefaultClosureWrapper {</div>

<div class="line"> <span class="keyword">template</span> <<span class="keyword">typename</span> C></div>

<div class="line"> <span class="keywordtype">void</span> operator()(C&& closure)<span class="keyword"> const </span>{ std::forward<C>(closure)(); }</div>

</div> </div></div>

</div>

</div>

<ul>

<li class="navelem"><a class="el" href="Algorithms.html">Taskflow Algorithms</a></li>

Maintained by <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>

 — 

Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.12.0

</li>

</ul>

</div>

taskflow/docs/PartitioningAlgorithm.html at master · stdexception/taskflow · GitHub

Expand file tree

Breadcrumbs

PartitioningAlgorithm.html

Latest commit

History

Breadcrumbs

PartitioningAlgorithm.html

File metadata and controls