Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 用EREW算法来模拟CRCW算法
发信站: 哈工大紫丁香 (2002年03月22日14:55:22 星期五), 站内信件

用EREW算法来模拟CRCW算法
现在我们已经知道CRCW算法能够比EREW算法更快地解决某些问题。并且，任何 EREW算法
都能在CRCW PRAM上执行。因此，严格地说CRCW模型要比EREW模型更有效力。但是其效力
究竟有多大？在第3节中，我们将会证明具有p个处理器的EREW PRAM能够在O(lg p)的运
行时间内对p个数进行排序。现在我们先运用这一结论来说明相对于EREW PRAM来说CRCW
 PRAM的效力的上界。
定理1
具有p个处理器的CRCW算法的运行速度至多比解决同一问题的最好的具有p个处理器的ER
EW算法快O(lg p)倍。
证明：
我们采用模拟论证。用一个运行时间为O(lgP)的EREW计算过程来模拟CRCW算法的每一步
操作。因为两种计算机的处理能力是相同的，所以我们仅重点讨论存储器存取操作。在
此我们仅对并发写操作进行模拟以证明定理。对并发读操作的模拟与此类似。
我们引入一个长度为p的数组A，使EREW PRAM中的p个处理器模拟CRCW算法中的并发写操
作。图7说明了这一思想。对i=0,1,..,p-1，当CRCW处理器pi要求把一个数据xi写入存储
单元li时；每个相应的EREW处理器pi把序对(li,xi)写入存储单元 A[i]中。因为每个处
理器对不同的存储单元进行写操作，所以这些写操作都是互斥的。然后，把数组A按其有
序对的第一个坐标在O(lg p)的时间内进行排序(参见Brent定理的推论3)，这样就使得写
到同一个存储单元的所有数据在输出时被放在一起。
现在，对i=1,2,..,p-1，每个EREW处理器pi检查A[i]=(lj,xj)，A[i-1]=(lk,xk)其中0≤
j,k≤p-1。如果lj≠lk或i=O，则对i=1,2,...,p-1，处理器pi把数据xj写到全局存储器
的存储单元lj中。否则处理器不作任何操作。因为数组A已按其第一个坐标排序，所以实
际上只有一个对任何给定存储单元执行写操作的处理器成功地执行操作，因此该写操作
是互斥的。所以这一过程在O(lg p)时间里实现了普通的CRCW模型中的并、发写操作中的
每个步骤。(证毕)
有关并发写的其他模型也可以同样被模拟。
(a)
(b)
图7 在一台EREW PRAM上模拟并发写操作
于是，又出现了这样一个问题：在CRCW和EREW中究竟应选择哪一种模型？如果选择CRCW
，则应选择什么样的CRCW模型？CRCW模型的支持者指出，CRCW模型的程序设计要比EREW
模型简单，并且运行速度快。CRCW模型的批评者则争论说实现并发存储的硬件要比实现
互斥存储器操作的硬件速度慢，因此CRCW算法的运行速度是不现实的，在现实中无法用
O(1)的运行时间找出n个值中的最大值。
另外还有一部分人认为PRAM，不论是EREW还是CRCW，都是完全不合适的模型。各处理必
须由一个通讯网络互相连接，而这个通讯网络也应该是模型的一部分。在网络中，处理
器应当仅能与其相邻的处理器进行通讯。
很清楚，不可能马上就能找出各种观点的人都赞同的“正确”并行模型。但是，重要的
一点是我们必须认识到：模型仅仅是模型。在现实世界中，各种模型的应用都要受到不
同程度的限制。模型在多大程度上与工程学的情形相匹配，在此模型上的算法分析就能
在多大程度上预示现实世界中的现象。因此学习各种并行模型和相应的算法是相当重要
的，随着对并行计算领域的研究不断发展，最终将会产生趋于一致的并且适合于实现的
并行计算模型的规范。

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

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