基于枚举的并行排序与选择算法设计

罗明山

摘要：随着多核处理器的普及以及云计算应用的推广，并行算法和并行程序设计再度升温，串行算法向并行算法转换已成为提高计算性能的重要途径。尽管枚举算法在串行环境下是不可取的，但是，由于其枚举比较本身具有潜在的并行执行的可能性，使得它在并行计算环境下大放异彩。该文串行的枚举排序为基础，阐述了基于枚举的并行排序、并行（m，n）-选择和并行K-选择算法，在Open MP编程模型上用C++加以实现。运行于多核CPU上，结果证明算法是有效的、有利用价值的。

关键词：枚举；秩；排序；选择算法；并行计算

中图分类号：TP312 文献标识码：A 文章编号：1009-3044（2015）12-0088-03

排序与选择是计算机处理数据的重要工作。经过长期的研究，人们提出了许多排序算法，包括插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和基数排序等。目前，排序算法是《数据结构与算法设计》课程的重要组成部分。

选择算法包括k-选择和（m，n）-选择。k-选择是指从数据序列中选出第k个最小（或最大）的数据元素；（m，n）-选择是指从n个数据序列中选择出m个最小（或最大）的数据元素[1]。选择算法更适用并行处理，且多采用比较网络实现。

基于枚举的排序称为枚举排序（Enumeration Sorting），也称为秩排序（Rank Sorting）[2]。在串行环境下，枚举排序是不可取的，但是，由于枚举比较本身具有潜在的并行执行的可能性，使得它在并行排序中大放异彩[3]。文献[1] [2][3]介绍了串行枚举排序和基于MIMD-CREW模型上的并行枚举排序。本文介绍多核处理机上Open MP编程环境下的并行枚举排序与并行选择算法。

1 并行枚举排序

所谓的“秩”是指数据集合中比自身小的数据元素的个数，它可以直接反映该数据在排序数据序列中的位置。枚举排序的基本思想是：逐一地计算每个数据的“秩”，然后根据“秩”调整数据的位置，最终实现排序。

并行枚举排序由数据播送、秩计算和数据收集三个过程组成[3]。与MIMD-CREW模型上的并行枚举排序算法相比，多核处理器上的并行枚举算法显得更加简单，其基本思想是将待排序数据进行分组，由多个处理机并行地对各分组进行秩计算，最后根据秩调整数据的位置，得出排序序列。

1.1秩的计算

在待排序数据序列为S[0，…，n-1]中，计算数据元素S[k]的秩就是逐一地统计比S[k]小的数据元素的个数。算法描述如下：

输入：待排序数组S[0，..，n-1]和数据元素S[k]

输出：数据元素S[k]的秩

Index（S[]，n，S[k] ）

{ int index=0；

for（int i=0；i<=n；i++）

if（S[k]

return index；}

算法的时间复杂度为O（n）。

1.2 各分组数据元素秩的计算

并行枚举排序的关键环节就是用多个处理机并行地进行秩计算。每个处理机负责一个或多个分组，逐一地用分组中的数据元素与所有（全局）的待排序数据进行比较，计算分组中各数据元素的秩。对于每一个处理机而言，这一个过程是串行的。为保证处理机能准确地找到自己的分组，需要给出分组的起始位置和长度。排序算法描述如下：

输入：带排序数据S[0，…，n-1]，S的长度slen，起始位置startinde，分组长度coupLen。

输出：S对应元素的秩数组indexA [0，…，n-1]。

void IndexSorting（int S[ ]，int sLen，int startindex，int coupLen，int indexA[]）

{

int endindex=startindex+coupLen；；

for（int i=startindex；i

{ int index= Index（S，sLen，S[i]）；

indexA[i]=index；}}

算法中，for循环的时间复杂度为 ，循环内的Index（S，sLen，S[i]）时间复杂度为 ，故该算法的时间复杂度为 。

1.3 并行枚举排序算法

多核处理器是分布式Cache的共享存储并行计算模型[4]。数据传播过程主要体现为读共享，而写数据时，每个处理机所写的存储单元是明确的、相对独立的，因此不存在冲突问题，计算可以达到最大程度的并发性。为确保处理机的均衡，提高算法效率，必须把处理机数作为分组依据之一。算法用Open MP编程模型上的C++语言描述如下：

