多核計算環境下的桶排序算法優化

康志輝

(廈門軟件職業技術學院，福建廈門361024)

排序是計算機領域中一類非常重要的問題，在很多數據處理中占用了計算機大量的處理時間，因此尋找高效排序算法一直是人們感興趣的問題［1］。以往，人們提出了許多高效排序算法，如快速排序算法［2］、縱橫多路并行歸并算法［3］、基于MPP的并行歸并算法［4］等。但是，有關桶排序算法的研究并不多，其主要原因是并行桶排序算法的時間復雜度為O((n/p)*log(n/p))［5］，如果要加以改進，比較困難。其次，并行桶排序算法對待排序數據的要求很高，要求數據在已知的范圍內均勻分布或接近均勻分布［11－12］。若待排序數據的分布極其不均勻，則并行桶排序算法會退化成串行快速排序算法，此時，其時間復雜度變為O(n*logn)［5］。本文針對以上問題，提出一種改進的并行桶排序算法，使其對任意分布的待排序數據進行排序的時間復雜度為O((n/p)*log(n/p))。

1 改進的并行桶排序算法

首先，我們給出如下定義。

定義1 前k－歸并:設非降序列S1和S2長分別為m和n，序列S為S1和S2歸并的結果，則稱由S1和S2求取S前k項的操作為S1和S2的前k－歸并(其中0＜=k＜=m+n)。

定義2 后k－歸并:設非降序列S1和S2長分別為m和n，序列S為S1和S2歸并的結果，我們稱由S1和S2求取S后k項的操作為S1和S2的后k－歸并(其中0＜=k＜=m+n)。

算法的基本思想:設A為長n的無序序列，B(i)(j)［k］表示第i層第j個桶的第k個數據，處理器數為p(不妨設n能被p整除)，對A進行排序。首先，把序列A劃分成等長子序列，將子序列與第0層的桶一一對應，并對桶內數據進行快速排序，從而得到?p/2」個有序桶。然后，對第0層中的相鄰有序桶并行進行前－歸并和后－歸并操作，從而生成第1層有序桶中的數據。從第1層開始，在以后各層的前后－歸并過程中，所產生的數據放入下層的相應桶內，只要下層桶內有數據就開始下層桶的前后 －歸并操作，把得到的數據放到其再下層的相應桶內。如此，從第1層開始形成樹形結構桶陣列，最后結果由樹根的桶得出。

算法的詳細描述如下:

輸入:無序序列A［0…n－1］，處理器個數p

輸出:有序序列 B［0…n－1］

end

本算法由三部分組成:

第一，把序列A劃分為p個n/p的等長子序列，分別放入桶B(0)(1)～B(0)(p)，處理器P1～Pp對B(0)(1)～B(0)(p)中的數據進行快速排序，使B(0)(1)～B(0)(p)成為有序桶。

第二，處理器P1對桶B(0)(1)和B(0)(2)進行前n/p－歸并，結果放入B(1)(1)的前n/p項，P2對桶B(0)(1)和B(0)(2)進行后n/p－歸并，結果放入B(1)(1)的后n/p項，依次處理后面的桶，可得到長為2*n/p的有序桶B(1)(1)～B(1)(p/2)(最后一個桶序列長可能小于2*n/p)。

第三，處理器P1對桶B(1)(1)和B(1)(2)進行前2*n/p－歸并，結果放入B(2)(1)的前2*n/p項，P3對桶B(1)(1)和B(1)(2)進行后2*n/p－歸并，結果放入B(2)(1)的后2*n/p項，并行處理后面的桶，可得到長為4*N/n的有序桶B(2)(1)～B(2)(p/4)(最后一個桶序列長可能小于4*n/p)。此時，偶數的處理器空閑，而當B(2)(1)和B(2)(2)的第0項有數據時(這只需要P1對桶B(1)(1)和B(1)(2)進行一次前－歸并操作，P5對桶B(1)(3)和B(1)(4)進行一次前－歸并操作)，P2可對B(2)(1)和B(2)(2)進行前4*n/p－歸并，產生的結果放入B(3)(1)的前4*n/p項。同理，P4對B(2)(1)和B(2)(2)進行后4*n/p－歸并，產生的結果放入B(3)(1)的后4*n/p項，同時并行處理第三層的桶中的數據，逐漸產生第四層桶的數據，且當第四層的桶有數據時(只需要第三層的桶同時進行一次前后－歸并操作)就開始產生第五層桶的數據。如此遞歸，形成了深度為?log(「p/2?)」+1的樹形結構，最后的結果由樹根上的桶B(?log(「p/2?)」+1)(0)給出。

舉下面實例，進一步說明算法的執行過程。

待排序數據:13，2，52，16，30，21，5，29，18，70，29，37，15，24，7，19

處理器數:8

