taskflow/docs/ExamplesFibonacciNumber.html at master · taskflow/taskflow

History

380 lines (363 loc) · 34.3 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

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

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

369

370

371

372

373

374

375

376

377

378

379

380

<!DOCTYPE html>

<head>

<title>Learning from Examples » Fibonacci Number | Taskflow QuickStart</title>

</head>

<body>

<a href="https://taskflow.github.io"><img src="taskflow_logo.png" alt="" />Taskflow</a> | <a href="index.html" class="m-thin">QuickStart</a>

</svg></a>

</div>

<li><a href="pages.html">Handbook</a></li>

<li><a href="namespaces.html">Namespaces</a></li>

</ol>

<li><a href="annotated.html">Classes</a></li>

<li><a href="files.html">Files</a></li>

</svg></a></li>

</ol>

</div>

</nav></header>

<h1>

<a href="Examples.html">Learning from Examples</a> »

Fibonacci Number

</h1>

<h3>Contents</h3>

<ul>

<li><a href="#FibonacciNumberProblem">Problem Formulation</a></li>

<li>

<a href="#RecursiveFibonacciParallelismUsingRuntimeTasking">Recursive Fibonacci Parallelism using Runtime Tasking</a>

<ul>

<li><a href="#TailRecursionOptimization">Tail Recursion Optimization</a></li>

<li><a href="#FibonacciNumberBenchmarking">Benchmarking</a></li>

</ul>

</li>

<li><a href="#RecursiveFibonacciParallelismUsingTaskGroup">Recursive Fibonacci Parallelism using %Task Group</a></li>

</ul>

</nav>

We study the classic problem, Fibonacci Number, to demonstrate the use of recursive task parallelism.<section id="FibonacciNumberProblem"><h2><a href="#FibonacciNumberProblem">Problem Formulation</a></h2>In mathematics, the Fibonacci numbers, commonly denoted as <code>fibonacci(n)</code>, form a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1.<code>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</code>A common solution for computing fibonacci numbers is recursion:<pre class="m-code">int fibonacci(int n) {

if(n < 2) return n;

return fibonacci(n-1) + fibonacci(n-2);

}</pre></section><section id="RecursiveFibonacciParallelismUsingRuntimeTasking"><h2><a href="#RecursiveFibonacciParallelismUsingRuntimeTasking">Recursive Fibonacci Parallelism using Runtime Tasking</a></h2>We use <a href="RuntimeTasking.html" class="m-doc">Runtime Tasking</a> and <a href="AsyncTasking.html" class="m-doc">Asynchronous Tasking</a> to recursively compute Fibonacci numbers in parallel. A runtime task tasks a reference to <a href="classtf_1_1Runtime.html" class="m-doc">tf::Runtime</a> as its argument, allowing users to interact with the executor and spawn tasks dynamically. The example below demonstrates a parallel recursive implementation of Fibonacci numbers using <a href="classtf_1_1Runtime.html" class="m-doc">tf::Runtime</a>:<pre class="m-code">#include <taskflow/taskflow.hpp>

size_t fibonacci(size_t N, tf::Runtime& rt) {

if(N < 2) return N;

size_t res1, res2;

rt.silent_async([N, &res1](tf::Runtime& rt1){ res1 = fibonacci(N-1, rt1); });

rt.silent_async([N, &res2](tf::Runtime& rt2){ res2 = fibonacci(N-2, rt2); });

// cooperatively run tasks until all tasks spawned by `rt` complete

rt.corun();

return res1 + res2;

}

int main() {

tf::Executor executor;

size_t N = 30, res;

executor.silent_async([N, &res](tf::Runtime& rt){ res = fibonacci(N, rt); });

executor.wait_for_all();

std::cout << N << "-th Fibonacci number is " << res << '\n';

return 0;

}</pre>The <code>fibonacci</code> function recursively spawns two asynchronous tasks to compute <code>fibonacci(N-1)</code> and <code>fibonacci(N-2)</code> in parallel using <code><a href="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05" class="m-doc">tf::Runtime::silent_async</a></code>. After spawning the two tasks, the function invokes <a href="classtf_1_1Runtime.html#aba54a7cacffb54f5eb133730d256a7c4" class="m-doc">tf::Runtime::corun()</a> to wait until all tasks spawned by <code>rt</code> complete, without blocking the caller worker. In the main function, the executor creates an async task from the top Fibonacci number and waits for completion using <a href="classtf_1_1Executor.html#ab9aa252f70e9a40020a1e5a89d485b85" class="m-doc">tf::Executor::wait_for_all</a>. Once finished, the result is printed. The figure below shows the execution diagram, where the suffixes *_1 and *_2 represent the left and right children spawned by their parent runtime:<div class="m-graph"><svg style="width: 40.400rem; height: 26.000rem;" viewBox="0.00 0.00 404.00 260.00">

<title>Fibonacci</title>

<text text-anchor="middle" x="221" y="-237" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(4)</text>

</g>

<text text-anchor="middle" x="175" y="-165" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(3)</text>

</g>

</g>

<text text-anchor="middle" x="267" y="-165" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(2)</text>

</g>

</g>

<text text-anchor="middle" x="83" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(2)</text>

</g>

</g>

<text text-anchor="middle" x="175" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(1)</text>

</g>

</g>

<text text-anchor="middle" x="37" y="-21" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(1)</text>

