Intel® oneAPI Threading Building Blocks
Ask questions and share information about adding parallelism to your applications when using this threading library.

Help with Fibonacci Recursive

Gregory_G_
Beginner
250 Views

Hi anyone can help me? why it's not running?

 

#include <stdio.h>
#include <tbb/tbb.h>

using namespace tbb;

class FibTask: public task {
    public:
    const long n;
    long* const sum;
    FibTask(long n_,long* sum_ ) : n(n_), sum(sum_)
    {}
     task* execute() {
        
            long x, y;
            FibTask& a = *new( allocate_child() )
            FibTask(n-1,&x);
            FibTask& b = *new( allocate_child() )
            FibTask(n-2,&y);
            set_ref_count(3);
            spawn( b );
            spawn_and_wait_for_all( a );
            *sum = x+y;
        
        return NULL;
    }
};


long ParallelFib(long n ) {
    long sum;
    FibTask& a = *new(task::allocate_root())
    FibTask(n,&sum);
    task::spawn_root_and_wait(a);
    
    return sum;
}

// Fibonacci paralelo.
int    main() {

    long int n = 30;
    task_scheduler_init init(task_scheduler_init::automatic);    
    init.initialize();
    printf("%ld",ParallelFib(n));
    init.terminate();
    
    return 0;
}

0 Kudos
5 Replies
Gregory_G_
Beginner
250 Views

ooops,

#include <stdio.h>
#include <tbb/tbb.h>

using namespace tbb;

class FibTask: public task {
    public:
    const long n;
    long* const sum;
    FibTask(long n_,long* sum_ ) : n(n_), sum(sum_)
    {}
     task* execute() {
        
            long x, y;
            FibTask& a = *new( allocate_child() )
            FibTask(n-1,&x);
            FibTask& b = *new( allocate_child() )
            FibTask(n-2,&y);
            set_ref_count(3);
            spawn( b );
            spawn_and_wait_for_all( a );
            *sum = x+y;
        
        return NULL;
    }
};


long ParallelFib(long n ) {
    long sum;
    FibTask& a = *new(task::allocate_root())
    FibTask(n,&sum);
    task::spawn_root_and_wait(a);
    
    return sum;
}

// Fibonacci paralelo.
int    main() {

    long int n = 30;
    task_scheduler_init init(task_scheduler_init::automatic);    
    init.initialize();
    ParallelFib(n);
    init.terminate();
    
    return 0;
}

0 Kudos
Gregory_G_
Beginner
250 Views

Segmentation falt

0 Kudos
RafSchietekat
Valued Contributor III
250 Views

You don't terminate the calculation. The User Guide does so by delegating the calculation to SerialFib below Cutoff, and SerialFib returns n below 2: 0, 1, … You can eliminate SerialFib, but not the special treatment below n=2.

0 Kudos
Gregory_G_
Beginner
250 Views

Thank's Raf,

Now it works!

 

the final version is

#include <stdio.h>
#include <tbb/tbb.h>

using namespace tbb;

long SerialFib(long n ) {
    if( n<2 )
        return n;
    else
    return SerialFib(n-1)+SerialFib(n-2);
}

class FibTask: public task {
    public:
    const long n;
    long* const sum;
    FibTask(long n_,long* sum_ ) : n(n_), sum(sum_)
    {}
     task* execute() {
        if ( n < 2) {
            *sum = SerialFib(n);
        } else {
            long x, y;
            FibTask& a = *new( allocate_child() ) FibTask(n-1,&x);
            FibTask& b = *new( allocate_child() ) FibTask(n-2,&y);
            set_ref_count(3);
            spawn( b );
            spawn_and_wait_for_all( a );
            *sum = x+y;
        }        
        return NULL;
    }
};


long ParallelFib(long n ) {
    long sum;
    FibTask& a = *new(task::allocate_root()) FibTask(n,&sum);
    task::spawn_root_and_wait(a);
    
    return sum;
}

// Fibonacci paralelo.
int    main() {
    
    task_scheduler_init init(task_scheduler_init::automatic);    
    init.initialize();
    printf("%ld",ParallelFib(40));
    init.terminate();

    return 0;
}

 

It's right isn't it?

0 Kudos
RafSchietekat
Valued Contributor III
250 Views

Except that you shouldn't switch to SerialFib only for n smaller than 2 (now you might as well return n instead and get rid of SerialFib). The role of SerialFib in the User Guide example is to give at least tasks at the lower levels enough work that average parallel overhead, even with tasks already orders of magnitude cheaper than threads, remains limited. Here it dominates because no task has more than a few instructions of useful work. See "User Guide>Parallelizing Simple Loops>parallel_for>Controlling Chunking" for a nice explanation of the principle.

0 Kudos
Reply