📄 chapter2_2.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>算法与数据结构 -- 并发写操作发挥作用的一个问题</title>
<!-- #EndEditable -->
<script id="header" language="JavaScript" src="../../lib/header.js"></script>
<!-- #BeginEditable "javascript" -->
<script language="JavaScript">
previous = "chapter2_1.htm";
next = "chapter2_3.htm";
contents="";
topic="并行算法 -- CRCW 算法与 EREW 算法";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>2.2 并发写操作发挥作用的一个问题</h3>
<p>为了证明并发写操作提供的性能要优于互斥写操作所能提供的性能，我们来考察一个在实数组成的数组中寻找最大元素的问题。我们将会看到，关于这个问题的任何EREW算法都需要Ω(lgn)的运行时间，没有任何CREW算法能获得更好的性能。但是，采用一个普通的CRCW算法来解决这一问题仅需要O(1)时间。在这个算法中数个处理器可以对同一个存储单元进行写操作，且写出的值相同。</p>
<p>找出n个数组元素中的最大值的CRCW算法假定输入的数组为A[0..n-1]。该算法使用了n<sup>2</sup>个处理器。对0≤i≤j≤n-1，每个处理器对A[i]和A[j]的值进行比较。实际上，算法是对一个比较矩阵进行操作，因此我们不仅可以把这n<sup>2</sup>个处理器赋予一个一维下标，也可以把它们理解为具有二维下标(i,j)。</p>
<pre><code class="pseudocode">Fast-Max(A)
1 n ← length(A)
2 for i←0 to n-1 并行地执行
3 do m[i]← TRUE
4 for i←0 to n-1 and j←0 to n-1 并行地执行
5 do if A[i] < A[j]
6 then m[i] ← FALSE
7 for i←0 to n-1 并行地执行
8 do if m[i] = TRUE
9 then max←A[i]
10 return max</code></pre>
<p>第1行确定了数组A的长度；它仅需在一个处理器(如处理器0)上执行。我们设置了一个数组m[0..n-1]，m[i]由处理器i响应。我们希望m[i]=TRUE当且仅当A[i]是数组A中元素的最大值。开始时(第2-3行)，我们把每个元素都当作可能的最大值处理，并且依靠第5行中的比较操作以确定哪些元素不是值最大的元素。</p>
<p>图6说明了算法的余下部分在第4-6行的循环代码中，我们对数组A中排序的每对元素进行检查。对每对元素A[i]和A[j]，第5行专看是否有A[i]<A[j]。如果这一比较式为真，我们就知道A[i]不可能是最大元素，于是在第6行中置m[i]←FALSE以便记录下这一事实。可能有数个(i,j)处理器同时对m[i]进行写操作，但它们要写入的都是相同的值：FALSE。</p>
<div align="center">
<table border="0">
<tr>
<td></td>
<td>
<p align="center"><b>A[j]</b>
</td>
</tr>
<tr>
<td><b>A[i]</b></td>
<td>
<div align="center">
<center>
<table border="1"
bordercolor="#000000"
bordercolorlight="#000000" cellspacing="0">
<tr>
<td align="center"> </td>
<td align="center">
<div align="center">
<table border="0" width="100%">
<tr>
<td width="20%" align="center"><b>5</b></td>
<td width="20%" align="center"><b>6</b></td>
<td width="20%" align="center"><b>9</b></td>
<td width="18%" align="center"><b>2</b></td>
<td width="22%" align="center"><b>9</b></td>
</tr>
</table>
</div>
</td>
<td align="center"><b>m</b></td>
</tr>
<tr>
<td align="center" valign="top">
<div align="center">
<table border="0" width="100%">
<tr>
<td width="100%" align="center"><b>5</b></td>
</tr>
<tr>
<td width="100%" align="center"><b>6</b></td>
</tr>
<tr>
<td width="100%" align="center"><b>9</b></td>
</tr>
<tr>
<td width="100%" align="center"><b>2</b></td>
</tr>
<tr>
<td width="100%" align="center"><b>9</b></td>
</tr>
</table>
</div>
</td>
<td align="center">
<table border="0" width="100%">
<tr>
<td width="20%" align="center">F</td>
<td width="20%" align="center">T</td>
<td width="20%" align="center">T</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">T</td>
</tr>
<tr>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">T</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">T</td>
</tr>
<tr>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
</tr>
<tr>
<td width="20%" align="center">T</td>
<td width="20%" align="center">T</td>
<td width="20%" align="center">T</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">T</td>
</tr>
<tr>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
<td width="20%" align="center">F</td>
</tr>
</table>
</td>
<td align="center">
<table border="0" width="127%">
<tr>
<td width="100%" align="center">F</td>
</tr>
<tr>
<td width="100%" align="center">F</td>
</tr>
<tr>
<td width="100%" align="center">T</td>
</tr>
<tr>
<td width="100%" align="center">F</td>
</tr>
<tr>
<td width="100%" align="center">T</td>
</tr>
</table>
</td>
</tr>
</table>
</center>
</div>
</td>
</tr>
<tr>
<td> </td>
<td>
<p align="right"><b><i>max </i>9</b>
</td>
</tr>
</table>
</div>
<p align="center">图6 用CRCW算法Fast-Max在O(1)的时间内求出n个值中的最大值</p>
<p>因此，在执行完第6行代码后，只有对A[i]是最大值的下标i，才有m[i]=TRUE。第7到9行把这一最大值存入变量max中，并返回。可能有数个处理器对变量max进行写操作，但如果是这样，它们要写入的都是相同的值，这个条件对于普通的CREW
PRAM模型是必须一贯保持的。</p>
<p>由于算法中的三个循环均是并发执行，所以Fast-Max的运行时间为O(1)。当然，它并不是高效的算法，这是因为它需要n<sup>2</sup>个处理器，而用串行算法解决这个问题所需的运行时间为O(n)。</p>
<p>在某种意义上说，过程Fast-Max的关键在于一台CRCW PRAM用了n个处理器在O(1)的时间内执行关于n个变量的布尔型“与”操作（因为普通的CRCW模型具备这种性能，所以具有更大效力的CRCW
PRAM模型更应具备这一性能）。实际上，上述代码一次执行了数个“与”操作，它对i=0,1,....n-1，计算：</p>
<p> <img src="images/Eqn5.gif" width="144" height="46"></p>
<p>上式可由DeMorgan定理推出。这一“与”功能也可用于其他方面。例如，CRCW PRAM具有在O(1)的时间内执行“与”操作的功能，因而不需要用一个独立的控制网络来测试全部处理器是否都完成了一次循环。是否结束循环仅由对所有处理器结束循环的要求进行“与”操作的结果来决定。</p>
<p>EREW模型不具备这种强有力的“与”工具。计算n个元素中的最大值的任何EREW算法均需要Ω(lgn)的运行时间。关于这一点的证明从概念上说类似于寻找二叉树根结点的下界的论证。在那个证明里，我们观察有多少结点“知道”其根的值，并证明了每一步操作至多使“知道”的结点数增加一倍。对于计算n个元素中的最大值问题，我们观察哪些元素“知道”它们不是最大值，从直观上说，在EREW
PRAM上的每一步操作后，这一“知道”的元素数目至多减少一半，这样我们就得了下界Ω(lgn)。</p>
<p>令人惊异的是，即使我们允许执行并发读操作，计算最大值的运行时间的下界依然是Ω(lgn)。亦即，对CREW算法该下界也保持不变。Cook，Dwork和Reischuk已经证明：实际上，即使处理器数目不受限制且存储器容量也不受限制，寻找n个元素中最大值的任何CREW算法都必须运行O(lgn)的时间。对于计算n个布尔值的“与”问题，该下界Ω(lgn)也适用。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -