Algorithm 版 (精华区)

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

CRCW 算法与 EREW 算法
并行计算机的硬件是否应该提供并发的存储器存取操作？一些人认为支持CRCW算法的硬
件系统过分昂贵，且使用过于频繁，另外一些人则抱怨说EREW PRAM提供的程序设计模型
局限性太大。也许这场争论的最终答案在于两者之间的权衡，实际上也出现了数种折衷
模型。下面我们来考察一下并发的存储器存取操作究竟给算法带来了哪些优越性能。
在本节中，我们将证明用CRCW算法来解决某些问题要比用最好的EREW算法来解决同样的
问题要好。例如，对于在树林中寻找树根的问题，允许并发读操作可以使人们获得一种
更快的算法。对于在一个数组中寻找最大元素的问题，允许并发写操作也可以使算法的
执行速度更快。
2.1 并发操作发挥作用的有关问题
2.2 并发写操作发挥作用的一个问题
2.3 用EREW算法来模拟CRCW算法

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

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