When I was at TechEd, Joe Duffy mentioned task parallelism and data parallelism a number of times. It was easy enough to follow what he meant, but I had to keep consciously thinking about the terms instead of instinctively knowing what they meant. This post is intended to ram the point home to me as much as anyone else – there’s nothing like writing things up to make them stick in your head.

I thought I had a modicum of success with my “real life example” in the post about “push” LINQ, so I’ll use another one here. The difference is that I won’t be presenting any actual code in this post, just concepts.

Example situation: the soup factory

Suppose you run a soup factory, producing tins of tomato soup. Now, to simplify things massively, we’re going to assume there are three tasks:

1. Create empty tins. Each empty tin takes 5 minutes to make, and has 400ml volume.
2. Cook the soup in a big saucepan. It takes one person 1 hour (of constant stirring etc) to cook the soup, and the saucepan holds 20 litres.
3. Fill the tins with soup. It takes 2 minutes to fill a tin and seal it.

Obviously the numbers here are entirely arbitrary. They just give us something to play with. Now let’s look at different ways we can run the soup factory.

No parallelism: a single worker

We’ll start off with the simplest situation – a single worker, who will just perform one task at a time. Let’s look at how he might spend his time, starting at 8am:

Time	Activity
8:00-8:05	Make tin 1
8:05-8:10	Make tin 2
…
12:05-12:10	Make tin 50
12:10-13:10	Cook soup
13:10-13:12	Fill tin 1
13:12-13:14	Fill tin 2
…
14:48-14:50	Fill tin 50

Now, that’s just one way of doing it. He could have cooked the soup first, then made tin 1, filled tin 1, made tin 2, filled tin 2 etc. The only dependency is that we have both an empty tin and some soup before we fill the tin. Let’s give our worker a colleague and see how things can improve.

Just data parallelism: two workers doing the same thing

When we add a second worker, we can do organize things any number of ways, as we’ll see in a minute. However, we’ll stick to a simple way at the moment. Each of the workers will deal with 25 tins, and one will relax while the other is cooking.

Time	Activity
	Worker 1	Worker 2
8:00-8:05	Make tin 1	Make tin 2
8:05-8:10	Make tin 3	Make tin 4
…
10:00-10:05	Make tin 49	Make tin 50
10:05-11:05	Cook soup	Relax
11:05-11:07	Fill tin 1	Fill tin 2
11:07-11:09	Fill tin 3	Fill tin 4
…
11:53-11:55	Fill tin 49	Fill tin 50

This shows data parallelism. Both the “making tins” and “filling tins” tasks involve 50 tins which are each independent. We don’t need to wait for one tin to be full before starting another – with two people working, we can go twice as quickly. Note that this doesn’t hold for the cooking – two people cooking wouldn’t be able to get the work done any quicker.

With 50 people working like this, we’d have a total time of 1 hour and 7 minutes – five minutes of everyone making tins, one hour of soup cooking, and then two minutes of everyone filling tins. Now let’s try something different with our two workers. Adding extra workers at that point wouldn’t help.

Task parallelism: one person cooking while the other makes tins

We’ve seen that the cooking is the bottleneck – in our previous example, we were wasting time while the soup was cooking. We don’t want workers relaxing on the job! Let’s try a different kind of parallelism now – task parallelism, where instead of breaking a single task into multiple independent bits, we perform two wholly different tasks at the same time.

We’ll have one worker make tins while the other cooks soup. They can both fill tins afterwards.

Time	Activity
	Worker 1	Worker 2
8:00-8:05	Make tin 1	Start cooking soup
8:05-8:10	Make tin 2	Still cooking…
…
9:00-9:05	Make tin 13	Finished cooking – relax
12:05-12:10	Make tin 50	Still relaxing
12:10-12:12	Fill tin 1	Fill tin 2
12:12-12:14	Fill tin 3	Fill tin 4
…
12:58-13:00	Fill tin 49	Fill tin 50

This is actually worse than the previous time – but could be improved by the second worker helping to make tins after the soup has finished cooking. This time, if we went up to 51 workers we’d have the fastest possible time for a single batch – 1 hour and 2 minutes.

Dependencies and pipelines

I think that’s enough detailed examples – it should be enough to demonstrate the difference between the two types of parallelism. However, I’d like to consider one more aspect: dependencies. When using task parallelism, you need to be aware of what dependencies are involved. As noted earlier, there’s no dependency between making tins and cooking the soup, but filling the tins depends on there being an empty tin available, and being soup available. That’s what makes the minimum possible time for a single batch 1 hour and 2 minutes rather than just the “longest single task” of 1 hour for cooking the soup.

So, does that mean that n batches of soup will take n * (1 hour and 2 minutes) to create? No – because we can form a pipeline for the work. Suppose we can start cooking another load of soup while the first one is being used to fill tins. We can get our average time for a batch down to an hour, using 7 people: 1 person always cooking, 4 people always making tins, 1 person always filling tins and 1 person making a couple of tins and then filling for the rest of the hour. The time taken for the first batch is relatively high, but thereafter we can keep producing a new batch of 50 full tins every hour.

Few processes in computing are as straightforward as this “assembly line” – but it’s a useful model to remind us of the two types of parallelism possible.