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