Re: [boost] [thread-pool/futures] Explicit yielding

From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-06-09 14:52:21

Hello,

----- Original Message ----- 
From: "Kowalke Oliver (QD IT PA AS)" <Oliver.Kowalke_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, June 09, 2008 1:53 PM
Subject: Re: [boost] [thread-pool/futures] Explicit yielding

> For what would be 'task-stealing' be usefull?
> Wouldn't be one task-queue on which worker threads are waiting be 
> sufficient?

It may be sufficient, but it can be ineficient.

> Polling of one thread in task-queues of other threads seams to be 
> expensive.

You are right, the main raison this is expensive is that we need to
synchronize the access to this shared resource. But this is already the case
when we have only one task-queue.

I think that the quiz is that we need to manage the root-task (without
parent) and the sub-task (with a parent task) differently. root-task must be
handle in fifo order, but sub-tasks are needed to complete other tasks, so
they need to be handled in lifo order.

So a worker thread will take a root-task at a time in fifo order. If the 
task needs to wait for the result of another task, the worker thread will 
handle the tasks in the task-stack in lifo order, checking if the future is 
ready. When there are no more tasks in the task-stack and the future is not 
ready, the worker thread can either wait explicitly on the future or try to 
execute other tasks. We can either take a new root-task or a sub-task of 
another worker thread. But what we can do when there are no new root-tasks? 
we can take a sub-task of the other worker threads. Even if this is 
expensive this avoid to let a working thread in a waiting state. Only when 
there are no more task to do the working thread will wait on the future. In 
addition some optimizations can be applied becuase the owner of the 
task-stack use it on lifo order but the others use it on fifo order (so it 
needs to be a dequeue).

I hope this will help you to understand for what would 'task-stealing' be 
usefull.
Anyway a reading of the FJTask  article 
http://gee.cs.oswego.edu/dl/papers/fj.pdf, or the tasks in Threading 
Building Blocks (TBB) 
http://www.threadingbuildingblocks.org/documentation.php will be worthwhile.

Best
_____________________
Vicente Juan Botet Escriba