Parallelism in .NET – Part 1, Decomposition

The first step in designing any parallelized system is Decomposition.  Decomposition is nothing more than taking a problem space and breaking it into discrete parts.  When we want to work in parallel, we need to have at least two separate things that we are trying to run.  We do this by taking our problem and decomposing it into parts.

There are two common abstractions that are useful when discussing parallel decomposition: Data Decomposition and Task Decomposition.  These two abstractions allow us to think about our problem in a way that helps leads us to correct decision making in terms of the algorithms we’ll use to parallelize our routine.

To start, I will make a couple of minor points.

  • I’d like to stress that Decomposition has nothing to do with specific algorithms or techniques.  It’s about how you approach and think about the problem, not how you solve the problem using a specific tool, technique, or library.  Decomposing the problem is about constructing the appropriate mental model: once this is done, you can choose the appropriate design and tools, which is a subject for future posts.
  • Decomposition, being unrelated to tools or specific techniques, is not specific to .NET in any way.  This should be the first step to parallelizing a problem, and is valid using any framework, language, or toolset.  However, this gives us a starting point – without a proper understanding of decomposition, it is difficult to understand the proper usage of specific classes and tools within the .NET framework.

Data Decomposition is often the simpler abstraction to use when trying to parallelize a routine.  In order to decompose our problem domain by data, we take our entire set of data and break it into smaller, discrete portions, or chunks.  We then work on each chunk in the data set in parallel.

This is particularly useful if we can process each element of data independently of the rest of the data.  In a situation like this, there are some wonderfully simple techniques we can use to take advantage of our data.  By decomposing our domain by data, we can very simply parallelize our routines.  In general, we, as developers, should be always searching for data that can be decomposed.

Finding data to decompose if fairly simple, in many instances.  Data decomposition is typically used with collections of data.  Any time you have a collection of items, and you’re going to perform work on or with each of the items, you potentially have a situation where parallelism can be exploited.  This is fairly easy to do in practice: look for iteration statements in your code, such as for and foreach.

Granted, every for loop is not a candidate to be parallelized.  If the collection is being modified as it’s iterated, or the processing of elements depends on other elements, the iteration block may need to be processed in serial.  However, if this is not the case, data decomposition may be possible.

Let’s look at one example of how we might use data decomposition.  Suppose we were working with an image, and we were applying a simple contrast stretching filter.  When we go to apply the filter, once we know the minimum and maximum values, we can apply this to each pixel independently of the other pixels.  This means that we can easily decompose this problem based off data – we will do the same operation, in parallel, on individual chunks of data (each pixel).

Task Decomposition, on the other hand, is focused on the individual tasks that need to be performed instead of focusing on the data.  In order to decompose our problem domain by tasks, we need to think about our algorithm in terms of discrete operations, or tasks, which can then later be parallelized.

Task decomposition, in practice, can be a bit more tricky than data decomposition.  Here, we need to look at what our algorithm actually does, and how it performs its actions.  Once we have all of the basic steps taken into account, we can try to analyze them and determine whether there are any constraints in terms of shared data or ordering.  There are no simple things to look for in terms of finding tasks we can decompose for parallelism; every algorithm is unique in terms of its tasks, so every algorithm will have unique opportunities for task decomposition.

For example, say we want our software to perform some customized actions on startup, prior to showing our main screen.  Perhaps we want to check for proper licensing, notify the user if the license is not valid, and also check for updates to the program.  Once we verify the license, and that there are no updates, we’ll start normally.  In this case, we can decompose this problem into tasks – we have a few tasks, but there are at least two discrete, independent tasks (check licensing, check for updates) which we can perform in parallel.  Once those are completed, we will continue on with our other tasks.

One final note – Data Decomposition and Task Decomposition are not mutually exclusive.  Often, you’ll mix the two approaches while trying to parallelize a single routine.  It’s possible to decompose your problem based off data, then further decompose the processing of each element of data based on tasks. 

This just provides a framework for thinking about our algorithms, and for discussing the problem.

About Reed
Reed Copsey, Jr. - http://www.reedcopsey.com - http://twitter.com/ReedCopsey

Comments

12 Responses to “Parallelism in .NET – Part 1, Decomposition”
  1. Great article,

    made absolute sense to me! I’ve got a feeling this is leading to a very interesting refreshing way of thinking and programming. (at least for me)

  2. Reed says:

    Caspar,

    Glad to hear it! I’m actually having a lot of fun with this – I’ve been wanting to write about parallelism in depth for a while… I hope the series continues to be useful for you.

    -Reed

  3. Sachin says:

    Great article. I was looking for good and simple artilce on PLINQ and you really made a simple and effective article… Its going to be interesting to read this series.

  4. Cyril Gupta says:

    Excellent series Reed! I wanted to use the Task Parallel library in my latest project but when I tried to look for it (in .Net framework 3.5) there wasn’t any task class in the Threading namespace.

    I thought you said it had been back-included in 3.5 sp1?

    I am now changing over to .Net 4.

    • Reed says:

      Cyril,

      Although I love VS 2010 RC and .NET 4, you can use this in .NET 3.5sp1. It requires installing the Rx Framework, available at:

      http://msdn.microsoft.com/en-us/devlabs/ee794896.aspx

      The Rx Framework includes a backport of nearly all of the Task Parallel Library and PLINQ. (The differences are mainly differences in the ThreadPool – the backport uses .NET 3.5’s ThreadPool, which is not as feature-rich as .NET 4’s ThreadPool.)

      -Reed

  5. Tariq Azam says:

    I wish i would have discovered it earlier. Great work Reed.

  6. Angel Eyes says:

    Thanks, that was very clear and concise. I’m going to read on about the tasks, and all the way to csharp 5.0 and async

Trackbacks

Check out what others are saying about this post...
  1. [...] my discussion of Decomposition of the problem space, I mentioned that Data Decomposition is often the simplest abstraction to use [...]

  2. [...] working with a problem that can be decomposed by data, we have a collection, and some operation being performed upon the collection.  I’ve [...]

  3. [...] tasks can be decomposed using a Data Decomposition approach, but often, this is not appropriate.  Frequently, [...]

  4. […] Part 1, Decomposition  […]



Speak Your Mind

Tell us what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!