 # Boost :

From: k-oli_at_[hidden]
Date: 2008-09-13 15:05:42

Am Freitag, 12. September 2008 08:17:55 schrieb vicente.botet:
> int fib_seq(int n) {
> if (n <= 1) return n;
> else return fib_seq(nâˆ’1) + fib_seq(nâˆ’2);
> }
> void fib_par(int n) {
> if (n <= 5) // granularity ctl
> return fib_seq(n);
> else {
> return t1.get_future().get() + t2.get_future().get();
> }
> }

The recursive fibonacci algorithm is horrible ineficient - better use this
one:

inline
int fibonacci( int n)
{
if ( n == 0) return 0;
if ( n == 1) return 1;
int k1( 1), k2( 0);
for ( int i( 2); i <= n; ++i)
{
int tmp( k1);
k1 = k1 + k2;
k2 = tmp;
}
return k1;
}

> Well, we can see that the number worker threads depends on the fib_par
> parameter. As soon as the fib_par function waits on its sub_tasks t1 and
> available for fib_par(9) and fib_par(8). When this worker thread call
> fib_par(9) after launching fib_par(8) and fib_par(7) will be blocked to
> manage other task, ... Evidently this do not scale very well, so we can not
> use the threadpool library to address this kind of problems, in which the
> tasks is split on sub-task launched to be run in parallel, and the the

The problem is caused by this code:
return t1.get_future().get() + t2.get_future().get();
Because it blocks until t1 and t2 are ready -> dead lock possible.

Instead you can do something like:

tp::task< int > t1( pool.submit( boost::bind( & fib_par, n - 1) ) );
tp::task< int > t2( pool.submit( boost::bind( & fib_par, n - 2) ) );
boost::future< void > f(
boost::op( t1.get_future() ) && boost::op( t2.get_future() ) );
pool.chained_submit(
boost::bind(