多核计算环境下的桶排序算法优化

康志辉

(厦门软件职业技术学院，福建厦门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.