?? chapter1_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 = "chapter1_1.htm";
next = "chapter1_3.htm";
contents="";
topic="并行算法——指針轉移";
</script>
<!-- #EndEditable -->
</head>
<body bgcolor="#FFFFFF">
<div id="content"> <!-- #BeginEditable "MainContent" -->
<h3>1.2 列表的并行前綴</h3>
<p>指針轉移技術遠不止應用于表排序問題。在算術電路中可以運用“前綴”計算來執行快速二進制加法。現在我們來探討如何運用指針轉移技術來進行前綴計算。有關前綴問題的EREW算法對由n個對象組成的表的運行時間為O(lgn)。</p>
<p>前綴計算是根據二進制中滿足結合律的運算符<font face="MT Symbol">Ä</font>來決定的。計算時輸入為序列<x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>>并產生一個輸出序列<y<sub>1</sub>,y<sub>2</sub>,...,y<sub>n</sub>>，滿足y<sub>1</sub>=x<sub>1</sub>，并且對k=2,3,...,n，有</p>
<blockquote>
<p><img border="0" src="images/Eqn2.gif" width="141" height="48"></p>
</blockquote>
<p>換句話說，每個y<sub>k</sub>是序列的頭k個元素一起“相乘”而得到的。因此才有“前綴”這一意義。</p>
<p>作為前綴計算的一個實例，假定n個對象組成的表中的每個元素包含的值為1，并設<font face="MT Symbol">Ä</font>表示普通加法運算。因為對k=1,2,...,n，表中第k個元素包含的值為x<sub>k</sub>=1。所以前綴計算后的結果為y<sub>k</sub>=k，即為第k個元素的下標。因此，進行表排序的另一種方法是先把表顛倒(可以在O(1)的時間內完成)，執行前綴計算，然后把計算所得的每個值減1。</p>
<p>我們現在說明EREW算法是如何在O(lgn)的運行時間里對n個對象組成的表進行前綴計算的。為了方便起見，我們定義符號記法：</p>
<blockquote>
<p><img border="0" src="images/Eqn3.gif" width="160" height="25"></p>
</blockquote>
<p>其中整數i和j滿足1≤i≤j≤n。則對k=1,2,..,n，有[k,k]=x<sub>k</sub>，并且對0≤i≤j≤k≤n，</p>
<blockquote>
<p><img border="0" src="images/Eqn4.gif" width="145" height="21"></p>
</blockquote>
<p>根據這一符號記法，前綴計算的目標就是計算y<sub>k</sub>=[1,k]，k=1,2,..n。</p>
<p>當我們對表進行前綴計算時，我們希望輸入序列<x<sub>1</sub>,x<sub>2</sub>,...,x<sub>n</sub>>的順序由對象在鏈表中的鏈接關系來確定，而不是由存儲對象的存儲器陣列中對象的下標來確定。下列EREW算法開始時，表L中每個對象i都有一個相應的值x[i]。如果對象i是從表頭開始的第k個對象，則x[i]=x<sub>k</sub>為輸入序列中的第k個元素。因此，并行前綴計算產生y[i]=y<sub>k</sub>=[1,k]。</p>
<pre><code class="pseudocode">List-Prefix(L)
1. for 每個處理器i，并行地執行
2. do y[i] ← x[i]
3. while 存在一個對象i滿灶next[i]≠NIL
4. do for 每個處理器i,并行地執行
5. do if next[i]≠NIL
6 then y[next[i]]← y[i]<font face="MT Symbol">Ä</font>y[next[i]];
7 next[i]← next[next[i]];</code></pre>
<p>上述偽代碼和圖3說明了這個算法和List-Rank的相似之處。僅有的差別在于初始化以及更新值的不同（d或y）。在List-Rank中，處理器i更新其自身的d[i]；在List-Prefix中，處理器i更新的是另一個處理器的y[next[i]]。注意，List-Prefix與List-Rank一樣也是EREW算法，因為指針轉移技術維持以下條件不變：對不同的對象i和j，或者next[i]≠next[j]，或者next[i]=next[j]=NIL。</p>
<p>圖3說明了while循環中的每一次迭代執行前表的狀態。這一過程保持下列條件不變：在第t次while循環執行結束時，第k個處理器中存放了[max(1，k-2<sup>t</sup>+1)，k]，k=1,2,..,n。在第一次迭代過程中，除最后一個對象的指針為NIL外，表中第k個對象均指向初始時的第k+1個對象。第6行使得第k個對象(k=1,2,..,n-1)從其后繼中取得值[k+1,k+1]。然后執行運算[k,k]<font face="MT Symbol">Ä</font>[k+1,k+1]，得到[k,k+1]，再把它存儲回其后繼中。然后，next指針與在List-Rank中一樣進行轉移，得到圖3(b)所示的第一次迭代后的結果。第二次迭代也是類似的。對k=1,2,...,n-2，第k個對象從其后繼（由其next域的新的值所定義）取得值[k+1,k+2]，然后把[k-1,k]<font face="MT Symbol">Ä</font>[k+1,k+2]=[k-1,k+2]存入其后繼中。結果如圖3(c)所示。在第三次也是最后一次迭代中，只有表的開頭兩個對象的指針不是NIL，它們從其各自的表中分別從其后繼取得相應的值。最后的結果如圖3(d)所示。我們注意到使算法List-Prefix能夠工作的關鍵是在每一步，如果我們對每一個存在的表進行先綴計算，則每個對象均包含正確的值。</p>
<p align="center"><img border="0" src="images/fig3a.gif" width="544" height="27"></p>
<p align="center">(a)</p>
<p align="center"><img border="0" src="images/fig3b.gif" width="544" height="61"></p>
<p align="center">(b)</p>
<p align="center"><img border="0" src="images/fig3c.gif" width="544" height="61"></p>
<p align="center">(c)</p>
<p align="center"><img border="0" src="images/fig3d.gif" width="544" height="27"></p>
<p align="center">(d)</p>
<p align="center">圖3 在鏈表上并行前綴算法List-Prefix的執行過程</p>
<p>因為上面介紹的兩種算法運用了同樣的指針轉移技術，所以對List-Prefix的分析與List-Rank相同：在EREW PRAM上的運行時間為O(lgn)，算法執行的全部工作為O(nlgn)。</p>
<!-- #EndEditable --> </div>
<script src='../../lib/footer.js'>
</script>
</body>
<!-- #EndTemplate -->
</html>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -