This chapter is from the book
This chapter is from the book
This chapter is from the book
4.5 THE DIVIDE AND CONQUER PATTERN
Problem
Suppose the problem is formulated using the sequential divide-and-conquer strategy. How can the potential concurrency be exploited?
Context
The divide-and-conquer strategy is employed in many sequential algorithms. With this strategy, a problem is solved by splitting it into a number of smaller subproblems, solving them independently, and merging the subsolutions into a solution for the whole problem. The subproblems can be solved directly, or they can in turn be solved using the same divide-and-conquer strategy, leading to an overall recursive program structure.
This strategy has proven valuable for a wide range of computationally intensive problems. For many problems, the mathematical description maps well onto a divide-and-conquer algorithm. For example, the famous fast Fourier transform algorithm [PTV93] is essentially a mapping of the doubly nested loops of the discrete Fourier transform into a divide-and-conquer algorithm. Less well known is the fact that many algorithms from computational linear algebra, such as the Cholesky decomposition [ABE+97, PLA], also map well onto divide-and-conquer algorithms.
The potential concurrency in this strategy is not hard to see: Because the sub-problems are solved independently, their solutions can be computed concurrently. Fig. 4.5 illustrates the strategy and the potential concurrency. Notice that each "split" doubles the available concurrency. Although the concurrency in a divide-and-conquer algorithm is obvious, the techniques required to exploit it effectively are not always obvious.
)
Figure 4.5 The divide-and-conquer strategy
Forces
-
The traditional divide-and-conquer strategy is a widely useful approach to algorithm design. Sequential divide-and-conquer algorithms are almost trivial to parallelize based on the obvious exploitable concurrency.
-
As Fig. 4.5 suggests, however, the amount of exploitable concurrency varies over the life of the program. At the outermost level of the recursion (initial split and final merge), there is little or no exploitable concurrency, and the subproblems also contain split and merge sections. Amdahl's law (Chapter 2) tells us that the serial parts of a program can significantly constrain the speedup that can be achieved by adding more processors. Thus, if the split and merge computations are nontrivial compared to the amount of computation for the base cases, a program using this pattern might not be able to take advantage of large numbers of processors. Further, if there are many levels of recursion, the number of tasks can grow quite large, perhaps to the point that the overhead of managing the tasks overwhelms any benefit from executing them concurrently.
-
In distributed-memory systems, subproblems can be generated on one PE and executed by another, requiring data and results to be moved between the PEs. The algorithm will be more efficient if the amount of data associated with a computation (that is, the size of the parameter set and result for each subproblem) is small. Otherwise, large communication costs can dominate the performance.
-
In divide-and-conquer algorithms, the tasks are created dynamically as the computation proceeds, and in some cases, the resulting "task graph" will have an irregular and data-dependent structure. If this is the case, then the solution should employ dynamic load balancing.
Example 4.6. Sequential pseudocode for the divide-and-conquer algorithm
func solve returns Solution; // a solution stage
func baseCase returns Boolean; // direct solution test
func baseSolve returns Solution; // direct solution
func merge returns Solution; // combine subsolutions
func split returns Problem[]; // split into subprobs
Solution solve(Problem P) {
if (baseCase(P))
return baseSolve(P);
else {
Problem subProblems[N]; Solution subSolutions[N];
subProblems = split(P);
for (int i = 0; i < N; i++)
subSolutions[i] = solve(subProblems[i]);
return merge(subSolutions);
}
}
Solution
A sequential divide-and-conquer algorithm has the structure shown in . The cornerstone of this structure is a recursively invoked function (solve ()) that drives each stage in the solution. Inside solve, the problem is either split into smaller subproblems (using split()) or it is directly solved (using baseSolve()). In the classical strategy, recursion continues until the subproblems are simple enough to be solved directly, often with just a few lines of code each. However, efficiency can be improved by adopting the view that baseSolve() should be called when (1) the overhead of performing further splits and merges significantly degrades performance, or (2) the size of the problem is optimal for the target system (for example, when the data required for a baseSolve() fits entirely in cache).
The concurrency in a divide-and-conquer problem is obvious when, as is usually the case, the subproblems can be solved independently (and hence, concurrently). The sequential divide-and-conquer algorithm maps directly onto a task-parallel algorithm by defining one task for each invocation of the solve() function, as illustrated in Fig. 4.7. Note the recursive nature of the design, with each task in effect dynamically generating and then absorbing a task for each subproblem.
)
Figure 4.7 Parallelizing the divide-and-conquer strategy. Each dashed-line box represents a task.
At some level of recursion, the amount of computation required for a subproblems can become so small that it is not worth the overhead of creating a new task to solve it. In this case, a hybrid program that creates new tasks at the higher levels of recursion, then switches to a sequential solution when the subproblems become smaller than some threshold, will be more effective. As discussed next, there are tradeoffs involved in choosing the threshold, which will depend on the specifics of the problem and the number of PEs available. Thus, it is a good idea to design the program so that this "granularity knob" is easy to change.
Mapping tasks to UEs and PEs
Conceptually, this pattern follows a straightforward fork/join approach (see the Fork/Join pattern). One task splits the problem, then forks new tasks to compute the subproblems, waits until the subproblems are computed, and then joins with the subtasks to merge the results.
The easiest situation is when the split phase generates subproblems that are known to be about the same size in terms of needed computation. Then, a straightforward implementation of the fork/join strategy, mapping each task to a UE and stopping the recursion when the number of active subtasks is the same as the number of PEs, works well.
In many situations, the problem will not be regular, and it is best to create more, finer-grained tasks and use a master/worker structure to map tasks to units of execution. This implementation of this approach is described in detail in the Master/Worker pattern. The basic idea is to conceptually maintain a queue of tasks and a pool of UEs, typically one per PE. When a subproblem is split, the new tasks are placed in the queue. When a UE finishes a task, it obtains another one from the queue. In this way, all of the UEs tend to remain busy, and the solution shows a good load balance. Finer-grained tasks allow a better load balance at the cost of more overhead for task management.
Many parallel programming environments directly support the fork/join construct. For example, in OpenMP, we could easily produce a parallel application by turning the for loop of into an OpenMP parallel for construct. Then the subproblems will be solved concurrently rather than in sequence, with the OpenMP runtime environment handling the thread management. Unfortunately, this technique will only work with implementations of OpenMP that support true nesting of parallel regions. Currently, only a few OpenMP implementations do so. Extending OpenMP to better address recursive parallel algorithms is an active area of research in the OpenMP community [Mat03]. One proposal likely to be adopted in a future OpenMP specification is to add an explicit taskqueue construct designed to support the expression of recursive algorithms [SHPT00].
The FJTask framework for Java [Lea00b, Lea] provides support for fork/join programs with a pool of threads backing the implementation. Several example programs using a divide-and-conquer strategy are provided with the package.
Communication costs
Because tasks are generated dynamically from a single top-level task, a task can be executed on a different PE than the one that generated it. In a distributed-memory system, a higher-level task will typically have the data necessary to solve its entire problem, the relevant data must be moved to the subproblem's PE, and the result moved back to the source. Thus it pays to consider how to efficiently represent the parameters and results, and consider whether it makes sense to replicate some data at the beginning of the computation.
Dealing with dependencies
In most algorithms formulated using the divide-and-conquer strategy, the subproblems can be solved independently from each other. Less commonly, the subproblems require access to a common data structure. These dependencies can be handled using the techniques described in the Shared Data pattern.
Other optimizations
A factor limiting the scalability of this pattern is the serial split and merge sections. Reducing the number of levels of recursion required by splitting each problem into more subproblems can often help, especially if the split and merge phases can be parallelized themselves. This might require restructuring, but can be quite effective, especially in the limiting case of "one-deep divide and conquer", in which the initial split is into P subproblems, where P is the number of available PEs. Examples of this approach are given in [Tho95].
Examples
Mergesort
Mergesort is a well-known sorting algorithm based on the divide-and-conquer strategy, applied as follows to sort an array of N elements.
-
The base case is an array of size less than some threshold. This is sorted using an appropriate sequential sorting algorithm, often quicksort.
-
In the split phase, the array is split by simply partitioning it into two contiguous subarrays, each of size N/2.
-
In the solve-subproblems phase, the two subarrays are sorted (by applying the mergesort procedure recursively).
-
In the merge phase, the two (sorted) subarrays are recombined into a single sorted array.
This algorithm is readily parallelized by performing the two recursive mergesorts in parallel.
This example is revisited with more detail in the Fork/Join pattern in the Supporting Structures design space.
Matrix diagonalization
Dongarra and Sorensen ([DS87]) describe a parallel algorithm for diagonalizing (computing the eigenvectors and eigenvalues of) a symmetric tridiagonal matrix T. The problem is to find a matrix Q such that QT · T · Q is diagonal; the divide-and-conquer strategy goes as follows (omitting the mathematical details).
-
The base case is a small matrix which is diagonalized sequentially.
-
The split phase consists of finding matrix T′ and vectors u, v, such that T = T′ + uvT, and T′ has the form
where T1 and T2 are symmetric tridiagonal matrices (which can be diagonalized by recursive calls to the same procedure).
-
The merge phase recombines the diagonalizations of T1 and T2 into a diagonalization of T.
)
Details can be found in [DS87] or in [GL96].
Known uses
Any introductory algorithms text will have many examples of algorithms based on the divide-and-conquer strategy, most of which can be parallelized with this pattern.
Some algorithms frequently parallelized with this strategy include the Barnes-Hut [BH86] and Fast Multipole [GG90] algorithms used in N-body simulations; signal-processing algorithms, such as discrete Fourier transforms; algorithms for banded and tridiagonal linear systems, such as those found in the ScaLAPACK package [CD97, Sca]; and algorithms from computational geometry, such as convex hull and nearest neighbor.
A particularly rich source of problems that use the Divide and Conquer pattern is the FLAME project [GGHvdG01]. This is an ambitious project to recast linear algebra problems in recursive algorithms. The motivation is twofold. First, mathematically, these algorithms are naturally recursive; in fact, most pedagogical discussions of these algorithms are recursive. Second, these recursive algorithms have proven to be particularly effective at producing code that is both portable and highly optimized for the cache architectures of modern microprocessors.
Related Patterns
Just because an algorithm is based on a sequential divide-and-conquer strategy does not mean that it must be parallelized with the Divide and Conquer pattern. A hallmark of this pattern is the recursive arrangement of the tasks, leading to a varying amount of concurrency and potentially high overheads on machines for which managing the recursion is expensive. If the recursive decomposition into sub-problems can be reused, however, it might be more effective to do the recursive decomposition, and then use some other pattern (such as the Geometric Decomposition pattern or the Task Parallelism pattern) for the actual computation. For example, the first production-level molecular dynamics program to use the fast multipole method, PMD [Win95], used the Geometric Decomposition pattern to parallelize the fast multipole algorithm, even though the original fast multipole algorithm used divide and conquer. This worked because the multipole computation was carried out many times for each configuration of atoms.