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. 

WorkStealing1

Let's say that the main program thread generated 2 tasks, which are added to the global queue. 

WorkStealing2

Then each worker thread can take a task to process. 

WorkStealing3

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. 

WorkStealing4

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. 

WorkStealing5

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. 

WorkStealing6

Finally, if Task 3 had further subtasks, they would be placed on Worker Thread p's local queue. 

WorkStealing7

To learn more about the support for parallel programming in .NET 4.0, check out Daniel Moth's talk from PDC 2008 at https://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:

https://www.danielmoth.com/Blog/2008/11/new-and-improved-clr-4-thread-pool.html

https://www.bluebytesoftware.com/blog/2008/08/12/BuildingACustomThreadPoolSeriesPart2AWorkStealingQueue.aspx