[boost] [threadpool] sub_tasks and active waiting

Subject: [boost] [threadpool] sub_tasks and active waiting
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-09-12 02:17:55

Hi,

How can I define pool so the following code do not deadlocks?

???? pool;

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

int main() {

    return fib_par(10);
}

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.

IMO, what we need is that instead of creating a task we create a subtask. 
When the function will wait until the results of its subtasks are ready, we 
don't need to block the worker thread, instead we can implement replace the 
pasive wait by an active one, which will check if the waited task is ready 
and if this is not the case it will do a scheduling step on the associated 
thread pool and check again.

void fib_par(int n) {
    if (n <= 5) // granularity ctl
        return fib_seq(n);
    else {
        tp::sub_task<int> t1(pool.submit_subtask(bind(fib_par, n-1));
        tp::sub_task<int> t2(pool.submit_subtask(bind(fib_par, n-2));
        return t1.get() + t2.get();
    }
}

The submison of a sub_task can be done differently of a task, because there 
is a parent task that will be waiting for the end of the sub_task, so maybe 
we can add it on LIFO order.

Do you think that this is an interesting feature for your library? could it 
be integrated in your library without disruption?

Best,
______________________
Vicente Juan Botet Escribá