📄 chapter2_3.htm
字号:
<html>
<!-- #BeginTemplate "/Templates/article_template.dwt" -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="keywords" content="algorithm, data structure, contest, programming, 算法, 数据结构, 程序设计, 竞赛">
<meta name="description" content="discussing the algorithm and data structure of computer programming, as well as all kinds of programming contest.">
<meta name="description" content="讨论程序设计的算法与数据结构，各类程序设计竞赛试题解析和参赛经验介绍。">
<!-- #BeginEditable "doctitle" -->
<title>算法与数据结构 -- 用EREW算法来模拟CRCW算法</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter2_2.htm";
next = "chapter3.htm";
contents="";
topic="并行算法 -- CRCW 算法与 EREW 算法";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>2.3 用EREW算法来模拟CRCW算法</h3>
<p>现在我们已经知道CRCW算法能够比EREW算法更快地解决某些问题。并且，任何 EREW算法都能在CRCW PRAM上执行。因此，严格地说CRCW模型要比EREW模型更有效力。但是其效力究竟有多大？在第3节中，我们将会证明具有p个处理器的EREW
PRAM能够在O(lg p)的运行时间内对p个数进行排序。现在我们先运用这一结论来说明相对于EREW PRAM来说CRCW PRAM的效力的上界。</p>
<p class="theorem"><b>定理1<a name="theorem1"></a></b></p>
<p>具有p个处理器的CRCW算法的运行速度至多比解决同一问题的最好的具有p个处理器的EREW算法快O(lg p)倍。</p>
<p class="proof"><b>证明：</b></p>
<p>我们采用模拟论证。用一个运行时间为O(lgP)的EREW计算过程来模拟CRCW算法的每一步操作。因为两种计算机的处理能力是相同的，所以我们仅重点讨论存储器存取操作。在此我们仅对并发写操作进行模拟以证明定理。对并发读操作的模拟与此类似。</p>
<p>我们引入一个长度为p的数组A，使EREW PRAM中的p个处理器模拟CRCW算法中的并发写操作。图7说明了这一思想。对i=0,1,..,p-1，当CRCW处理器p<sub>i</sub>要求把一个数据x<sub>i</sub>写入存储单元l<sub>i</sub>时；每个相应的EREW处理器p<sub>i</sub>把序对(l<sub>i</sub>,x<sub>i</sub>)写入存储单元
A[i]中。因为每个处理器对不同的存储单元进行写操作，所以这些写操作都是互斥的。然后，把数组A按其有序对的第一个坐标在O(lg p)的时间内进行排序(<a href="chapter3.htm#deduction3">参见Brent定理的推论3</a>)，这样就使得写到同一个存储单元的所有数据在输出时被放在一起。</p>
<p>现在，对i=1,2,..,p-1，每个EREW处理器p<sub>i</sub>检查A[i]=(l<sub>j</sub>,x<sub>j</sub>)，A[i-1]=(l<sub>k</sub>,x<sub>k</sub>)其中0≤j,k≤p-1。如果l<sub>j</sub>≠l<sub>k</sub>或i=O，则对i=1,2,...,p-1，处理器p<sub>i</sub>把数据x<sub>j</sub>写到全局存储器的存储单元l<sub>j</sub>中。否则处理器不作任何操作。因为数组A已按其第一个坐标排序，所以实际上只有一个对任何给定存储单元执行写操作的处理器成功地执行操作，因此该写操作是互斥的。所以这一过程在O(lg
p)时间里实现了普通的CRCW模型中的并、发写操作中的每个步骤。(证毕)</p>
<p>有关并发写的其他模型也可以同样被模拟。</p>
<p align="center"><img border="0"
src="images/fig7a.gif" width="220" height="250"></p>
<p align="center"><br>
(a)</p>
<p align="center"><img border="0"
src="images/fig7b.gif" width="700" height="380"></p>
<p align="center">(b)</p>
<p align="center">图7 在一台EREW PRAM上模拟并发写操作</p>
<p>于是，又出现了这样一个问题：在CRCW和EREW中究竟应选择哪一种模型？如果选择CRCW，则应选择什么样的CRCW模型？CRCW模型的支持者指出，CRCW模型的程序设计要比EREW模型简单，并且运行速度快。CRCW模型的批评者则争论说实现并发存储的硬件要比实现互斥存储器操作的硬件速度慢，因此CRCW算法的运行速度是不现实的，在现实中无法用O(1)的运行时间找出n个值中的最大值。</p>
<p>另外还有一部分人认为PRAM，不论是EREW还是CRCW，都是完全不合适的模型。各处理必须由一个通讯网络互相连接，而这个通讯网络也应该是模型的一部分。在网络中，处理器应当仅能与其相邻的处理器进行通讯。</p>
<p>很清楚，不可能马上就能找出各种观点的人都赞同的“正确”并行模型。但是，重要的一点是我们必须认识到：模型仅仅是模型。在现实世界中，各种模型的应用都要受到不同程度的限制。模型在多大程度上与工程学的情形相匹配，在此模型上的算法分析就能在多大程度上预示现实世界中的现象。因此学习各种并行模型和相应的算法是相当重要的，随着对并行计算领域的研究不断发展，最终将会产生趋于一致的并且适合于实现的并行计算模型的规范。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -