Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 并发操作发挥作用的有关问题
发信站: 哈工大紫丁香 (2002年03月22日14:54:46 星期五), 站内信件

并发操作发挥作用的有关问题
假定已知一个二叉树组成的森林，其中每个结点都有一个指针parent[i]指向其父母结点
，我们希望每个结点能找出它所在的树的根结点。我们把处理器i与森林F中的每个结点
i相联结，下列指针转移算法把每个结i所在的树的根结点的值存储在root[i]中。
Find-Roots(F)
1 for 每个处理器i，并行地执行
2   do if parent[i]=NIL
3        then root[i]←i
4 while 存在一个结点i满足parent[i]≠NIL
5   do for 每个处理器i，并行地执行
6        do if parent[i]≠NIL
7             then root[i]← root[parent[i]]
8                  parent[i]← parent[parent[i]]
图5说明了该算法的操作过程。在第1-3行执行初始化操作后，如图5(a)所示，知道根的
值的唯一结点是根结点自身。第4-8行的while循环执行指针转移操作，并填入root域。
图5(b)-(d)分别说明了循环中的第1，第2和第3次迭代后森林的状态。我们可以看出，算
法保持下列条件不变：如果parent[i]=NIL，则把该结点的根的值赋给root[i]。
(a)
(b)
(c)
(d)
图5 用一台CREW PRAM在二叉树森林中寻找根的过程
我们说Find-Roots是一个运行时间为O(lgd)的CREW算法，其中d是森林中具有最大深度的
树的深度。写操作仅出现在第3，7和8行，并且因为在每个写操作中处理器仅对结点i写
入，所以这些写操作都是互斥性的。但是，第7-8行的读操作是并发执行的，这是因为数
个结点的指针可能指向同一个结点。例如在图5(b)中，我们可以看到在while循环的第二
次迭代中，root[4]和parent[4]同时被处理器18，2和7读出。
Find-Roots的运行时间为O(lgd)，其理由与List-Rank相同：每次迭代使每条路径的长度
缩短一半。图5明显地说明了这一特征。
如果只允许互斥读操作，则树林中的n个结点要找出其所在二叉树的根又需要多少时间？
我们可以简单地证明需要O(lgn)运行时间。关键的一点是：当读操作互斥时，PRAM的每
一步只允许把一条已知信息复制到存储器中的至多一个其他存储单元，因此每一步执行
后包含该信息的存储单元数至多增加一倍。在单棵树的情况下，初始时至多有一个存储
器单元保存着根的值；在第一步执行后，至多有两个存储器单元包含根的值；执行k步后
，至多有2k个存储单元包含根的值。如果树的规模为O(n)，则算法结束时就需要O(n)个
存储单元来存储根的值。因此，总共要执行的步数是O(lgn)。
每当森林中各个树的最大深度d为2O(lgn)时，从渐近意义上来说，CREW算法Find-Roots
要超过任何EREW算法。特别地，在一个由n个结点组成的森林中，最大深度的树是一棵具
有O(n)个结点平衡二叉树，d = O(lgn)，在这种情形下Find-Roots的运行时间为：O(lg
lgn)。用任何EREW算法解决这一问题则要Ω(lgn)的运行时间。因此，在这一问题中允许
并发读对于我们是有帮助的。

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

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