Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 并行算法——列表的并行前缀
发信站: 哈工大紫丁香 (2002年03月22日14:52:31 星期五), 站内信件

并行算法——指针转移
 上一页 | 返回目录 | 下一页
1.2 列表的并行前缀
指针转移技术远不止应用于表排序问题。在算术电路中可以运用“前缀”计算来执行快
速二进制加法。现在我们来探讨如何运用指针转移技术来进行前缀计算。有关前缀问题
的EREW算法对由n个对象组成的表的运行时间为O(lgn)。
前缀计算是根据二进制中满足结合律的运算符?来决定的。计算时输入为序列<x1,x2,..
.,xn>并产生一个输出序列<y1,y2,...,yn>，满足y1=x1，并且对k=2,3,...,n，有
换句话说，每个yk是序列的头k个元素一起“相乘”而得到的。因此才有“前缀”这一意
义。
作为前缀计算的一个实例，假定n个对象组成的表中的每个元素包含的值为1，并设?表示
普通加法运算。因为对k=1,2,...,n，表中第k个元素包含的值为xk=1。所以前缀计算后
的结果为yk=k，即为第k个元素的下标。因此，进行表排序的另一种方法是先把表颠倒(
可以在O(1)的时间内完成)，执行前缀计算，然后把计算所得的每个值减1。
我们现在说明EREW算法是如何在O(lgn)的运行时间里对n个对象组成的表进行前缀计算的
。为了方便起见，我们定义符号记法：
其中整数i和j满足1≤i≤j≤n。则对k=1,2,..,n，有[k,k]=xk，并且对0≤i≤j≤k≤n，

根据这一符号记法，前缀计算的目标就是计算yk=[1,k]，k=1,2,..n。
当我们对表进行前缀计算时，我们希望输入序列<x1,x2,...,xn>的顺序由对象在链表中
的链接关系来确定，而不是由存储对象的存储器阵列中对象的下标来确定。下列EREW算
法开始时，表L中每个对象i都有一个相应的值x[i]。如果对象i是从表头开始的第k个对
象，则x[i]=xk为输入序列中的第k个元素。因此，并行前缀计算产生y[i]=yk=[1,k]。
List-Prefix(L)
1. for 每个处理器i，并行地执行
2.   do y[i] ← x[i]
3. while 存在一个对象i满灶next[i]≠NIL
4.   do for 每个处理器i,并行地执行
5.        do if next[i]≠NIL
6              then y[next[i]]← y[i]?y[next[i]];
7                   next[i]← next[next[i]];
上述伪代码和图3说明了这个算法和List-Rank的相似之处。仅有的差别在于初始化以及
更新值的不同（d或y）。在List-Rank中，处理器i更新其自身的d[i]；在List-Prefix中
，处理器i更新的是另一个处理器的y[next[i]]。注意，List-Prefix与List-Rank一样也
是EREW算法，因为指针转移技术维持以下条件不变：对不同的对象i和j，或者next[i]≠
next[j]，或者next[i]=next[j]=NIL。
图3说明了while循环中的每一次迭代执行前表的状态。这一过程保持下列条件不变：在
第t次while循环执行结束时，第k个处理器中存放了[max(1，k-2t+1)，k]，k=1,2,..,n
。在第一次迭代过程中，除最后一个对象的指针为NIL外，表中第k个对象均指向初始时
的第k+1个对象。第6行使得第k个对象(k=1,2,..,n-1)从其后继中取得值[k+1,k+1]。然
后执行运算[k,k]?[k+1,k+1]，得到[k,k+1]，再把它存储回其后继中。然后，next指针
与在List-Rank中一样进行转移，得到图3(b)所示的第一次迭代后的结果。第二次迭代也
是类似的。对k=1,2,...,n-2，第k个对象从其后继（由其next域的新的值所定义）取得
值[k+1,k+2]，然后把[k-1,k]?[k+1,k+2]=[k-1,k+2]存入其后继中。结果如图3(c)所示
。在第三次也是最后一次迭代中，只有表的开头两个对象的指针不是NIL，它们从其各自
的表中分别从其后继取得相应的值。最后的结果如图3(d)所示。我们注意到使算法List
-Prefix能够工作的关键是在每一步，如果我们对每一个存在的表进行先缀计算，则每个
对象均包含正确的值。
(a)
(b)
(c)
(d)
图3 在链表上并行前缀算法List-Prefix的执行过程
因为上面介绍的两种算法运用了同样的指针转移技术，所以对List-Prefix的分析与Lis
t-Rank相同：在EREW PRAM上的运行时间为O(lgn)，算法执行的全部工作为O(nlgn)。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]