Batcher歸併網路

Batcher歸併網路

Batcher歸併網路是Batcher提出來的,由一系列Batcher比較器(Batcher's Comparator)組成的。Batcher比較器是指在兩個輸入端給定輸入x, y,再在兩個輸出端輸出最大值和最小值。Batcher歸併網路採用了分而治之策略,即把得到兩個序列各分成兩半,前一半先進行分類,後一半同樣進行分類,得到兩個有序的子序列,再利用歸併網路進行歸併。

定義

Batcher歸併網路是利用歸併排序的方法可以方便地構造出排序網路。如果排序網路採用奇偶歸併構造而成,我們稱之為奇偶排序網路如果排序網路採用雙調歸併構造而成,則稱之為雙調排序網路採用歸併方法構造排序網路的具體步驟如下:

•首先對長度為n的輸人序列進行兩兩比較,形成若干長度為2的有序序列;

•使用歸併方法對長度為2的有序序列進行歸併,得到若干長度為4的有序序列,歸併的方法為上述的奇偶歸併或雙調歸併;

•重複上述步驟,直到得到一個完整的長度為的有序序列為止 [1]。

奇偶歸併網路

輸入兩個已排好序的序列,對這兩個序列進行歸併排序,在串列算法中的時間複雜度為O(n)。在並行計算中可以用奇偶歸併算法來實現的。以輸入的兩個4元素有序序列為A和B為例,首先將這兩個序列進行逆洗牌(Unshuffle)得到兩個序列:其中一個是由A,B中奇數號元素組成的序列,記作奇序列OM,另一個則是由A,B中偶數號元素組成的序列,記作偶序列序列EM。接著將OM送入(2,2)奇歸併器中,將EM送入(2,2)偶歸併器中。於是得到一組有序的奇序列和一組有序偶序列。最後除了奇序列一個元素之外將這兩個序列進行洗牌(Shuffle)比較操作即可得到一個有序序列。

算法的遞歸性:一個n階的歸併器是由兩個n/2階的歸併器加一個洗牌比較網路構成的。比如上面的兩個(2,2)歸併器和最後的洗牌比較網路就構成了一個(4,4)的歸併器。

一個四階奇偶歸併的例子:假設歸併前的的序列是(1,5,7,6)和(2,3,4,9),那么第一次操作就將(1,2,7,4)送入(2,2)歸併器中歸併,得到結果為(1,2,4,7);(5,3,6,9)送入(2,2)歸併器中歸併,得到結果為(3,5,6,9),接著將這兩個排好序的序列進行洗牌比較:(1,3<->2,5<->4,6<->7,9)=>(1,2,3,4,5,6,7,9)。

可以證明這個算法是正確的,我們要用到高德納(Donald Ervin Knuth)的0-1原理,我們發現,對於輸入的任意兩個有序的0,1序列,奇序列與偶序列正好相差0個,1個或2個0。由於奇序列的第一個元素不參與最後的洗牌比較,所以參與比較的0,1數偶只有0個或1個,所以對0,1序列一定能夠得到正確的排序。故而對任意的序列,奇偶歸併網路可以產生正確的排序。

雙調歸併網路

Batcher歸併網路 Batcher歸併網路
Batcher歸併網路 Batcher歸併網路

雙調歸併網路是基於Batcher定理而構建的。Batcher定理是說將任意一個長為2n的雙調序列A分為等長的兩半X和Y,將X中的元素與Y中的元素一一按原序比較,即 與 比較,將較大者放入MAX序列,較小者放入MIN序列。則得到的MAX和MIN序列仍然是雙調序列,並且MAX序列中的任意一個元素不小於MIN序列中的任意一個元素。根據這個原理,我們可以將一個輸入的n元素雙調序列首先通過洗牌比較操作得到一個MAX序列和一個MIN序列,然後通過兩個n/2階雙調歸併器處理就可以得到一個有序序列。這個算法也是遞歸的,因為n階的雙調歸併器是由一個洗牌比較網路兩個n/2階的雙調歸併器組成的。

所謂 雙調序列(Bitonic Sequence)是指由一個非嚴格增序列X和非嚴格減序列Y(其中X的最小元素正好是Y的最大元素)構成的序列,比如序列(23,10,8,3,5,7,11,78)。定義:一個序列a1,a2,…,an是 雙調序列(Bitonic Sequence),如果:

•存在一個ak(1≤k≤n),使得a1≥…≥ak≤…≤an成立;

•或者序列能夠循環移位滿足條件(1)。

並行計算

並行計算(parallel computing)一般是指許多指令得以同時進行的計算模式。在同時進行的前提下,可以將計算的過程分解成小部分,之後以並發方式來加以解決。

計算機軟體可以被分成數個運算步驟來運行。為了解決某個特定問題,軟體採用某個算法,以一連串指令運行來完成。傳統上,這些指令都被送至單一的中央處理器,以循序方式運行完成。在這種處理方式下,單一時間中,只有單一指令被運行(processor level: 比較微處理器,CISC, 和RISC,即流水線Pipeline的概念,以及後來在Pipeline基礎上以提高指令處理效率為目的的硬體及軟體發展,比如branch-prediction, 比如forwarding,比如在每個運算單元前的指令堆疊,彙編程式設計師對programm code的順序改寫)。並行運算採用了多個運算單元,同時運行,以解決問題。相對於串列計算,並行計算可以劃分成時間並行和空間並行。時間並行即流水線技術,空間並行使用多個處理器執行並發計算,當前研究的主要是空間的並行問題。以程式和算法設計人員的角度看,並行計算又可分為數據並行和任務並行。數據並行把大的任務化解成若干個相同的子任務,處理起來比任務並行簡單。

空間上的並行導致兩類並行機的產生,按照麥克·弗萊因(Michael Flynn)的說法分為單指令流多數據流(SIMD)和多指令流多數據流(MIMD),而常用的串列機也稱為單指令流單數據流(SISD)。MIMD類的機器又可分為常見的五類:並行向量處理機(PVP)、對稱多處理機(SMP)、大規模並行處理機(MPP)、工作站機群(COW)、分散式共享存儲處理機(DSM)。

相關詞條

熱門詞條

聯絡我們