多核計(jì)算環(huán)境下的桶排序算法優(yōu)化

康志輝

(廈門軟件職業(yè)技術(shù)學(xué)院，福建廈門361024)

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

1 改進(jìn)的并行桶排序算法

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

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

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

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

算法的詳細(xì)描述如下:

輸入:無(wú)序序列A［0…n－1］，處理器個(gè)數(shù)p

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

end

本算法由三部分組成:

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

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

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

舉下面實(shí)例，進(jìn)一步說(shuō)明算法的執(zhí)行過(guò)程。

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

處理器數(shù):8

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

2 算法正確性分析

算法由3部分組成，第一部分的正確性已經(jīng)在相關(guān)文獻(xiàn)中得到論證。下面來(lái)證明第二部分和第三部分的正確性。

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

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

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

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

定理 算法結(jié)束時(shí)，最后一層的桶保存A序列的有序排列。

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

3 算法時(shí)間復(fù)雜度分析

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

綜上分析，算法總的執(zhí)行時(shí)間為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 結(jié)論

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

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

［2］霍紅衛(wèi)，許進(jìn).快速排序算法研究［J］.微電子學(xué)與計(jì)算機(jī)，2002(6):6－10.

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

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

［5］Barry Wilkinson，Michael Allen.并行程序設(shè)計(jì)［M］.北京:機(jī)械工業(yè)出版社，2005.