-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathExamples.html
More file actions
243 lines (241 loc) · 16.8 KB
/
Copy pathExamples.html
File metadata and controls
243 lines (241 loc) · 16.8 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
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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
<!-- HTML header for doxygen 1.13.1-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.13.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow: A General-purpose Task-parallel Programming System: Learning from Examples</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="cookie.js"></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" />
<link href="custom.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 id="projectrow">
<td id="projectlogo"><img alt="Logo" src="taskflow_logo.png"/></td>
<td id="projectalign">
<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>
<!-- end header part -->
<!-- Generated by Doxygen 1.13.1 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() { codefold.init(0); });
/* @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:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',true,false,'search.php','Search',true);
$(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:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function(){initNavTree('Examples.html',''); initResizable(true); });
/* @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">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></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>
</div>
</div>
<div><div class="header">
<div class="headertitle"><div class="title">Learning from Examples</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#ExamplesTaskGraph">Task Graph</a>
</li>
<li class="level1">
<a href="#ExamplesAsyncTasking">Async Tasking</a>
</li>
<li class="level1">
<a href="#ExamplesParallelAlgorithms">Parallel Algorithms</a>
</li>
<li class="level1">
<a href="#ExamplesGPUTaskGraph">GPU Task Graph</a>
</li>
</ul>
</div>
<div class="textblock"><p>This page collects self-contained examples that demonstrate Taskflow across a broad range of parallel programming patterns, from classic graph algorithms and numerical computing to dynamic task graphs, async pipelines, and GPU acceleration. Each example is designed to be read independently and includes a problem formulation, a parallel implementation, and a discussion of the key Taskflow features at work.</p>
<h1><a class="anchor" id="ExamplesTaskGraph"></a>
Task Graph</h1>
<p>These examples demonstrate how to express parallelism as a static task dependency graph using <a class="el" href="classtf_1_1Taskflow.html" title="class to create a taskflow object">tf::Taskflow</a>, including conditional and non-deterministic control flow.</p>
<table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadLeft">Example </th><th class="markdownTableHeadLeft">Brief </th></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="wavefront.html">Wavefront Parallelism</a> </td><td class="markdownTableBodyLeft">Diagonal sweep parallelism over a 2D grid where each cell depends on its left and top neighbours </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="graphtraversal.html">Graph Traversal</a> </td><td class="markdownTableBodyLeft">Parallel DAG traversal where task dependencies mirror the input graph structure </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesNondeterministicControlFlow.html">Nondeterministic Control Flow</a> </td><td class="markdownTableBodyLeft">Stochastic branching using conditional tasks to express non-deterministic execution paths </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesCholesky.html">Blocked Cholesky Factorization</a> </td><td class="markdownTableBodyLeft">Task-parallel blocked Cholesky decomposition based on a tile dependency graph </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesPERT.html">Critical Path Scheduling</a> </td><td class="markdownTableBodyLeft">PERT chart executed as a static task graph to identify the critical path </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesMakeGraph.html">Incremental Build Graph</a> </td><td class="markdownTableBodyLeft">Make-style incremental build system using condition tasks </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesSpeculativeExecution.html">Speculative Execution</a> </td><td class="markdownTableBodyLeft">Bloom filter simualtion using condition tasks </td></tr>
</table>
<p>Links to each example subpage are provided below:</p><ul>
<li><a class="el" href="wavefront.html">Wavefront Parallelism</a></li>
<li><a class="el" href="graphtraversal.html">Graph Traversal</a></li>
<li><a class="el" href="ExamplesNondeterministicControlFlow.html">Nondeterministic Control Flow</a></li>
<li><a class="el" href="ExamplesCholesky.html">Blocked Cholesky Factorization</a></li>
<li><a class="el" href="ExamplesPERT.html">Critical Path Scheduling</a></li>
<li><a class="el" href="ExamplesMakeGraph.html">Incremental Build Graph</a></li>
<li><a class="el" href="ExamplesSpeculativeExecution.html">Speculative Execution</a></li>
</ul>
<h1><a class="anchor" id="ExamplesAsyncTasking"></a>
Async Tasking</h1>
<p>These examples focus on Taskflow's dynamic task creation capabilities, including async tasks, dependent-async task graphs, cooperative execution, and recursive runtime tasking.</p>
<table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadLeft">Example </th><th class="markdownTableHeadLeft">Brief </th></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesFibonacciNumber.html">Fibonacci Number</a> </td><td class="markdownTableBodyLeft">Recursive task parallelism using <a class="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> and cooperative synchronization via <a class="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesAsyncProducerConsumer.html">Async Producer-Consumer Pipeline</a> </td><td class="markdownTableBodyLeft">Overlapping producer, validator, and consumer stages using dependent-async tasks </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesDivideAndConquer.html">Divide and Conquer</a> </td><td class="markdownTableBodyLeft">Divide-and-conquer parallelism with <a class="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a>, demonstrated on parallel merge sort </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesDynamicDependencyGraph.html">Dynamic Dependency Graph</a> </td><td class="markdownTableBodyLeft">Runtime-driven task graph whose topology and dependencies are determined by program data </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesTSP.html">Traveling Salesman Problem</a> </td><td class="markdownTableBodyLeft">Parallel branch-and-bound solver for the traveling salesman problem </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesGraphColoring.html">Graph Coloring Problem</a> </td><td class="markdownTableBodyLeft">Parallel branch-and-bound solver for the graph coloring problem </td></tr>
</table>
<p>Links to each example subpage are provided below:</p><ul>
<li><a class="el" href="ExamplesFibonacciNumber.html">Fibonacci Number</a></li>
<li><a class="el" href="ExamplesAsyncProducerConsumer.html">Async Producer-Consumer Pipeline</a></li>
<li><a class="el" href="ExamplesDivideAndConquer.html">Divide-and-Conquer Parallelism</a></li>
<li><a class="el" href="ExamplesDynamicDependencyGraph.html">Dynamic Dependency Graph</a></li>
<li><a class="el" href="ExamplesTSP.html">Travelling Salesman Problem</a></li>
<li><a class="el" href="ExamplesGraphColoring.html">Graph Coloring</a></li>
</ul>
<h1><a class="anchor" id="ExamplesParallelAlgorithms"></a>
Parallel Algorithms</h1>
<p>These examples apply Taskflow's parallel algorithms and pipeline scheduling to classic computational and data-processing problems.</p>
<table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadLeft">Example </th><th class="markdownTableHeadLeft">Brief </th></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesBFS.html">Parallel Breadth-First Search</a> </td><td class="markdownTableBodyLeft">Parallel BFS using stateful frontier iteration with <a class="el" href="namespacetf.html#a6c928ec9248757ba8276e316ef26846b" title="alias for the common 1D case of tf::IndexRanges">tf::IndexRange</a> and atomic distance claims </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="matrix_multiplication.html">Matrix Multiplication</a> </td><td class="markdownTableBodyLeft">Parallel dense matrix multiplication partitioned across CPU workers </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="kmeans.html">K-Means Clustering</a> </td><td class="markdownTableBodyLeft">Parallel k-means clustering with iterative assignment and centroid update steps </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesStencil3D.html">3D Stencil Computation</a> </td><td class="markdownTableBodyLeft">Parallel 3D Jacobi stencil over a volumetric grid using <a class="el" href="classtf_1_1IndexRanges.html" title="class to create an N-dimensional index range of integral indices">tf::IndexRanges</a> </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesSpMV.html">Sparse Matrix-Vector Multiplication</a> </td><td class="markdownTableBodyLeft">Parallel SpMV in CSR format demonstrating partitioner selection for irregular workloads </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="ExamplesConv2D.html">2D Image Convolution</a> </td><td class="markdownTableBodyLeft">Parallel 2D image convolution using <a class="el" href="classtf_1_1IndexRanges.html" title="class to create an N-dimensional index range of integral indices">tf::IndexRanges</a> </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="TextProcessingPipeline.html">Text Processing Pipeline</a> </td><td class="markdownTableBodyLeft">Character frequency analysis expressed as a three-stage parallel pipeline </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="GraphProcessingPipeline.html">Graph Processing Pipeline</a> </td><td class="markdownTableBodyLeft">Wavefront pipeline scheduling over a DAG of dependent processing stages </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="TaskflowProcessingPipeline.html">Taskflow Processing Pipeline</a> </td><td class="markdownTableBodyLeft">Nested taskflow graphs embedded inside pipeline stages for hierarchical parallelism </td></tr>
</table>
<p>Links to each example subpage are provided below:</p><ul>
<li><a class="el" href="ExamplesBFS.html">Parallel Breadth-First Search</a></li>
<li><a class="el" href="matrix_multiplication.html">Matrix Multiplication</a></li>
<li><a class="el" href="kmeans.html">k-means Clustering</a></li>
<li><a class="el" href="ExamplesStencil3D.html">3D Stencil Computation</a></li>
<li><a class="el" href="ExamplesSpMV.html">Sparse Matrix-Vector Multiplication</a></li>
<li><a class="el" href="ExamplesConv2D.html">2D Image Convolution</a></li>
<li><a class="el" href="TextProcessingPipeline.html">Text Processing Pipeline</a></li>
<li><a class="el" href="GraphProcessingPipeline.html">Graph Processing Pipeline</a></li>
<li><a class="el" href="TaskflowProcessingPipeline.html">Taskflow Processing Pipeline</a></li>
</ul>
<h1><a class="anchor" id="ExamplesGPUTaskGraph"></a>
GPU Task Graph</h1>
<p>These examples demonstrate how to offload computation to a CUDA GPU using <a class="el" href="namespacetf.html#a713c427e4f9841a90dec67045a3babed" title="default smart pointer type to manage a cudaGraph_t object with unique ownership">tf::cudaGraph</a>, coordinated with CPU tasks in a single taskflow.</p>
<table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadLeft">Example </th><th class="markdownTableHeadLeft">Brief </th></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft"><a class="el" href="MatrixMultiplicationWithCUDAGPU.html">Matrix Multiplication (CUDA)</a> </td><td class="markdownTableBodyLeft">GPU-accelerated dense matrix multiplication using <a class="el" href="namespacetf.html#a713c427e4f9841a90dec67045a3babed" title="default smart pointer type to manage a cudaGraph_t object with unique ownership">tf::cudaGraph</a> coordinated with CPU tasks </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft"><a class="el" href="KMeansWithCUDAGPU.html">K-Means Clustering (CUDA)</a> </td><td class="markdownTableBodyLeft">GPU-accelerated k-means clustering with CUDA kernels for assignment and centroid update </td></tr>
</table>
<p>Links to each example subpage are provided below:</p><ul>
<li><a class="el" href="MatrixMultiplicationWithCUDAGPU.html">Matrix Multiplication with CUDA GPU</a></li>
<li><a class="el" href="KMeansWithCUDAGPU.html">k-means Clustering with CUDA GPU</a> </li>
</ul>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="footer">
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.13.1
</li>
</ul>
</div>