Steve Strong's Blog

So far, we've looked the the motivations behind concurrency and Data Parallelism as a technique to introduce concurrency into your code. We've also looked at some simple examples of Parallel.For() and Parallel.ForEach(). In this post we're going to explore the other main way that concurrency can be harnessed, Task Parallelism.

Data parallelism was all about executing the same block of code on many different data items. Task parallelism is about concurrently executing different blocks of code, perhaps operating on the same data, perhaps on different. What's important is that the tasks are, as far as possible, independent. If there are dependencies between them things will rapidly get more complex, and all those issues we discussed in data parallelism such as corruption and deadlocks will raise their heads.

Let's look at an example. Firstly, in the familiar sequential world:

public void OnlineStore()
{
	TakeOrder();
	SendOrderReceivedNotification();
	PrepareInvoice();
	SendInvoice();
	PickGoodsFromShelf();
	UpdateStockControl();
	PackGoods();
	ShipGoods();
	SendDispatchedNotification();
}

In here, we have a whole bunch of different methods (tasks, code blocks, call them what you want). Some are dependent on others, some aren't. Let's see how it could be parallelised (pseudocode only):

public void Amazon()
{
	TakeOrder();
	
	in parallel do
		=> SendOrderReceivedNotification();
		=> DealWithInvoicing();
		=> DealWithTheGoods();
}

public void DealWithInvoicing()
{
	PrepareInvoice();
	SendInvoice();
}

public void DealWithTheGoods()
{
	PickGoodsFromShelf();

	in parallel do
		=> UpdateStockControl();
		=> SendGoods();
}

public void SendGoods()
{ 
	PackGoods();
	ShipGoods();
	SendDispatchedNotification();
}

A bit more code, but still readable (I'd actually argue a bit more readable since the first method was, IMO, doing way too much stuff). Basically all we've done is divide the tasks into those that are dependent and those that aren't. For the independent tasks, we're using a new "in parallel do" construct to indicate to the language / runtime that these can be run on different threads. In the new code, the longest chain from start to completion is 5 steps compared to the 9 steps in the sequential code, so we should expect some speedup when run on a multi-core system.

How much speedup? Since we've dropped from 9 steps to 5, does that indicate that we should now be almost twice as fast? Clearly not, since each step is unlikely to have the same sequential execution time. Let me introduce Gene Amdahl who formulated the fundamental limits to what parallelisation could achieve. In essence, he stated that the maximum speedup that can be achieved through concurrency is limited by the sequential part of the program. That is, if you have a program that takes 10 hours to run and within that there is a task of 2 hours that cannot be parallelised, then the fastest that program can run, regardless of the number of processors that can be thrown at it, is 2 hours. Not exactly rocket science, but it earned the title of Amdahl's Law; go take a look if you want to see the maths (it's not hard). Data Parallelism enjoys the fact that the sequential parts can be very small, and so the possible speedups can be truly enormous. Task parallelism is more restricted, in that it's limited to how fast the longest (in time, not code) dependent chain of tasks can run.

If anyone's reading all this, are you spotting a theme yet? Concurrency is important (and will get more so), but dependencies are the problem. Dependencies introduce the bottleneck beyond which you're relying on the hardware to improve it's sequential execution speed to see improvements. And we've already seen that that's unlikely. Dependencies are also the thing that cause you to start dropping locks and other synchronisation mechanisms in your code, obscuring your "business rules" and introducing the risk of hard-to-test, hard-to-diagnose bugs. Loosely coupled, independent code is something that you should strive for, and immutable data structures assist greatly in this. I'm thinking that perhaps the "I" in SOLID could be re-purposed...

That should give an idea as to what Task Parallelism is all about. In the next post, we'll look at how to do this in .Net 4.0.