本實例對幾個隨機數據進行排序，如上所示:(a)部分:是待排序序列根據處理器數目進行劃分后快速排序的結果。(b)部分:1)是(a)中的相鄰子序列進行前1－歸并和后1－歸并的結果，其詳細過程是2與16比較把2放入下一層的第一個桶的首位，13和52比較，把52放入下一層的第一個桶的末位，同時并行操作后面的桶。2)是進行前2－歸并和后2－歸并的結果，即13與16比較，把13放入下一層的第一個桶的第二位，13與16比較，把16放入下一層的第一個桶的倒數第二位，同時并行操作后面的桶。(c)部分:1)是對(b)中得到的四個有序桶(第一層的桶)進行前1－歸并和后1－歸并操作，分別得到其下一層的兩個數據。2)對第一層的桶進行前后2－歸并的同時，由于第二層桶有待處理數據，且有空閑的處理器，所以開始并行的前后－歸并第二層桶中的數據。其詳細過程是，13和5比較把5放入下層第一個桶的第二位，16和30比較把30放入下層第一個桶的倒數第二位，18和15比較，37和24比較，方別把15和37放入下層第二個桶的相應位置。同時，在下一層的桶的前1－歸并中，2和7進行比較，把2放入第三層桶的首位，52和70進行比較，把70放入第三層桶的末位。由于第三層只有一個桶，所以其最終結果即為我們所需要的已排序序列。

2 算法正確性分析

算法由3部分組成，第一部分的正確性已經在相關文獻中得到論證。下面來證明第二部分和第三部分的正確性。

引理1 對長為m和n的有序序列S1和S2做前k－歸并和后(m+n－k)－歸并，合并其結果，即可得到S1和S2的歸并結果。

證明 設S1和S2歸并結果為S，顯然，S長為m+n，由定義1可知，前k－歸并S1和S2可以得到S的前k項，后(m+n－k)－歸并S1和S2可以得到S的后m+n－k項，合并S的前k項和后m+n－k項即可得到S。

推論1 對長為m和n的有序序列S1和S2做前k1－歸并和后k2－歸并，若k1+k2＞=m+n，合并前－歸并和后－歸并的結果，就可以得到S1和S2的歸并結果。推論2 算法在執行完第二部分，得「p/2?個有序序列。引理2 算法第三部分最多使用p－2個處理器。

證明 在算法的第三部分，會形成一個二叉樹結構的桶陣列。在前后－歸并過程中，每兩個桶使用兩個處理器，單個桶不使用處理器，即所使用的處理器數最多和桶的數目一樣。又在第一層，共有「p/2?個桶，由二叉樹的性質可得第三部分的桶陣列深度為?log(「p/2?)」+1，所以所需桶的數目為2?log(「p/2?)」+1－1=p－1個，由于樹根的桶不需要處理器進一步處理，所以最多使用的處理器數為p－2。

定理 算法結束時，最后一層的桶保存A序列的有序排列。

證明 由推論2知，算法執行完第二部分可以得到「p/2?個有序序列，在算法的第三部分，只要桶中存在沒有被處理過的數據，就對其進行前后－歸并操作，把每次歸并的結果放入下一層的相應桶的相應位置。由于對上層桶的一次前后－歸并操作可以得到其下一層的每個桶的兩個數據，而每次的前后－歸并操作最多只處理掉桶中的一個數據。所以，只要某一層開始歸并操作，其上一層就能及時地供應足夠的數據，直到上層數據處理完畢，這時，這一層中的所有數據也全部給出。由于最多使用的處理器數為p－2個，即有足夠的處理器使用，而不需要等待處理器。當算法執行完畢，所有的數據匯集到樹根節點的桶中，并且，桶中的數據是有序的，即算法結束時，最下層桶保存著原序列的有序排列。

3 算法時間復雜度分析

算法的第一部分，對長為n/p的序列進行快速排序，所需時間為O((n/p)*log(n/p))。算法的第二部分，對長為n/p的有序序列執行前后n/p－歸并操作，時間為n/p。算法的第三部分，在算法第二步完成之后開始執行，對其形成的p/2個長為2*n/p的有序序列進行前后－歸并操作。只要對p/2個長為2*n/p的有序序列執行一次前后－歸并操作就可以為第2層的每個桶生成2個數據。同理，在第2層中進行一次前后－歸并操作也可以為第3層的每個桶生成2個數據，如此，直到最后一層。由于第三部分共?log(「p/2?)」+1層，所以當最后一層有數據時，總共需要?log(「p/2?)」次操作。而得到最后一層的桶的所有數據需要倒數第二層「n/2?執行次前后－歸并操作，所以第三部分總的時間為?log(「p/2?)」+「n/2? －1。

綜上分析，算法總的執行時間為T(n)=n/p*log(n/p)+n/p+?log(「p/2?)」+n/2=O(n/p*log(n/p))，算法成本為C(n)=p*T(n)=O(n*log(n/p))。

4 結論

本文針對多核計算環境下的桶排序算法優化，突破了經典的并行桶排序算法中要求原始數據在已知的范圍內服從均勻分布或接近均勻分布的限制。這種改進的并行桶排序算法可以對任意分布的數據進行排序操作，其時間復雜度為O((n/p)*log(n/p))，這與經典并行桶排序算法對均勻分布的數據的排序時間復雜度是相同的。

［1］楊磊，宋濤.基于數組的桶排序算法［J］.計算機研究與發展，2007，44(2):341 －347.

［2］霍紅衛，許進.快速排序算法研究［J］.微電子學與計算機，2002(6):6－10.

［3］王穎，李肯立，李浪，等.縱橫多路并行歸并算法［J］.計算機研究與發展，2006，43(12):2180－2186.

［4］丁衛群，計永昶，陳國良.一種基于MPP的并行歸并算法［J］.計算機研究與發展，1999，36(1):52－56.

［5］Barry Wilkinson，Michael Allen.并行程序設計［M］.北京:機械工業出版社，2005.