Hello, ----- Original Message ----- From: "Kowalke Oliver (QD IT PA AS)" <Oliver.Kowalke@qimonda.com> To: <boost@lists.boost.org> 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