Wednesday, February 15, 2012

Parallelism in .NET

In one of my previous blogs, I had pointed out to an interesting article that shows how TPL controls the number of threads in the Thread Pool using hill-climbing heuristics.

In order to understand why TPL (Task Parallel Library) is far superior to simple muli-threading, we need to understand the concepts of global queue, local queue on each thread, work-stealing algorithms, etc.
Given below are some interesting links that explain these concepts with good illustrations.

http://www.danielmoth.com/Blog/New-And-Improved-CLR-4-Thread-Pool-Engine.aspx

http://blogs.msdn.com/b/jennifer/archive/2009/06/26/work-stealing-in-net-4-0.aspx

http://udooz.net/blog/2009/08/net-4-0-work-stealing-queue-plinq/

A few important points to remember:
  • There is one global queue for the default Thread Pool in .NET 4.0
  • There is also a local queue for each Thread. The Task Scheduler distributes the tasks from the global queue to the local queues on each Thread. Even sub-tasks created by each Thread get queued on the local queue. This improves the performance, as there is no contention to pick up work items (tasks) from the global queue; especially in a multi-core scenario.
  • If a thread is free and there are no tasks in its local queue and also global queue, then it will steal work from other threads. This ensures that all cores are optimally utilized. This concept is called 'work stealing'.
  • Tasks from the global queue are picked up in 'FIFO' order. Tasks from the local queue are picked up in 'LIFO' order based on the assumption that the last-in is still hot in the cache. Work stealing again happens in 'FIFO' order.
There is a wonderful book on parallel computing available on MSDN that is a must read for everyone.