输入：待排序数组A[]

输出：已排序数组S[]

void ParallIndexSorting（int A[]，int len，int S[]）

{

int coupNum1=（int）（log10（（double）len）+0.9999999）； //

int PNum=omp_get_num_procs（）； //获取处理机（运算核）个数

coupNum=coupNum1*PNum； //计算分组数

int coupLen=（int）len/coupNum； //计算每个分组的长度

int *indexA=new int[len]； //定义“秩”数组，存放数组A[]对应元素的“秩”

int startindex；

#pragma omp parallel for //并发地计算各分组元素的“秩”

for（int i=0；i<=coupNum；i++）

{ if（i< coupNum）

{ startindex=coupLen*i；

IndexSorting（A，len，startindex，coupLen，indexA）；}

else //最后一个分组

{ startindex=coupLen*coupNum；

int ccouplenlen=len-startindex；

IndexSorting（A，len，startindex，ccouplenlen，indexA）；

}

}

//根据“秩”调整数据的位置，直接写入输出数组S[]

#pragma omp parallel for //并发回收数据

for（int i=0；i

{ S[indexA[i]]=A[i]； }}

假设待处理数据为n个元素，处理器有p个运算核，，则分组计算秩的时间为n2/p，收集过程的时间为n/p。根据n2/p与n2的关系可知，所获得的性能几乎与运算核数目p成正比。

2 并行枚举选择算法

根据（m，n）选择网络的原理[1]，只要从每个分组中选择m个最小的数，就可以覆盖n个数据中m个最小的数。因此，（m，n）-枚举选择算法与（m，n）-选择网络的处理方法一样：对n个数据进行分组，然后从每个分组中选择m个最小的数组成新的待选择数据，再分组，再选择，直到找到m个最小的数据为止。不同的是，（m.n）选择网络采用硬件实现，容易实现多路归并选择。对于多核处理器，每个处理机的执行可以视为一个分组上的串行（m，n）-选择，所以，并行枚举（m，n）-选择算法可以建立在串行（m，n）-选择的基础上。

2.1 串行枚举（m，n）-选择算法

为减少计算秩的次数，提高算法效率，先定义leftCmpd和rightCmpd两个参照数，令leftCmpd始终保存秩小于m的最大数，rightCmpd始终保存秩大于m的最小数。初始时，leftCmpd等于一个无穷小量，rightCmpd等于无穷大量。选择处理过程中，任何小于leftCmpd的数据都是所需的m个数据之一，不必再计算它的秩，直接存入输出数组中；任何大于rightCmpd的数都不在所需的数据范围之内，不做任何处理；而介于leftCmpd和rightCmpd之间的数，则可能是所需的数据，需要计算它的秩，如果秩小于m，则是所需的数据，将其存入输出数组中，并调整leftCmpd的值，使之左向逼近m；如果秩大于m，则不是所需的数据，直接调整rightCmpd的值，使之右向逼近m。算法描述如下：

输入：A[0，…，len-1]

输出：S[0，…，m-1]

void M_N_Select（int A[]，int len，int S[]，int m）

{ int leftCmpd，rightCmpd；

leftCmpd=-2147483648； //无穷小数，取最小的int值

rightCmpd=2147483647； //无穷大数，取最大的int值

for（int i=0，j=0；i

{if（A[i]

{ S[j]=A[i]； j++； }

else if（A[i]>rightCmpd）

{ }

else //A[i]介于leftCmpd和rightCmpd之间

{ int index=Index（A，len，A[i]）；

if（index

{ S[j]=A[i]；

j++；

leftCmpd=A[i]；

}

if（index>=m）

{ rightCmpd=A[i]； }}}}

算法中，最好的情形下需要进行1次求秩和m次比较，复杂度为O（n）；最坏的情形下需要进行（n-m）次求秩和m次比较，复杂度为O（n2）。

2.2 并行枚举（m，n）-选择算法

