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.
