Cross Rails

Parallel Programming for your grandmother

In the world of programming, parallel programming is mostly translated to multi-threading.
Thread is an abstract concept that can be seen as a worker which can accomplish tasks in a computer. For example if you want to execute a method like Add(2,3), you can assign this task to a thread and wait for the result. The thread execute some instructions on CPU to carry out the result.

So threads are like people! They can do some tasks using the available resources like CPU, Memory, Network and ... Just like humans that can do some jobs using their brain, memory and …

To make things simpler, I am going to use humans to model parallel computing, instead of using thread concept.

Here in this post, I want to separate 2 concepts: Parallelism and Asynchrony

Parallel Programming

Consider you are in a grocery store with a shopping list in your hand (written by your wife!). You should find all those 50 items alone and collect them into the tray.

Sequential Solution

A sequential solution would be finding all those items yourself alone. So the algorithm would be:

1.   Find item 1 and put it in the tray.
2.   Find item 2 and put it in the tray.
3.   Find item 3 and put it in the tray.
      .
      .
      .
200. Find item 50 and put it in the tray.
Parallel Solution

Now, consider you are not alone. You went to the grocery store with 10 of your friends and you are going to manage them to collect the items. You could split your list into 10 sublists and assign each sublist to one of your friends. So a parallel solution would be:

1.    Split the list into 10 sublists (each containing 20 items).
2.    Assign sublist 1 to Jim.
3.    Assign sublist 2 to Jane.
4.    Assign sublist 3 to Mark.
        .
        .
        .
11.   Assign sublist 10 to Mehran.
12.   Wait for people to finish their job.

But what if the sublists for Jim and Jane are easier than others to collect? For example Jim's sublist contains just fruits, which all are available at the fruit section and can be collected in just 1 minute. And some lists are harder to collect. For example the sublist for Mehran contains:

  • Apple
  • Shoe
  • Ball
  • Shampoo
  • Sugar

Poor Mehran! Although his list contains 5 items same as others, but his list is really harder as his items are distributed all over the store. Using the parallel algorithm as stated above, after 3 minutes all of people will finish their jobs, but Mehran is not! All other people are waiting for him to finish his job, and worse, they are not even helping him despite they could.

Better Parallel Solution

What is the problem with previous solution? Although the size of the lists are fixed and same (5 items for all people), but finding various items takes different times as they are located in different locations in the store. If we knew the required time to find each item, we could create some smarter sublists. For example if finding ball takes 5 minutes and finding Potato takes 1 minute, we could put them in one list and finally balance all lists. But unfortunately, we have not that information. We have not any knowledge about the amount of time required to find each item when we enter the store. As finding a more optimized solution is not the topic of this post I don't want to discuss about possible solutions here. But you can challenge yourself and use your creativity to find some.

Asynchronous Programming

Doing some tasks asynchronously is not exactly equal to doing them in parallel. In fact, parallel is just one of the solutions to achieve asynchrony, an expensive solution! Here I describe why is it an expensive solution.

Parallel Programming is an expensive solution to achieve Asynchronous Programming.

To describe asynchronous programming and its relation to parallel programming, I found Eric Lippert's interview very interesting (You can find the full discussion here). So I selected a part of it and just pasted here:

An analogy might help. Suppose you’re in a restaurant kitchen. Two orders come in, one for toast and one for eggs.
A synchronous workflow would be: put the bread in the toaster, wait for the toaster to pop, deliver the toast, put the eggs on the grill, wait for the eggs to cook, deliver the eggs. The worker – you – does nothing while waiting except sit there and wait.
An asynchronous but non-parallel workflow would be: put the bread in the toaster. While the toast is toasting, put the eggs on the grill. Alternate between checking the eggs, checking the toast, and checking to see if there are any new orders coming in that could also be started.
Whichever one is done first, deliver first, then wait for the other to finish, again, constantly checking to see if there are new orders.

An asynchronous parallel workflow would be: you just sit there waiting for orders. Every time an order comes in, go to the freezer where you keep your cooks, thaw one out, and assign the order to them. So you get one cook for the eggs, one cook for the toast, and while they are cooking, you keep on looking for more orders. When each cook finishes their job, you deliver the order and put the cook back in the freezer.

You’ll notice that the second mechanism is the one actually chosen by real restaurants because it combines low labor costs – cooks are expensive – with responsiveness and high throughput. The first technique has poor throughput and responsiveness, and the third technique requires paying a lot of cooks to sit around in the freezer when you really could get by with just one.

In the Eric's interview there is a good quote too:

Parallelism is one technique for achieving asynchrony, but asynchrony does not necessarily imply parallelism. -Eric Lipert

Parallel vs. Asynchronous

Most of the time when I want to utilize threads in a piece of code, I ask myself what kind of problem do I want to solve? Am I using threads to implement parallel programming, or I am over-using it to implement some asynchronous situation? Believe me, they are totally different.

When you want to use parallel programming, you are going to utilize the maximum number of threads that you can. You are optimizing the algorithms so the application can utilize more and more threads.

But when you want to use asynchronous programming, it is inverse! You want to use minimum threads for your tasks. The optimum solution is to use one thread to do all of your tasks asynchronously.

So, I suggest that if you want to write any code implying some parallel concept, keep this in mind:

Parallel programming is to use more and more threads effectively.
Asynchronous programming is to use less and less threads effectively.

About the author

Mehran Davoudi

A former technology geek! Currently a mentor and software architect, working as a consultant for companies with large scale software development.
Why dvd? Read about me (uɒɹɥəɯ)!

View all posts

5 Comments

  • When you already have employed labors to do the jobs (modern cpus have already 4 or more cores)
    Is it reasonable to do the jobs with just one of them??

  • In case you're asking why in async we try to use fewer threads: In a production system, the main concern is, for example, serving 1000 request/second. In this case, if each request uses the threads most efficiently (not holding them while blocking them) We could assign more threads to other requests resulting in a boost in performance.

  • Wow, I have read a lot of articles about this, but there was always something that wasn't clear to me. Now, thanks to you, Mehran, everything is fully understandable. It was very helpful! <3

Leave a Reply

Your email address will not be published. Required fields are marked *