posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          Sorting Networks

          Posted on 2008-04-23 20:22 ZelluX 閱讀(1757) 評論(2)  編輯  收藏 所屬分類: Algorithm
          算法導(dǎo)論第27章,在并行處理的條件下效率很高的排序算法。

          介紹
          如下面左圖所示,每條橫線(wire)代表一個待比較的數(shù)值,豎線(comparator)表示連接的兩條橫線要做一次比較,并將較小的值放在輸出橫線的上方,較大的放在下面。排序過程就是從左往右依次調(diào)用各個comparator(在同一位置上的comparator可以同時做)
          有圖表示了四個數(shù)字3, 2, 4, 1在經(jīng)過這個Sorting Network時的行為。

          下圖是一個冒泡排序的Sorting Network表示

          可以看到所有的比較都沒有并行,效率很低。接下來先介紹一個0-1原理,然后利用它來構(gòu)造一些比較高效的網(wǎng)絡(luò)。

          性質(zhì)
          首先是引理27.1:
          對于輸入數(shù)據(jù)A = <a_1, a_2, .., a_n>,如果某個比較網(wǎng)絡(luò)(comparison network)的輸出是B = <b_1, b_2, ..., b_n>,那么對于任一單調(diào)遞增的函數(shù)f,這個網(wǎng)絡(luò)能把輸入數(shù)據(jù)f(A) = <f(a_1), f(a_2), ..., f(a_n)>變?yōu)閒(B) = <f(b_1), f(b_2), ...f(b_3)>

          這個引理的證明很簡單,關(guān)鍵在于min(f(x), f(y)) = f(min(x,y))

          接下來就是0-1原理:
          一個有n個輸入數(shù)據(jù)的比較網(wǎng)絡(luò),如果它能將僅由0和1組成的序列正確的排序(這種輸入共有2^n種可能),那么它也能正確的將任意數(shù)字組成的序列排序。
          證明也不難,利用前面的引理反正即可得到這個定理。

          雙調(diào)排序
          接下來先考慮雙調(diào)序列(bitonic sequence)這種特殊情況,所謂雙調(diào)序列就是先單調(diào)遞增,后單調(diào)遞減,或者可以通過環(huán)形旋轉(zhuǎn)變化出上述特性的序列,比如<1, 4, 6, 8, 3, 2>和<6, 9, 4, 2, 3, 5>都滿足條件(對于后面一種序列,只要把最后的3, 5移到序列開頭就行了)。
          雙調(diào)排序(bitonic sorter)有若干步驟,其中有一步叫做half-cleaner,每一次half-cleaner講數(shù)據(jù)放到一個深度為1的排序網(wǎng)絡(luò)中,第i行和第i+n/2行比較(i=1,2,..,n/2)

          引理27.3:
          做完上述的half-cleaner后,輸出的上半部分和下半部分都保持雙調(diào)的特點(diǎn),而且上半部分的每個元素都不大于下半部分的任一元素。
          分四種情況討論即可。

          通過遞歸調(diào)用half-cleaner即可完成雙調(diào)隊(duì)列的排序。要對n個元素進(jìn)行雙調(diào)排序Bitonic-Sorter(n),首先調(diào)用Half-Cleaner(n),將元素分成上下兩部分,接著依次對這兩部分執(zhí)行Bitonic-Sorter(n/2)即可。
          調(diào)用的深度D(n) = lgn

          歸并網(wǎng)絡(luò)
          書上只給出了對0-1序列排序的算法,任意數(shù)字的排序算法留作了習(xí)題。
          合并網(wǎng)絡(luò)基于這樣一個事實(shí):對于兩個已經(jīng)排序了的序列X = 00000111,Y = 00001111,將Y倒過來后和X拼接的結(jié)果是一個雙調(diào)序列。對這個雙調(diào)序列再做一次Bitonic-Sorter就能有序。
          通過修改Bitonic-Sorter方法的第一步就能實(shí)現(xiàn)Merger,關(guān)鍵在于隱式的反轉(zhuǎn)輸入的下半部分。Half-Cleaner方法中比較了第i和第i+n/2兩個元素,如果下半部分反轉(zhuǎn)的話就相當(dāng)于比較第i和第n-i+1個元素。直接繼續(xù)執(zhí)行Bitonic-Sorter方法即可,如下圖所示。
          sortnetwork.JPG

          排序網(wǎng)絡(luò)
          我們已經(jīng)有了構(gòu)造一個排序網(wǎng)絡(luò)所需的工具,接下來介紹一種利用歸并網(wǎng)絡(luò)進(jìn)行排序的并行版本。
          大致方法和傳統(tǒng)的歸并排序類似,從最小的顆粒開始二分增長,直到整個序列有序。
          這樣,一共需要lg(n)次Merger,每次歸并中需要做lg(i)次Sorter,排序的總深度
          D(n) =
          0 ? ? ? ? ? ? ? (n = 1)
          D(n/2) + lg(n)? (n = 2^k且 k>=1)
          由Master Method可推出D(n) = big-omega(lg^2(n))
          也就是說理想的并行環(huán)境中,n個數(shù)可以在O(lg^2(n))時間內(nèi)完成排序。

          Bitonic Sorter http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/bitonic/bitonicen.htm

          評論

          # re: Sorting Networks  回復(fù)  更多評論   

          2008-04-24 19:33 by luohandsome
          似乎突破NlogN的極限了

          # re: Sorting Networks  回復(fù)  更多評論   

          2008-04-24 21:02 by ZelluX
          @luohandsome
          恩,不過是理想化的情況,即使在Nvidia的8800GT上也只能同時跑128個kernel,所以我覺得這個算法實(shí)際的復(fù)雜度是系數(shù)很小的big-omega(nlogn)
          主站蜘蛛池模板: 马山县| 麻阳| 乐陵市| 莆田市| 公安县| 宝坻区| 通城县| 彰武县| 石嘴山市| 谷城县| 松桃| 宁蒗| 安庆市| 霍山县| 织金县| 什邡市| 巧家县| 隆安县| 赤水市| 中山市| 吉首市| 安乡县| 唐河县| 遵义县| 舒城县| 内丘县| 荃湾区| 海原县| 长宁区| 讷河市| 凤凰县| 庐江县| 三门县| 上虞市| 和顺县| 勐海县| 汾阳市| 武冈市| 剑河县| 贵德县| 浦江县|