?? 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 + -