fibonacci

# Fibonacci Number

Problem Formulation

Problem Formulation

fibonacci_1FibonacciNumberProblem
Recursive Fibonacci Parallelism

Recursive Fibonacci Parallelism

fibonacci_1RecursiveFibonacciParallelism

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.

    intfib(intn){
    if(n<2)returnn;
    returnfib(n-1)+fib(n-2);
    }

# Recursive Fibonacci Parallelism

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

    #include<taskflow/taskflow.hpp>

    intspawn(intn,tf::Subflow&sbf){
    if(n<2)returnn;
    intres1,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();
    returnres1+res2;
    }

    intmain(intargc,char*argv[]){

    intN=5;
    intres;

    tf::Executorexecutor;
    tf::Taskflowtaskflow("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;

    return0;
    }

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

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