14 Parallel Algorithm¶

文本统计：约 1760 个字 • 38 行代码

14.1 Introduction¶

并行：

Machine parallelism：硬件上的并行
Parallel algorithms：算法并行，这其中有两个模型，Parallel Random Access Machine (PRAM)模型 和 Work-depth measurement模型

并行算法，目的是利用cpu可以同时执行多条指令（通过流水线、多核、超长指令字等）的特性，合理调度指令的执行方式，使得工作量不增加的情况下减少运行时间。

14.1.1 PRAM¶

——Parallel Random Access Machine

每个单位时间每个处理器都只能执行一个操作，但是每个处理器可以并行地同时地进行操作。

冲突的类型

例子

如下所示的B定义为 B(迭代次数, 处理器编号)

具体算法：

for Pi ,  1 <= i <= n  pardo
  B(0, i) := A( i )
  for h = 1 to log n do
    if i <= n/2h
      B(h, i) := B(h-1, 2i-1) + B(h-1, 2i)
    else stay idle
  for i = 1: 
    output B(log n, 1); 
  for i > 1: stay idle

这样的时间开销为 \(T(n)=\log n+2\)

PRAM缺陷：会造成资源的浪费，因为并不是所有的处理器都需要工作；我们不知道某条指令分配给哪个处理器。

14.1.2 Work-Depth¶

PRAM是获得若干个处理器，那么在任务完成之前，这些处理器就算没有工作也不会释放。

而WD每一步都会去请求一些处理器来工作，这样可以减少资源的浪费。

14.2 衡量效率¶

Work load – total number of operations 总工作量: \(W(n)\)

Worst-case running time 时间复杂度: \(T(n)\)

Claim: A parallel algorithm with workload \(W\) and depth \(D\) can be implemented in \(W/p+ D\) time using p processors for any \(p > 0\).

设第 \(i\) 层的工作量为 \(W_i\)，则可以得到

\[ \begin{aligned} W&=\sum_{i=1}^DW_i\\ T_p&=\sum_{i=1}^D[\frac{W_i}{p}]+1\\ &=\sum_{i=1}^D[\frac{W_i}{p}]+D\le\sum_{i=1}^D\frac{W_i}{p}+D=\frac{W}{p}+D\\ &\ge\sum_{i=1}^D\frac{W_i}{p}=\frac{W}{p} \end{aligned} \]

从而我们完成证明

14.3 Prefix-Sums¶

问题描述：输入n个数，分别输出前k个数的和 (\(k=1,2,...,n\))

仍然构建出原来的二叉树：

定义C为，以当前节点为根节点，最右叶节点之前的和。比如B(3,1)的C就是前8个，比如B(1,3)的C就是前6个的和。

如果在左路径上，那么C值和B值相等；若一个节点是右儿子，那么C和父节点的值是一样的。

如果不是以上两种情况，那么C就是左边节点的C（左边节点的C值又=其父节点的C值）加上自身的B值。

我们自下而上算B，之后，自上而下算C。

代码：算B值的work load是 \(n+n/2+n/4+…+1=2n\)，算C值的 work load 仍然是 \(2n\)。其实可以通过观察二叉树的结点个数来看work load，一个node代表一个 work load。

//求B值
for Pi , 1 <= i <= n pardo
  B(0, i) := A(i)
for h = 1 to log n
  for i , 1 <= i <= n/2h pardo
    B(h, i) := B(h - 1, 2i - 1) + B(h - 1, 2i)

//求C值    
for h = log n to 0
    //右节点与父亲节点的值相同
    for i even, 1 <= i <= n/(2^h) pardo
        C(h, i) := C(h + 1, i/2)
    //左路径上的节点值与父亲相同
    for i = 1 pardo
        C(h, 1) := B(h, 1)
    //节点为父亲的左孩子，值为自身的值加上左边节点父亲的值
    for i odd, 3 <= i <= n/(2^h) pardo
        C(h, i) := C(h + 1, (i - 1)/2) + B(h, i)
for Pi , 1 <= i <= n pardo
  Output C(0, i)

这样的话 \(T(n)=O(\log n)\)，\(W(n)=O(n)\)

14.4 Merging¶

