设计并行算法的思路(2) parallel mergesort

Sequential Mergesort

func mergesort(A) |A| = n
   if n <= 1 return A
   (spawn)
   A1 = mergesort(A[1:n/2])
   A2 = mergesort(A[n/2+1:n])   
   (sync)
  return merge(A1,A2)

$T(n) = 2T(\frac{n}{2}) + O(n) = O(nlogn)$

$W_{pms} = 2W_{pms}(\frac{n}{2}) + O(n)$

$D_{pms}(n) = D_{mps}(\frac{n}{2}) + O(n)= O(n)$

work optimality(right)
polylog span(no)

那么应该如何提高效率呢？

我们可以看见这个算法的主要限制是merge的过程是顺序的，所以限制了算法的速度。那么有什么方式可以提高效率呢？

image

其实我们可以用在 A 序列中找到一个终点，并用它将 B 分成两部分使得 $a_{1} ,b_{1} \leq a_{m}\leq a_{2},b_{2}$

那么在最理想的情况下我们可以得到 $D_{pm}(n) = D_{pm}(\frac{n}{2})+O_{pm}(logn_{b})$ ,其中 log n 是二分查找 B的重点的过程。

在最坏的情况下，是 $\frac{n_A}{2}$ 与 $n_B$ merge的

$\left \lfloor{\frac{n_{A}}{2}}\right \rfloor + n_{B} \leq \frac{n_A}{2} + n_B$

$= \frac{n_A+n_B}{2} + \frac{n_B}{2}$

$= \frac{n}{2} + \frac{n_B}{2} \leq \frac{n}{2} + \frac{n}{4} = \frac{3n}{4}$

$D_{pm}(n) = D_{pm}(\frac{3n}{4})+O_{pm}(logn_{b}) = O(log^2n)$

$D_{pms}(n) = D_{mps}(\frac{n}{2}) + O(log^2n)= O(log^3n)$

设计并行算法的思路(2) parallel mergesort

推荐阅读更多精彩内容