Work-Stealing in .NET 4.0
There is some truly amazing support for parallel programming in .NET 4.0. One of the compelling new features of the Thread Pool in .NET 4.0 is work-stealing, which allows work to be processed by worker threads more efficiently.
First of all, in addition to the global queue, there are local queues for each worker thread.
Let's say that the main program thread generated 2 tasks, which are added to the global queue.
Then each worker thread can take a task to process.
Then, suppose that Task 2 spawns three subtasks: Task 3, Task 4, and Task 5. These tasks are placed on the local queue of Worker Thread 1.
Next, assume Worker Thread 1 completes Task 2. It looks at its local queue, and takes the last task (Task 5) off to process. It purposefully takes the last task, the point being that the last task might still be in the cache, while it is likely that the first task (Task 3) is out of the cache. Hence, there are performance improvements in processing local queues in a LIFO order.
Now, assume Worker Thread p completes Task 1. It looks first at its local queue, and there are no tasks there. Then it looks at the global queue...no tasks there either. Finally, it looks at other local queues. This is the concept of work-stealing: it can "steal" tasks from those queues. So Worker Thread p would take Task 3 to process.
Note also that it steals work from the top of the queue (taking the first in), while Worker Thread 1 is processing from the bottom of the queue (taking the last in). That is to reduce contention. It also optimizes for caching: Worker Thread 1 is taking the tasks that are likely still in its cache, and Worker Thread p is taking the tasks that are least likely to be in Worker Thread 1's cache.
Finally, if Task 3 had further subtasks, they would be placed on Worker Thread p's local queue.
To learn more about the support for parallel programming in .NET 4.0, check out Daniel Moth's talk from PDC 2008 at http://channel9.msdn.com/pdc2008/TL26/. It was one of my top 2 favorite talks from PDC last year...Daniel is an amazing presenter and the functionality is just so cool.
Other Resources on Work-Stealing Queues:
http://www.danielmoth.com/Blog/2008/11/new-and-improved-clr-4-thread-pool.html
http://www.bluebytesoftware.com/blog/2008/08/12/BuildingACustomThreadPoolSeriesPart2AWorkStealingQueue.aspx
