并行算法——指针转移（表排序）

我们介绍的第一个并行算法是有关列表的。列表在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行的while循环的迭代操作以前列表的状态。在第一次迭代中，表中开头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]。因此，所以 List-Rank是一种EREW算法。 从现在起，我们忽略有关同步的细节描述并假定PRAM与其伪代码设计环境都以始终如一的同步方式进行操作，所有处理器可同时执行读操作与写操作。 分析 我们现在来证明如果表L中有n个对象，则List-Rank的运行时间为O(lgn)。因为初始化占用的时间为O(1)，并且while循环中的每次迭代所需时间也是O(1)，所以只需证明总共有 「lgn」次迭代操作就可以了。 我们注意到关键是：指针转移的每一步把每个表转化为交错的两个表：一个表由偶数位置上的对象构成，另一个表由奇数位置上的对象构成。因此每个指针转移步使表的数目增加一倍而使其长度减为一半。因此，在「lgn」次迭代结束时，所有的表均包含一个对象。 第5行中的终止条件测试所需时间为O(1)。事实上，只要在循环体内用一个变量记录next[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不是高效的算法。