Types of Parallelism

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.

4 thoughts on “Types of Parallelism”

  1. Nice explanation :)

    I designed and built a solution that had exactly this kind of problem – it was a problem that was this straightforward. We were required to encode & protect musicflim content ready for sale and this involved a multi-step process were certain steps were considerably long than others and would have caused bottleneck if a combination of both ‘data’ & ‘task’ parallelism weren’t used.

    Ollie

    Like

  2. I was thinking about similar thing a few weeks back.

    Why is it that our programming languages haven’t evolved to an extent where – it should not be evident that we are doing any parallel work. Just the way, we as human do things in parallel mode.

    Isn’t it sad that we still need to learn multi-threading as a separate topic?

    Also, language such as c# has static typing & python/ruby has dynamic typing.

    Can’t we have single data type for numbers & natural way to get results?
    e.g.
    number x = 3;
    number y = 2;
    number z = 3 / 2; (would result 1.5)

    No need to do a cast for that matter.
    What do you say?

    Like

  3. Multi-threading being explicit: No, I like the fact that you have to be explicit about it. The developer has more knowledge than the system about what is parallelisable. The system can *support* that better (and will do, through things like Parallel Extensions) but I think it still needs to be explicit.

    Typing: again, no, I want to know whether I’m doing integer arithmetic or not.

    Jon

    Like

  4. Another issue with task parallelism and dependencies is overflowwing the pipeline. For instance assume you had 3 threads with equal priority for this problem and each one did the respective task (thread1 make tin, etc). Thread2 can start as soon as Thread1 finishes the first tin. But thread2 cannot process the second tin until it finishes cooking the first. In that time Thread1 will have made 12 more tins. Thread2 won’t be able to catch up to this number and hence Thread1 is potentially doing wasted work (Unless of course Thread1 has a sweet contract and can take off 4 days a week thus allowing Thread2 time to catch up :) ).

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s