parallel
bound running time
Work Load \(W\): total work
Depth \(D\): the depth of algorithm (how parallel the this algorithm is)
Running Time \(\frac{W}{p} \leq T_p\leq \frac{W}{p}+D\)
这个深度不好理解, 他说的是序列操作对于前面序列操作的依赖链长度
比如, \(n\) 个数线性取最大值, 每个数与 max 变量取最大, 当前第 \(i\) 步的最大值与之前 \(i-1\) 个数有依赖, 所以 \(D=O(n)\)
ranking
binary search
\(W=O(n\log n), D=O(\log n)\)
sequential
i = j = 0;
while ( i <= n || j <= m ) {
if ( A(i+1) < B(j+1) )
RANK(++i, B) = j;
else RANK(++j, A) = i;
}
++i 说明当前状态对于之前有依赖
\(W=D=O(n+m)\)
parallel ranking
先分割成 \(p=n/\log n\) 组, 取等间隔 \(p\) 个分隔点, 求出他们在另一个数组中的 ranking
使用二分, \(D=O(\log n), W=O(p\log n)=O(n)\)
再将分割出的最多 \(2p\) 组, 每组最多 \(m=O(\log n)\) 个元素
线性合并, \(D=O(m)=O(\log n), W=O(pm)=O(n)\)
max finding
binary tree
\(W=O(n),D=O(\log n)\)
comparing all pairs
\(D=O(1),W=O(n^2)\)
double-log
-
按 \(\sqrt n\) 分割, 递归到底
处理合并每层的 \(\sqrt n\) 个组, 可以用全部对比的方式
\(D=O(1),W=O({\sqrt n}^2)=O(n)\)
\(\therefore D(n)=D(\sqrt n)+O(1), W(n)=\sqrt n W(\sqrt n)+O(n)\)
\(D(n)=O(\log\log n), W(n)=O(n\log\log n)\) 2. 先按 \(h=\log\log n\) 分割一步
每一组有 \(O(h)\) 个元素, 暴力取最大值
这里用的不是全部对比, 而是单纯依次与
max变量比较取最大值由于这个操作第 \(i\) 步对前 \(i-1\) 步是有线性依赖的, 所以 \(D=W=O(h)\)
\(n/h\) 组的总 \(W=O(h\times (n/h))\)
再按 \(\sqrt n\) 处理这 \(n/h\) 组
\(D(n)=O(h+\log\log(n/h))=O(\log\log n)\)
\(W(n)=O(h\times(n/h)+(n/h)\log\log(n/h))=O(n)\)
random sampling
-
随机取出 \(n^{7/8}\) 个元素
\(D=O(1),W=O(n^{7/8})\) 2. 分成 \(n^{3/4}\) 组, 每组 \(n^{1/8}\) 个元素
用全对比找每组的最大值, \(D=O(1),W=O((n^{1/8})^2)=O(n^{1/4})\)
总的 \(W=O(n^{1/4}\times n^{3/4})=O(n)\) 3. 分成 \(n^{1/2}\) 组, 每组 \(n^{1/4}\) 个元素
用全对比找每组的最大值, \(D=O(1),W=O((n^{1/4})^2)=O(n^{1/2})\)
总的 \(W=O(n^{1/2}\times n^{1/2})=O(n)\) 4. 最后剩下 \(n^{1/2}\) 个元素(组), 直接全对比查找
总的 \(D=O(1),W=O(n)\)