[Parallel Algo.] 9. Partition

Parallel Algorithm

9. Partition

Main idea

      [1] Break up the given problem into p independent subproblems of almost equal size
          將問題分成p個獨立且大小幾乎一樣的子問題

     [2] Solve the p subproblems concurrently, where p is the number of processors available
          同時解決p個問題，其中p是可使用的processor數量

      Next, We discuss the difference between D&G and Partition:
      接下來，我們討論其和Ｄ＆Ｇ的不同

      Divide-and-conquer: usually lies in the merging of sub-solutions
                                       通常倚賴在子結果的整合上

      Partition: lies in carefully partitioning the problem into independent sub-problems
                     倚賴在如何把問題分成獨立的子問題

Example: Merging

      Input: two sorted sequences A[1...n] and B[1...n] 
      Output: a sorted sequence C[1...2n]

(RA[i] be the rank of A[i] in B (the number of values <= A[i] in B.) RB[i] is defined similarly. )

Stage 1, Determine RA[i x m], 1 <= i <= n/m. Then, partition A and B into Ai's and Bi's respectively, where Ai = {A[(i–1) x m+1], ..., A[i x m]} and Bi = {B[RA[(i–1) x m]–((i– 1) x m)+1], ..., B[RA[i x m]–i x m]}. 

Stage 2, For each pair of Ai and Bi, 1 <= i <= n/m, if |Bi|=O(log n), then rank all elements in Ai and Bi sequentially. Otherwise, apply the partition technique used in stage 1 to partition Ai and Bi into Ai,j's and Bi,j's of size O(log n) (in this case, Bi plays the role of A and Ai plays the role of B). And then, for each pair of Ai,j and Bi,j, rank all elements in Ai,j and Bi,j sequentially.

 

Remark:

The merge problem can be viewed as that of determining RA[1...n] and RB[1...n]. For simplicity, assume that all elements in A and B are distinct.