Algorithms and Parallel Computing

7.8 DIVIDE-AND-CONQUER (RECURSIVE PARTITIONING) STRATEGIES

Divide-and-conquer techniques partition the problem into subtasks of the same size, but it iteratively keeps repeating this process to obtain yet smaller problems. In that sense, divide and conquer iteratively applies the problem partitioning technique as shown in Fig. 7.2. Divide and conquer is sometimes called recursive partitioning. Typically, the problem size N is an integer power of 2 and the divide-and-conquer technique halves the problem into two equal parts during each iteration.

Figure 7.2 Divide-and-conquer technique iteratively partitions the problem into N equal-sized subtasks. In this case, N = 8.

Let us apply the divide-and-conquer technique to the problem of adding K numbers in Eq. 7.10. Assume that we have N = 8 processors. Since N = 2³, the divide-and-conquer technique progresses through three iterations and the size of the subtask allocated to each processor is

(7.18)

Figure 7.3 shows how adding the K numbers progresses among the processors. The size of the smallest task allocated to each processor is s = 128/8 = 16. Thus, each processor has to add 16 numbers. This is shown at the bottom of the diagram at level 0. At the end of processing at level 0, N = 8 temporary results are produced. At level 1, ...