| Taskflow: A General-purpose Task-parallel Programming System

Loading...
Searching...
No Matches
Fibonacci Number

We study the classic problem, Fibonacci Number, to demonstrate the use of recursive task parallelism.

# Problem Formulation

In mathematics, the Fibonacci numbers, commonly denoted as `fibonacci(n)`, form a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1.

`0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...`

A common solution for computing fibonacci numbers is recursion:

int fibonacci(int n) {
if(n < 2) return n;
return fibonacci(n-1) + fibonacci(n-2);
}

# Recursive Fibonacci Parallelism using Runtime Tasking

We use Runtime Tasking and Asynchronous Tasking to recursively compute Fibonacci numbers in parallel. A runtime task tasks a reference to tf::Runtime 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 tf::Runtime:

#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;
}
tf::Executor::silent_async
void silent_async(P &&params, F &&func)
similar to tf::Executor::async but does not return a future object
tf::Executor::wait_for_all
void wait_for_all()
waits for all tasks to complete
tf::Runtime
class to create a runtime task
Definition runtime.hpp:47
tf::Runtime::silent_async
void silent_async(F &&f)
runs the given function asynchronously without returning any future object
Definition runtime.hpp:671
tf::Runtime::corun
void corun()
corun all tasks spawned by this runtime with other workers
Definition runtime.hpp:646

The `fibonacci` function recursively spawns two asynchronous tasks to compute `fibonacci(N-1)` and `fibonacci(N-2)` in parallel using `tf::Runtime::silent_async`. After spawning the two tasks, the function invokes tf::Runtime::corun() to wait until all tasks spawned by `rt` 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 tf::Executor::wait_for_all. 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:

## Tail Recursion Optimization

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.

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); });
// tail optimization for the right child
res2 = fibonacci(N-2, rt);
// cooperatively run tasks until all tasks spawned by `rt` complete
rt.corun();
return res1 + res2;
}

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.

## Benchmarking

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.

N | w/ tail recursion optimization | w/o tail recursion optimization
--- | --- | ---
20 | 0.23 ms | 0.31 ms
25 | 2 ms | 4 ms
30 | 23 ms | 42 ms
35 | 269 ms | 483 ms
40 | 3003 ms | 5124 ms

As `N` 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 `N = 40`, tail recursion optimization reduces the runtime by over 40%.

# Recursive Fibonacci Parallelism using Task Group

Similar to tf::Runtime, tf::TaskGroup provides a lightweight and structured mechanism for expressing recursive parallelism directly within a running task (see Task Group). The example below demonstrates how to parallelize Fibonacci using a task group:

tf::Executor executor;
size_t fibonacci(size_t N) {
if(N < 2) return N;
size_t res1, res2;
tf::TaskGroup tg = executor.task_group();
tg.silent_async([N, &res1](){ res1 = fibonacci(N-1); });
res2 = fibonacci(N-2);
// cooperatively run tasks until all tasks spawned by `tg` complete
tg.corun();
return res1 + res2;
}
int main() {
size_t N = 30, res;
res = executor.async([](){ return fibonacci(30); }).get();
std::cout << N << "-th Fibonacci number is " << res << '\n';
return 0;
}
tf::Executor
class to create an executor
Definition executor.hpp:62
tf::Executor::task_group
TaskGroup task_group()
creates a task group that executes a collection of asynchronous tasks
Definition task_group.hpp:879
tf::Executor::async
auto async(P &&params, F &&func)
creates a parameterized asynchronous task to run the given function
tf::TaskGroup
class to create a task group from a task
Definition task_group.hpp:61
tf::TaskGroup::corun
void corun()
corun all tasks spawned by this task group with other workers
Definition task_group.hpp:725
tf::TaskGroup::silent_async
void silent_async(F &&f)
runs the given function asynchronously without returning any future object
Definition task_group.hpp:756