Algorithm 版 (精华区)

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

并行算法——指针转移
 上一页 | 返回目录 | 下一页
1.1 表排序
我们介绍的第一个并行算法是有关列表的。列表在PRAM中的存储方式与普通的 RAM相同
。为了便于并行地对列表中的对象进行操作，我们为每个对象分配一个“响应”处理器
。假定处理器数目与列表中的对象一样多，并且第i个处理器负责处理第i个对象。例如
，图2(a)说明了一个由对象序列<3,4,6,1,0,5>组成的链表。由于每个对象对应于一个处
理器，所以表中的每个对象都可由其响应处理器在O(1)的时间内对其进行操作。
(a)
(b)
(c)
(d)
图2 运用指针转移在O(lgn)时间内求出n个对象组成的链表中每个对象到表尾的距离
假定已知一个包含n个对象的单链表L，我们希望计算出表L中的每个对象到表尾的距离。
更形式地说，如果next是指针域，我们希望计算出表中每个对象i的值d[i]，使得：
我们把这一计算d值的问题称为表排序问题。
解决表排序问题的一种方法是从表尾把距离往回传输。因为表中从末端开始的第k个对象
必须等到其后的k-1个对象确定了它们到表尾的距离后才能确定其自身到表尾的距离，所
以这一方法需要O(n)的运行时间。实际上，这一解决方法是一种串行算法。
下面的代码给出了一种有效的并行算法，其运行时间仅为O(lgn)。
List-Rank(L)
1. for 每个处理器i，并行地执行
2.   do if next[i]=NIL
3.        then d[i]←0
4.        else d[i]←1;
5. while 存在一个对象i，满足next[i]≠NIL
6.   do for 每个处理器i，并行地执行
7.        do if next[i]≠NIL
8.             then d[i]←d[i]+d[next[i]];
9.                  next[i]←next[next[i]];
图2说明了算法是如何计算出各个距离值的。图中的每个部分说明了执行第5-9行的whil
e循环的迭代操作以前列表的状态。在第一次迭代中，表中开头5个对象的指针不为NIL，
所以由其响应处理器分别执行第8-9行的操作。其操作结果见图中的(b)部分。在第二次
迭代中，只有前面4个对象的指针不是NIL，该次迭代后的结果见图中的(c)部分，在第3
次迭代中，只对表中开头2个对象进行操作，最后所有对象的指针均变为NIL，其结果见
图中的(d)部分。
在第9行中，对所有非NIL指针next[i]，我们置next[i]← next[next[i]]，它实现的设
计思想称为指针转移。注意，由于指针转移操作改变了指针域，因而也就破坏了链表的
结构。如果必须保持链表结构，则我们可以对next指针做备份并使用该备份来计算距离
的值。
正确性
List-Rank维持以下不变条件：在第5-9行while循环中每次迭代开始时，对每个对象i，
如果对以i作表头的子表的各个d值求和，就得到了从i到初始表L尾的正确距离。例如，
在图2(b)中，对象3作表头的子表是序列<3,6,0>，其d值分别为2,2,和1，它们的和为5，
这就是该对象到初始表尾的距离。上述不变条件成立的原因是当每个对象与其在表中的
后继进行“拼接”时，它把其后继的d值加到自身的d值中。
必须注意，为使指针转移算法能正确执行，必须使并行的存储器存取保持同步。每次执
行第9行代码可以对数个next指针进行更新。我们要求赋值式右边的存储器读操作（读 
next[next[i]]）出现在赋值式左边的任何存储器写操作（写next[i]）之前。
现在让我们看看List-Rank是一个EREW算法的原因。因为每个处理器至多响应一个对象，
所以第2-7行的每个读操作和写操作都是互斥的，第8-9行的写操作也是如此。请注意指
针转移维持下列不变条件：对任意两个不同的对象i和j，或者有next[i]≠next[j]，或
者有next[i]=next[j]=NIL。对初始表这一条件显然成立，并且通过第9行操作该条件一
直保持成立。因为所有非NIL的next值都是不同的，所以第9行中的读操作也是互斤的。

如果所有读操作都是互斥的，我们就无需假设在第8行中执行了某种同步操作。特定地，
我们要求所有处理i只能先读d[i]，然后才能读d[next[i]]。有了这种同步要求，如果一
个对象i有next[i]≠NIL，并且有另外一个对象j指向i（即next[j]=i），则第1个读操作
为处理器i取得值d[i]，然后第 2个读操作才能为处理器j取得值d[i]。因此，所以 Lis
t-Rank是一种EREW算法。
从现在起，我们忽略有关同步的细节描述并假定PRAM与其伪代码设计环境都以始终如一
的同步方式进行操作，所有处理器可同时执行读操作与写操作。
分析
我们现在来证明如果表L中有n个对象，则List-Rank的运行时间为O(lgn)。因为初始化占
用的时间为O(1)，并且while循环中的每次迭代所需时间也是O(1)，所以只需证明总共有
 「lgn」次迭代操作就可以了。我们注意到关键是：指针转移的每一步把每个表转化为
交错的两个表：一个表由偶数位置上的对象构成，另一个表由奇数位置上的对象构成。
因此每个指针转移步使表的数目增加一倍而使其长度减为一半。因此，在「lgn」次迭代
结束时，所有的表均包含一个对象。
第5行中的终止条件测试所需时间为O(1)。事实上，只要在循环体内用一个变量记录nex
t[i]≠NIL的i的个数，就可以在O(1)的时间内完成第5行的测试。
除了并行的运行时间外，对于并行算法还存在另一种有趣的性能评价方法。我们定义并
行算法执行的工作为其运行时间与所需的处理器数目的积。从直观上看，工作是一个串
行RAM模拟并行算法时所执行的计算量。
过程List-Rank执行了O(nlgn)的工作，这是因为它需要n个处理器且其运行时间为O(lgn
)。关于表排序问题的简单的串行算法的运行时间为O(n)，这说明List-Rank执行的某些
工作并不是必需的，但两者仅差一个对数因子。
已知一个PRAM算法A和求解同一个问题的另一种(串行或并行)算法B，如果A执行的工作不
超过B执行的工作乘以一个常数因子，我们就说算法A对于算法B来说高效。如果算法A对
于串行RAM上最好的算法来说是高效的，我们就更简单地称PRAM算法A高效。因为在串行
RAM上关于表排序的最好算法的运行时间为O(n)，所以List-Rank不是高效的算法。我们
将在第4节中阐述一个关于表排序的高效的并行算法。

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

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