Parallel Sum (Reduce)
给定 , 计算 .
这个问题作为引入并行计算的例子.
就是写成分治的算法来让子问题并行地执行, 最常见的套路.
Parallel Prefix Sum (Scan)
数组 ,
前缀和为 ,
下文中所有的除法都默认下取整.
非并行的算法为 .
根据 reduce 算法得到的树就可以直接通过搜索计算出每个前缀和, 这需要
的时间,
具体搜索规则如下:
- 现在要计算
对应位置的前缀和, 从二叉树的根节点开始搜索 , 搜索路径是唯一的,
当路径向左时什么也不做; 当路径向右时,
则加上到达的结点的另一个兄弟节点.
并行思路 1
类似于计算序列和的 reduce 算法的其中一个, 减小问题规模:
计算 的前缀和得到
, 且 .
然后
现在 work 和 span 分别满足
因此
主方法应该更好用.
并行思路 2
分治可以得到更好的 span.
将 分成两部分 ,
分别计算每一部分的前缀和得到 , 这样可以得到前缀和 满足 ,
或者说, 这里的
应该写成 ,
这就意味着如果要使用分治, 就需要维护一个 offset, 每一个区间都有一个
offset.
更一般地, 设算法执行到某个阶段时下标区间为 , 当前区间的 offset 为 , 则令 , 分区间 , 区间
的 offset 为 , 的 offset 为 .
下面是一个例子, 对应的序列为 .
如果在并行时再计算求和
显然开销较大, 则可以先预处理, 存到数组 中, 满足 ,
同时注意到分支过程中每一个出现的 都不会重复,
因此可以用一维数组 , 预处理 的过程可以通过计算序列和的 reduce
算法得到, 因此:
1
2
3
4
5
6
7
8
9
| scan_up(A[],L[],n){
if(n==1)return A[0];
m=n/2;
par_do:
l=scan_up(A,L,m);
r=scan_up(A+m,L+m,n-m);
L[m-1]=l;
return l+r;
}
|
scan_up 预处理出数组 L 后, 用
scan_down 计算前缀和
1
2
3
4
5
6
7
8
9
10
| scan_down(A,B,L,s,t,offset){
if(s==t){
B[s]=A[s]+offset;
return;
}
mid=(s+t)/2;
par_do:
scan_down(A,B,L,s,mid,offset);
scan_down(A,B,mid+1,t,offset+L[mid-1]);
}
|
对于 work 和 span, 的 work 和 的 span.
还有一个不需要额外空间的改进版本:
并行前缀和的应用:
filtering/packing
filtering 问题描述如下:
给定
和布尔函数 ,
求满足 的那些数,
并输出得到序列 ,
保留这些数在 中的顺序.
并行地对序列 求前缀和
, 以此获取 中每个满足 的数在 中的下标.
1
2
3
4
5
6
7
8
9
10
11
12
| filtering(A,b,B,f){
new array flag[n],ps[n];
flag=[&](int i){
return f(A[i]);
};
ps=scan(flag,n);
par_for(int i=0;i<n;i++){
if(flag[i]){
B[ps[i]]=A[i];
}
}
}
|
这需要 的 work 和 的 span.
Parallel Quick Sort
快排的基本思想是找一个 pivot ,
把 序列中 和 的分别放在 的左边和右边(这一操作称为 partition),
再分别对两者进行相同操作.
最直观的并行想法是 partition 之后对两部分并行地处理, 但是 partition
需要 的时间, 因此 得到 .
parallel partition
借助前面提到的 filtering, partition 的过程就可以看作是一个 filtering,
其中 .
那么这一个过程就可以用 parallel filtering 来实现.
1
2
3
4
5
6
7
| qsort(A,n){
t=parallel_partition(A,A[random()]);
par_do{
qsort(A,t);
asort(A+t,n-t);
}
}
|
现在主要的问题其实是如何高效地用 parallel filtering 来将序列中小于
pivot 的数放在 pivot 的左边, 大于 pivot 的数放在 pivot 的右边,
并且要保证是 in-place 的, 但是如果要用 filtering, 比如先除了小于 pivot
的数据的时候, 会覆盖掉很多数据, 也就是会影响大于 pivot 的那些数.
如果说是并行实现, 那就是交换操作保证是 in-place 的.
1
2
3
4
5
6
7
8
9
10
11
| void q_sort2(int l,int r){
int mid=(a[l]+a[r])/2;
int i=l,j=r;
while(i<=j){
while(a[i]<mid)i++;
while(a[j]>mid)j--;
if(i<=j)swap(a[i++],a[j--]);
}
if(j>l)q_sort2(l,j);
if(i<r)q_sort2(i,r);
}
|
Analysis of Quick Sort
非并行的快排的期望时间复杂度为 , 递归次数期望为 .
设把第
个元素排序到最终位置花了 次
(在分治树的第 层),
那么算法整体的 work 实际上是 , span 为 . 且 .
称
以很高的概率成立 (with high probability), 如果
, , 其中
是一个常数.
即
成立的概率至少是 .
设独立同分布的随机变量 且 , 令 ,
则
w.h.p.
最终并行快排有 的
work 以及 的 span
w.h.p, 即 .
