Re: [boost] [threadpool] sub_tasks and active waiting

Subject: Re: [boost] [threadpool] sub_tasks and active waiting
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 {
>         tp::task<int> t1(pool.submit(bind(fib_par, n-1));
>         tp::task<int> t2(pool.submit(bind(fib_par, n-2));
>         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
> t2, the worker thread cannot handle other tasks, so we need a thread
> 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
> parennt task waits on its child sub-task to do somthing.

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(
        & add,
        t1.get_future(),
        t2.get_future() ),
  f);

Oliver