Decomposing a Problem for Parallelism
Determining when, where, and how to incorporate multiprocessing and multithreading into the software development effort is what is of the utmost importance in utilizing multiple cores. Which brings us to two of the primary questions:
- How will I know when my software application needs multicore programming?
- How will I know where to put the multicore programming in my piece of software?
Decomposition is the process of breaking down a problem or solution into its fundamental parts. Sometimes the parts are grouped into logical areas (i.e., searching sorting, calculating, input, output, etc.) In other situations the parts are grouped by logical resource (processor, database, communication, etc.) The decomposition of the software solution amounts to the Work Breakdown Structure (WBS) or its Architectural Artifacts(AA). The WBS determines which piece of software does what. The AA determines what concepts or things a software solution is divided into. The WBS typically reflects a procedural decomposition where as the AA represents an object oriented decomposition. Unfortunately, there is no cookbook approach to identifying the WBS or the AA of a software solution. We can say that model driven decomposition is one of the most practical approaches. We shall have much to say about models throughout this book. We cannot talk about where to use threads or whether to use simultaneously executing processes in the software solution until we have decomposed both the problem and the solution. Problem and solution decompositions are typically performed during the analysis and design activities in the SDLC (Software Development Life Cycle). A successful decomposition is one of the primary ingredients of a successful software development effort. On the other hand a poor or inappropriate problem and solution breakdown will almost certainly lead to failed software. The need or opportunity for multithreading or multiprocessing is most often discovered during the decomposition activity.
To see what we mean by decomposition let's take as a simple example the problem of a painting the house before the guests arrive for the holidays. Of course we will take this opportunity to use the latest craze in software automated painters. Let's see how we might decompose the problem of painting the house as well as the solution. The problem could be broken down into two approaches for decomposing this problem and creating possible solutions:
We can quickly see part of the challenge of decomposition. The first observation to be made verifies the fact that there is typically more than one way to decompose the problem. As you look at the problem and solution breakdown, you may have had a very different set of steps in mind. In fact we could have chosen an entirely different approach to the problem of painting the house before the guests arrive for the holidays as demonstrated in Decomposition #2.
The second observation to be made is that a decomposition might be incomplete or inappropriate! Ideally the fundamental parts of a decomposition should collectively represent the initial problem or solution. It's like putting the pieces of a puzzle back together again. If the pieces don't collectively represent the whole then the decomposition is incomplete. This means we haven't captured the entire problem and we won't have the entire solution. In our painting the house problem, was identifying the amount or cost of the paint part of the original problem? We can't tell from the statement of the problem. So we don't know if Decomposition #1 or #2 were incomplete. On the other hand it is clear that we need to paint the house before the guests arrive. Problem and solution Decomposition #1 does not address the guests arrival at all. So it is not clear whether the solution in Decomposition #1 will be acceptable. While Decomposition #2 does attempt to address the arrival of the guests, the problem and solution is geared towards finding ways not to paint the house at all or to paint as few walls as possible. This decomposition may be inappropriate. It might reflect a poor understanding of the intent of the initial problem.
Let us also point out that in the solution for Decomposition #1 a single automated software painter is suggested, and in Decomposition #2 multiple automated software painters were chosen. So not only does Decomposition #2 seek to minimize the number of walls to be painted it attempts to do so as fast as possible. Appropriate decomposition is a primary challenge for applications based on the sequential model. It is even more on an issue where parallel processing is called for. There are software tools and libraries that can help the developer with implementing a decomposition, however the process itself remains part of the problem solving and design activity. Until we get the problem and solution breakdown right, the application of multithreading or multiprocessing will be murky.
Earlier, we defined decomposition as the process of breaking down a problem or solution into its fundamental parts. But what are the fundamental parts of a problem or solution? The answer depends on what model you will use to represent the problem and the solution. One of the challenges of software decomposition is that there are multiple ways to represent a problem and its solution. It could also be reasonably argued that there is no one right way to decompose a problem or a solution. So which decomposition should we choose? Another challenge is making sure the decomposition is complete, appropriate, and correct. But how will we know if the breakdown is right? In some cases its not a matter of choosing between multiple and possibly conflicting WBS, it is a matter of coming up with any decomposition at all. This might be due to the complexity of the original problem. The decomposition issue is front and center in any software development effort. It's especially important where parallel processing tools or techniques will be deployed. But the WBS or AA chosen rely on the idea of models. Wherever decomposition takes place there is always one or more models in the vicinity. Hiding beneath the surface of our choices in Decomposition #1 and #2 is an assumed and shared model.
This excerpt appeared in our book Professional Multicore Programming, Chapter 3, Wrox, 2008