Taskflow  2.7.0
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 F(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 fib(int n) {
if(n < 2) return n;
return fib(n-1) + fib(n-2);
}

Recursive Fibonacci Parallelism

We use tf::Subflow to recursively compute fibonacci numbers in parallel.

int spawn(int n, tf::Subflow& sbf) {
if (n < 2) return n;
int res1, res2;
sbf.emplace([&res1, n] (tf::Subflow& sbf) { res1 = spawn(n - 1, sbf); } ).name(std::to_string(n-1));
sbf.emplace([&res2, n] (tf::Subflow& sbf) { res2 = spawn(n - 2, sbf); } ).name(std::to_string(n-2));
sbf.join();
return res1 + res2;
}
int main(int argc, char* argv[]) {
int N = 7;
int res;
tf::Executor executor;
tf::Taskflow taskflow("fibonacci");
taskflow.emplace([&res, N] (tf::Subflow& sbf) { res = spawn(N, sbf); }).name(std::to_string(N));
executor.run(taskflow).wait();
taskflow.dump(std::cout);
std::cout << "Fib[" << N << "]: " << res << std::endl;
return 0;
}

The spawned taskflow graph for computing up to the 7th fibonacci number is shown below:

fibonacci_7.svg

Even if recursive dynamic tasking or subflows are permitted, the recursion depth may not be too deep or it can cause stack overflow.