并行枚举（m，n）-选择算法的基本思想是：将待查找数据进行分组，由p个处理机并发地调用串行枚举（m，n）-选择算法对各分组进行（m，n）-选择，再将各分组选出的m个最小数据重新组成待查找数据，递归地进行并行枚举（m，n）-选择，当待查找数据元素的个数足够小（分组数为1）时，直接进行串行（m.n）-枚举选择。算法描述如下：

输入：A[0，…，len-1]

输出：S[0，…，m-1]

Parallel_M_N_Select（int A[]，int len，int S[]，int m）

{ int coupNum1=（int）（log10（（double）len）+0.9999999）；

int PNum=omp_get_num_procs（）； //获取处理机数目

int coupNum=coupNum1*PNum； //计算分组数

int coupLen=（int）len/coupNum； //计算每各分组的长度

while（coupLen<2*m&&&coupNum>1） //调整分组数，确保每个分组长度都大于2m

{ coupNum--；

coupLen=（int）len/coupNum；}

if（coupNum==1） //只有1个分组时，直接进行串行（m.n）-选择

M_N_Select（int A[]，int len，int S[]，int m）；

else //分组数大于1，并行地对各分组作（m.n）-选择

{ int *newA； //用于收集各分组选出的m个最小数据元素

int newAlen=0； // newA的长度

#pragma omp parallel for

for（int i=0；i

{ int alen； //本分组长度

if（i

{ alen=coupLen； }

else //最后一个分组

{ alen=len-（coupLen*i）； }

int * privateA=new int[alen]； //内部数组，存放本分组的待查找的数据元素

int * privateS=new int[m]； //内部数组，存放本分组找出的m个最小数

for（int j=0；j

{ privateA[j]=A[（coupLen*i）+j]； }

M_N_Select（ privateA，alen， privateS，m）；

newAlen+=m；

newA=new int[newAlen]；

for（int j=0；j

{ newA [（m*i）+j]=privateS[j]； }}

Parallel_M_N_Select（newA，newAlen，S，m）； //递归地进行并行（m，n）-选择}}

串行（m，n）-枚举选择算法的最坏时间复杂度为O（n2），采用并行处理后，相当于每个处理机只需要处理n/p个数据，即加速比为接近p2。

2.3 并行枚举k-选择算法

K-选择可以视为特殊的（m，n）-选择算法。因此，并行枚举k-选择可以先进行m=k的并行（m，n）-选择，再对找出的k个数据进行串行k-选择。算法描述如下：

输入：A[0，…，n-1]，k。

输出：第k个最小的数据元素

Parallel_k_selection（A[]，n，k）

{ Parallel_M_N_Select（A[]，len， S[]，k）；

for（int i=1；i

{ if（Index（S[]，n，S[i]） ==k）

return S[i]；}}

该算法的时间复杂度主要取决于并行枚举（m，n）-选择的时间复杂度。因此，其时间复杂度与并行枚举（m，n）-选择算法的时间复杂度相当。

3 结束语

本文利用枚举排序的基本思想，实现了并行的排序、（m，n）-选择、k-选择等算法。算法以串行算法为基础，通过分组技术和Open MP的并行导语实现并行处理，算法直观，简单明了。在Open MP编程模型上使用C++加以实现，运行于具有2个运算核以上的PC机。实验结果与理论分析预计的效果基本相同，证明枚举算法在并行计算环境上是可取的、有运用价值的。

参考文献：

[1] 陈国良.并行算法的设计与分析[M]. 3版.北京：高等教育出版社， 2009.

[2] 陈国良.并行算法实践[M].北京：高等教育出版社， 2004.

[3] Thomas H， Cormen Charles E， Leiserson Ronald L.算法导论[M]. 潘金贵，译.北京：机械工业出版社， 2009.

[4] 周伟明.多核计算与程序设计[M]. 武汉：华中科技大学出版社，2009.

[5] Wilkinson B， Allen M.并行程序设计 [M]. 陆鑫达，译.2版.北京：机械工业出版社， 2005.

[6] 钟诚.并行散列选择算法[J].计算机工程与科学， 2000，22（3）.

[7] 朱战立.数据结构—java语言描述[M].北京：清华大学出版社， 2005.