Parallel Programming Patterns
For years object-oriented programmers have been using design patterns to logically design their applications. Parallel programming is no different than object-oriented programming -- parallel programming problems generally fall into one of several well-known patterns. A few of the more common parallel programming patterns and their relationship to the aforementioned decompositions are in Table 2.
In this section, we provide a brief overview of each pattern and the types of problems that each pattern may be applied to.
- Task-level Parallelism Pattern. In many cases, the best way to achieve parallel execution is to focus directly on the tasks themselves. In this case, the task-level parallelism pattern makes the most sense. In this pattern, the problem is decomposed into a set of tasks that operate independently. It is often necessary remove dependencies between tasks or separate dependencies using replication. Problems that fit into this pattern include the so-called embarrassingly parallel problems, those where there are no dependencies between threads, and replicated data problems, those where the dependencies between threads may be removed from the individual threads.
- Divide-and-Conquer Pattern. In the divide-and-conquer pattern, the problem is divided into a number of parallel sub-problems. Each sub-problem is solved independently. Once each subproblem is solved, the results are aggregated into the final solution. Since each sub-problem can be independently solved, these sub-problems may be executed in a parallel fashion.
The-divide-and conquer approach is widely used on sequential algorithms such as merge sort. These algorithms are very easy to parallelize. This pattern typically does a good job of load balancing and exhibits good locality; which is important for effective cache usage.
- Geometric Decomposition Pattern. The geometric decomposition pattern is based on the parallelization of the data structures used in the problem being solved. In geometric decomposition, each thread is responsible for operating on data "chunks". This pattern may be applied to problems such as heat flow and wave propagation.
- Pipeline Pattern. The idea behind the pipeline pattern is identical to that of an assembly line. The way to find concurrency here is to break down the computation into a series of stages and have each thread work on a different stage simultaneously.
- Wavefront Pattern. The wavefront pattern is useful when processing data elements along a diagonal in a two-dimensional grid. This is shown in Figure 1.
The numbers in Figure 1 illustrate the order in which the data elements are processed. For example, elements in the diagonal that contains the number 3 are dependent on data elements 1 and 2 being processed previously. The shaded data elements in Figure 1 indicate data that has already been processed. In this pattern, it is critical to minimize the idle time spent by each thread. Load balancing is the key to success with this pattern.
For a more extensive and thorough look at parallel programming design patterns, see Patterns for Parallel Programming, by Timothy Mattson et al.
