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