</g>

</g>

<text text-anchor="middle" x="129" y="-21" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(0)</text>

</g>

</g>

<text text-anchor="middle" x="267" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(1)</text>

</g>

</g>

<text text-anchor="middle" x="359" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(0)</text>

</g>

</g>

</svg>

</div><section id="TailRecursionOptimization"><h3><a href="#TailRecursionOptimization">Tail Recursion Optimization</a></h3>In recursive parallelism, especially for problems like Fibonacci computation, spawning both recursive branches as asynchronous tasks can lead to excessive task creation and stack growth, which may degrade performance and overwhelm the runtime scheduler. Additionally, when both child tasks are launched asynchronously, the parent task must wait for both to finish, potentially blocking a worker thread and reducing parallel throughput. To address these issues, we apply tail recursion optimization to one branch of the Fibonacci call. This allows one of the recursive calls to proceed immediately in the current execution context, reducing both scheduling overhead and stack usage.<pre class="m-code">size_t fibonacci(size_t N, tf::Runtime& rt) {

// tail optimization for the right child

res2 = fibonacci(N-2, rt);

// cooperatively run tasks until all tasks spawned by `rt` complete

rt.corun();

}</pre>The figure below shows the execution diagram, where the suffix *_1 represent the left child spawned by its parent runtime. As we can see, the right child is optimized out through tail recursion optimization.<div class="m-graph"><svg style="width: 40.400rem; height: 26.000rem;" viewBox="0.00 0.00 404.00 260.00">

<title>Fibonacci</title>

<text text-anchor="middle" x="221" y="-237" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(4)</text>

</g>

<text text-anchor="middle" x="175" y="-165" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(3)</text>

</g>

</g>

<text text-anchor="middle" x="267" y="-165" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(2)</text>

</g>

</g>

<text text-anchor="middle" x="83" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(2)</text>

</g>

</g>

<text text-anchor="middle" x="175" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(1)</text>

</g>

</g>

<text text-anchor="middle" x="37" y="-21" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(1)</text>

</g>

</g>

<text text-anchor="middle" x="129" y="-21" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(0)</text>

</g>

</g>

<text text-anchor="middle" x="267" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(1)</text>

</g>

</g>

<text text-anchor="middle" x="359" y="-93" font-family="Helvetica,sans-Serif" font-size="10.00">fibonacci(0)</text>

</g>

</g>

</svg>

</div></section><section id="FibonacciNumberBenchmarking"><h3><a href="#FibonacciNumberBenchmarking">Benchmarking</a></h3>Based on the discussion above, we compare the runtime of recursive Fibonacci parallelism (1) with tail recursion optimization and (2) without it, across different Fibonacci numbers.<table class="m-table"><thead><tr><th>N</th><th>w/ tail recursion optimization</th><th>w/o tail recursion optimization</th></tr></thead><tbody><tr><td>20</td><td>0.23 ms</td><td>0.31 ms</td></tr><tr><td>25</td><td>2 ms</td><td>4 ms</td></tr><tr><td>30</td><td>23 ms</td><td>42 ms</td></tr><tr><td>35</td><td>269 ms</td><td>483 ms</td></tr><tr><td>40</td><td>3003 ms</td><td>5124 ms</td></tr></tbody></table>As <code>N</code> increases, the performance gap between the two versions widens significantly. With tail recursion optimization, the program avoids spawning another async task, thereby reducing scheduling overhead and stack pressure. This leads to better CPU utilization and lower task management cost. For example, at <code>N = 40</code>, tail recursion optimization reduces the runtime by over 40%.</section></section><section id="RecursiveFibonacciParallelismUsingTaskGroup"><h2><a href="#RecursiveFibonacciParallelismUsingTaskGroup">Recursive Fibonacci Parallelism using %Task Group</a></h2>Similar to <a href="classtf_1_1Runtime.html" class="m-doc">tf::Runtime</a>, <a href="classtf_1_1TaskGroup.html" class="m-doc">tf::TaskGroup</a> provides a lightweight and structured mechanism for expressing recursive parallelism directly within a running task (see <a href="TaskGroup.html" class="m-doc">Task Group</a>). The example below demonstrates how to parallelize Fibonacci using a task group:<pre class="m-code">tf::Executor executor;

tf::TaskGroup tg = executor.task_group();

tg.silent_async([N, &res1](){ res1 = fibonacci(N-1); });

// cooperatively run tasks until all tasks spawned by `tg` complete

tg.corun();

}

int main() {

res = executor.async([](){ return fibonacci(30); }).get();

return 0;

}</pre></section>

</div>

</article></main>

<div>Tab / T to search, Esc to close</div>

</div>

<form>

</form>

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.

Use ↓

/ ↑ to navigate through the list,

Enter to go.

Tab autocompletes common prefix, you can

copy a link to the result using ⌘

L while ⌘

M produces a Markdown link.

</div>

<div id="search-notfound" class="m-text m-warning m-text-center">Sorry, nothing was found.</div>

</div>

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–2026. Generated by <a href="https://doxygen.org/">Doxygen</a> 1.9.1 and <a href="https://mcss.mosra.cz/">m.css</a>.

</div>

</nav></footer>

</body>

</html>

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

FilesExpand file tree

ExamplesFibonacciNumber.html

Latest commit

History

ExamplesFibonacciNumber.html

File metadata and controls