Merging – merge two non-decreasing arrays \(A(1), A(2), …, A(n)\) and \(B(1), B(2), …, B(m)\) into another non-decreasing array \(C(1), C(2), …, C(n+m)\)

分割法 Partitioning Paradigm：分割成若干个问题，这些问题互相之间没有依赖关系。

引入RANK来表示一个数组中的元素在另一个数组中的位置：

如果我们已经知道了RANK的值，那么例如A[i]最后的位置其实就是RANK（B数组中比他小的值的个数）+i（A数组中比他小的个数）。

因为上述操作不会往同一个位置写元素，所以他们是独立的，所以可以并行。

那么我们如何求出RANK？第一种是二分查找法；第二种是串型算法，类似于普通的归并排序算法的合并，也就是两个指针指着两个数组前进。

以上两种算法的比较：

二分查找法：时间复杂度更低，但是要消耗更多的CPU资源（需要n个处理器），而且总的工作量更大。
串型算法：时间复杂度高，但是只需要一个处理器，总工作量小。

算法改进

第一步：任务划分 (分为p块)

把数组分成每个大小为 \(\log ~n\) 的块。对于每一块的第一个元素，我们利用二分查找计算RANK。

把以上任意两条线之间定义为一个子任务。（注意红线和蓝线不相交）

这样就能划分出 \(2p\) 个子任务，每个子任务最大为 \(O(\log n)\)，因为每个 block 的大小最多为 \(2\log n\)。

以上，通过二分查找来获得RANK需要 \(T(\log n)\)，总工作量为 \(O(p\log n)=O(n)\)。

第二步：

对每个子任务应用串行算法，得到子序列的排序

总结：\(T=O(\log n), W=O(n)\)

14.5 Maximum Finding¶

法一¶

可以直接套用刚刚的算法，因为找最大值比加法容易，可以把加号替换成max。

法二¶

两两比较比较所有的数据，最终一次都没有被打败的就是最大的。如果产生冲突，那么使用CRCW的common处理机制，只有在写入的值相同的时候才能有效写入。

for Pi , 1 <= i <= n  pardo
    B(i) := 0
for i and j, 1 <= i, j <= n  pardo
    if ( (A(i) < A(j)) || ((A(i) = A(j)) && (i < j)) )
            B(i) = 1
    else B(j) = 1
for Pi , 1 <= i <= n  pardo
    if B(i) == 0
       A(i) is a maximum in A

\(T(n)=O(1)\) \(W(n)=O(n^2)\)

法三¶

将问题按照\(\sqrt n\)的规模分成\(\sqrt n\)个子问题。之后用法二来算出最大的。

将上述算法进行改进，让每个子问题的规模都是 \(h\) ，然后合并的时候调用上面这个方法，这样工作量可以减少到\(O(n)\)

注：每个子问题是通过线性查找的方式进行的，时间为 \(O(h)\) , work 为 \(O(h)\)

法四¶

先从\(n\)个元素中随机筛选出\(n^{7/8}\)个元素，找出\(n^{7/8}\)个处理器，去随机找出一个元素，但是这样的话不能保证不重复，但是无伤大雅。\(T=O(1), W=O(n^{7/8})\)

把上述\(n^{7/8}\)个元素分成\(n^{3/4}\)个每组有\(n^{1/8}\)元素。对于每个\(n^{1/8}\)的子问题都使用法二来暴力求解，找到最大值。每个子问题\(T=O(1), W=O((n^{1/8})^2 = O(n^{1/4})\)，所有加起来为\(T=O(1), W=O(n^{1/4}) \times n^{3/4}=O(n)\)

上一步得到了\(n^{3/4}\)个最大值，再作切分，分成\(n^{1/2}\)个每组有\(n^{1/4}\)元素。对于每个\(n^{1/4}\)的子问题都使用法二来暴力求解，找到最大值。每个子问题\(T=O(1), W=O((n^{1/4})^2 = O(n^{1/2})\)，所有加起来为\(T=O(1), W=O(n^{1/2}) \times n^{1/2}=O(n)\)

上一步得到了\(n^{1/2}\)的最大值，直接使用法二暴力求解。\(T=O(1), W=O((n^{1/2})^2 = O(n)\)

上一步得到了\(n^{7/8}\)个元素中的最大值s。