O'Reilly logo

Algorithms and Parallel Computing by Fayez Gebali

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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.

c07f002

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 = 23, the divide-and-conquer technique progresses through three iterations and the size of the subtask allocated to each processor is

(7.18) c07e018

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, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required