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

Subject: Re: [boost] [threadpool] sub_tasks and active waiting
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-09-13 16:11:42

----- Original Message ----- 
From: <k-oli_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Saturday, September 13, 2008 9:05 PM
Subject: Re: [boost] [threadpool] sub_tasks and active waiting

> 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:

this was only one example. Take the sort example if you want.

> 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);

What boost::op stands for?

Which will be the returned value?

What about the sub-tasks feature?

Vicente