羅明山

摘要：隨著多核處理器的普及以及云計(jì)算應(yīng)用的推廣，并行算法和并行程序設(shè)計(jì)再度升溫，串行算法向并行算法轉(zhuǎn)換已成為提高計(jì)算性能的重要途徑。盡管枚舉算法在串行環(huán)境下是不可取的，但是，由于其枚舉比較本身具有潛在的并行執(zhí)行的可能性，使得它在并行計(jì)算環(huán)境下大放異彩。該文串行的枚舉排序?yàn)榛A(chǔ)，闡述了基于枚舉的并行排序、并行（m，n）-選擇和并行K-選擇算法，在Open MP編程模型上用C++加以實(shí)現(xiàn)。運(yùn)行于多核CPU上，結(jié)果證明算法是有效的、有利用價(jià)值的。

關(guān)鍵詞：枚舉；秩；排序；選擇算法；并行計(jì)算

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）12-0088-03

排序與選擇是計(jì)算機(jī)處理數(shù)據(jù)的重要工作。經(jīng)過(guò)長(zhǎng)期的研究，人們提出了許多排序算法，包括插入排序、希爾排序、選擇排序、堆排序、冒泡排序、快速排序、歸并排序和基數(shù)排序等。目前，排序算法是《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》課程的重要組成部分。

選擇算法包括k-選擇和（m，n）-選擇。k-選擇是指從數(shù)據(jù)序列中選出第k個(gè)最?。ɑ蜃畲螅┑臄?shù)據(jù)元素；（m，n）-選擇是指從n個(gè)數(shù)據(jù)序列中選擇出m個(gè)最?。ɑ蜃畲螅┑臄?shù)據(jù)元素[1]。選擇算法更適用并行處理，且多采用比較網(wǎng)絡(luò)實(shí)現(xiàn)。

基于枚舉的排序稱為枚舉排序（Enumeration Sorting），也稱為秩排序（Rank Sorting）[2]。在串行環(huán)境下，枚舉排序是不可取的，但是，由于枚舉比較本身具有潛在的并行執(zhí)行的可能性，使得它在并行排序中大放異彩[3]。文獻(xiàn)[1] [2][3]介紹了串行枚舉排序和基于MIMD-CREW模型上的并行枚舉排序。本文介紹多核處理機(jī)上Open MP編程環(huán)境下的并行枚舉排序與并行選擇算法。

1 并行枚舉排序

所謂的“秩”是指數(shù)據(jù)集合中比自身小的數(shù)據(jù)元素的個(gè)數(shù)，它可以直接反映該數(shù)據(jù)在排序數(shù)據(jù)序列中的位置。枚舉排序的基本思想是：逐一地計(jì)算每個(gè)數(shù)據(jù)的“秩”，然后根據(jù)“秩”調(diào)整數(shù)據(jù)的位置，最終實(shí)現(xiàn)排序。

并行枚舉排序由數(shù)據(jù)播送、秩計(jì)算和數(shù)據(jù)收集三個(gè)過(guò)程組成[3]。與MIMD-CREW模型上的并行枚舉排序算法相比，多核處理器上的并行枚舉算法顯得更加簡(jiǎn)單，其基本思想是將待排序數(shù)據(jù)進(jìn)行分組，由多個(gè)處理機(jī)并行地對(duì)各分組進(jìn)行秩計(jì)算，最后根據(jù)秩調(diào)整數(shù)據(jù)的位置，得出排序序列。

1.1秩的計(jì)算

在待排序數(shù)據(jù)序列為S[0，…，n-1]中，計(jì)算數(shù)據(jù)元素S[k]的秩就是逐一地統(tǒng)計(jì)比S[k]小的數(shù)據(jù)元素的個(gè)數(shù)。算法描述如下：

輸入：待排序數(shù)組S[0，..，n-1]和數(shù)據(jù)元素S[k]

輸出：數(shù)據(jù)元素S[k]的秩

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

{ int index=0；

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

if（S[k]

return index；}

算法的時(shí)間復(fù)雜度為O（n）。

1.2 各分組數(shù)據(jù)元素秩的計(jì)算

并行枚舉排序的關(guān)鍵環(huán)節(jié)就是用多個(gè)處理機(jī)并行地進(jìn)行秩計(jì)算。每個(gè)處理機(jī)負(fù)責(zé)一個(gè)或多個(gè)分組，逐一地用分組中的數(shù)據(jù)元素與所有（全局）的待排序數(shù)據(jù)進(jìn)行比較，計(jì)算分組中各數(shù)據(jù)元素的秩。對(duì)于每一個(gè)處理機(jī)而言，這一個(gè)過(guò)程是串行的。為保證處理機(jī)能準(zhǔn)確地找到自己的分組，需要給出分組的起始位置和長(zhǎng)度。排序算法描述如下：

輸入：帶排序數(shù)據(jù)S[0，…，n-1]，S的長(zhǎng)度slen，起始位置startinde，分組長(zhǎng)度coupLen。

輸出：S對(duì)應(yīng)元素的秩數(shù)組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循環(huán)的時(shí)間復(fù)雜度為 ，循環(huán)內(nèi)的Index（S，sLen，S[i]）時(shí)間復(fù)雜度為 ，故該算法的時(shí)間復(fù)雜度為 。

1.3 并行枚舉排序算法

多核處理器是分布式Cache的共享存儲(chǔ)并行計(jì)算模型[4]。數(shù)據(jù)傳播過(guò)程主要體現(xiàn)為讀共享，而寫數(shù)據(jù)時(shí)，每個(gè)處理機(jī)所寫的存儲(chǔ)單元是明確的、相對(duì)獨(dú)立的，因此不存在沖突問(wèn)題，計(jì)算可以達(dá)到最大程度的并發(fā)性。為確保處理機(jī)的均衡，提高算法效率，必須把處理機(jī)數(shù)作為分組依據(jù)之一。算法用Open MP編程模型上的C++語(yǔ)言描述如下：

輸入：待排序數(shù)組A[]

輸出：已排序數(shù)組S[]

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

{

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

int PNum=omp_get_num_procs（）； //獲取處理機(jī)（運(yùn)算核）個(gè)數(shù)

coupNum=coupNum1*PNum； //計(jì)算分組數(shù)

int coupLen=（int）len/coupNum； //計(jì)算每個(gè)分組的長(zhǎng)度

int *indexA=new int[len]； //定義“秩”數(shù)組，存放數(shù)組A[]對(duì)應(yīng)元素的“秩”

int startindex；

#pragma omp parallel for //并發(fā)地計(jì)算各分組元素的“秩”

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

{ if（i< coupNum）

{ startindex=coupLen*i；

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

else //最后一個(gè)分組

{ startindex=coupLen*coupNum；

int ccouplenlen=len-startindex；

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

}

}

//根據(jù)“秩”調(diào)整數(shù)據(jù)的位置，直接寫入輸出數(shù)組S[]

#pragma omp parallel for //并發(fā)回收數(shù)據(jù)

for（int i=0；i

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

假設(shè)待處理數(shù)據(jù)為n個(gè)元素，處理器有p個(gè)運(yùn)算核，，則分組計(jì)算秩的時(shí)間為n2/p，收集過(guò)程的時(shí)間為n/p。根據(jù)n2/p與n2的關(guān)系可知，所獲得的性能幾乎與運(yùn)算核數(shù)目p成正比。

2 并行枚舉選擇算法

根據(jù)（m，n）選擇網(wǎng)絡(luò)的原理[1]，只要從每個(gè)分組中選擇m個(gè)最小的數(shù)，就可以覆蓋n個(gè)數(shù)據(jù)中m個(gè)最小的數(shù)。因此，（m，n）-枚舉選擇算法與（m，n）-選擇網(wǎng)絡(luò)的處理方法一樣：對(duì)n個(gè)數(shù)據(jù)進(jìn)行分組，然后從每個(gè)分組中選擇m個(gè)最小的數(shù)組成新的待選擇數(shù)據(jù)，再分組，再選擇，直到找到m個(gè)最小的數(shù)據(jù)為止。不同的是，（m.n）選擇網(wǎng)絡(luò)采用硬件實(shí)現(xiàn)，容易實(shí)現(xiàn)多路歸并選擇。對(duì)于多核處理器，每個(gè)處理機(jī)的執(zhí)行可以視為一個(gè)分組上的串行（m，n）-選擇，所以，并行枚舉（m，n）-選擇算法可以建立在串行（m，n）-選擇的基礎(chǔ)上。

2.1 串行枚舉（m，n）-選擇算法

為減少計(jì)算秩的次數(shù)，提高算法效率，先定義leftCmpd和rightCmpd兩個(gè)參照數(shù)，令leftCmpd始終保存秩小于m的最大數(shù)，rightCmpd始終保存秩大于m的最小數(shù)。初始時(shí)，leftCmpd等于一個(gè)無(wú)窮小量，rightCmpd等于無(wú)窮大量。選擇處理過(guò)程中，任何小于leftCmpd的數(shù)據(jù)都是所需的m個(gè)數(shù)據(jù)之一，不必再計(jì)算它的秩，直接存入輸出數(shù)組中；任何大于rightCmpd的數(shù)都不在所需的數(shù)據(jù)范圍之內(nèi)，不做任何處理；而介于leftCmpd和rightCmpd之間的數(shù)，則可能是所需的數(shù)據(jù)，需要計(jì)算它的秩，如果秩小于m，則是所需的數(shù)據(jù)，將其存入輸出數(shù)組中，并調(diào)整leftCmpd的值，使之左向逼近m；如果秩大于m，則不是所需的數(shù)據(jù)，直接調(diào)整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； //無(wú)窮小數(shù)，取最小的int值

rightCmpd=2147483647； //無(wú)窮大數(shù)，取最大的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]； }}}}

算法中，最好的情形下需要進(jìn)行1次求秩和m次比較，復(fù)雜度為O（n）；最壞的情形下需要進(jìn)行（n-m）次求秩和m次比較，復(fù)雜度為O（n2）。

2.2 并行枚舉（m，n）-選擇算法

并行枚舉（m，n）-選擇算法的基本思想是：將待查找數(shù)據(jù)進(jìn)行分組，由p個(gè)處理機(jī)并發(fā)地調(diào)用串行枚舉（m，n）-選擇算法對(duì)各分組進(jìn)行（m，n）-選擇，再將各分組選出的m個(gè)最小數(shù)據(jù)重新組成待查找數(shù)據(jù)，遞歸地進(jìn)行并行枚舉（m，n）-選擇，當(dāng)待查找數(shù)據(jù)元素的個(gè)數(shù)足夠小（分組數(shù)為1）時(shí)，直接進(jìn)行串行（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（）； //獲取處理機(jī)數(shù)目

int coupNum=coupNum1*PNum； //計(jì)算分組數(shù)

int coupLen=（int）len/coupNum； //計(jì)算每各分組的長(zhǎng)度

while（coupLen<2*m&&&coupNum>1） //調(diào)整分組數(shù)，確保每個(gè)分組長(zhǎng)度都大于2m

{ coupNum--；

coupLen=（int）len/coupNum；}

if（coupNum==1） //只有1個(gè)分組時(shí)，直接進(jìn)行串行（m.n）-選擇

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

else //分組數(shù)大于1，并行地對(duì)各分組作（m.n）-選擇

{ int *newA； //用于收集各分組選出的m個(gè)最小數(shù)據(jù)元素

int newAlen=0； // newA的長(zhǎng)度

#pragma omp parallel for

for（int i=0；i

{ int alen； //本分組長(zhǎng)度

if（i

{ alen=coupLen； }

else //最后一個(gè)分組

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

int * privateA=new int[alen]； //內(nèi)部數(shù)組，存放本分組的待查找的數(shù)據(jù)元素

int * privateS=new int[m]； //內(nèi)部數(shù)組，存放本分組找出的m個(gè)最小數(shù)

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）； //遞歸地進(jìn)行并行（m，n）-選擇}}

串行（m，n）-枚舉選擇算法的最壞時(shí)間復(fù)雜度為O（n2），采用并行處理后，相當(dāng)于每個(gè)處理機(jī)只需要處理n/p個(gè)數(shù)據(jù)，即加速比為接近p2。

2.3 并行枚舉k-選擇算法

K-選擇可以視為特殊的（m，n）-選擇算法。因此，并行枚舉k-選擇可以先進(jìn)行m=k的并行（m，n）-選擇，再對(duì)找出的k個(gè)數(shù)據(jù)進(jìn)行串行k-選擇。算法描述如下：

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

輸出：第k個(gè)最小的數(shù)據(jù)元素

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]；}}

該算法的時(shí)間復(fù)雜度主要取決于并行枚舉（m，n）-選擇的時(shí)間復(fù)雜度。因此，其時(shí)間復(fù)雜度與并行枚舉（m，n）-選擇算法的時(shí)間復(fù)雜度相當(dāng)。

3 結(jié)束語(yǔ)

本文利用枚舉排序的基本思想，實(shí)現(xiàn)了并行的排序、（m，n）-選擇、k-選擇等算法。算法以串行算法為基礎(chǔ)，通過(guò)分組技術(shù)和Open MP的并行導(dǎo)語(yǔ)實(shí)現(xiàn)并行處理，算法直觀，簡(jiǎn)單明了。在Open MP編程模型上使用C++加以實(shí)現(xiàn)，運(yùn)行于具有2個(gè)運(yùn)算核以上的PC機(jī)。實(shí)驗(yàn)結(jié)果與理論分析預(yù)計(jì)的效果基本相同，證明枚舉算法在并行計(jì)算環(huán)境上是可取的、有運(yùn)用價(jià)值的。

參考文獻(xiàn)：

[1] 陳國(guó)良.并行算法的設(shè)計(jì)與分析[M]. 3版.北京：高等教育出版社， 2009.

[2] 陳國(guó)良.并行算法實(shí)踐[M].北京：高等教育出版社， 2004.

[3] Thomas H， Cormen Charles E， Leiserson Ronald L.算法導(dǎo)論[M]. 潘金貴，譯.北京：機(jī)械工業(yè)出版社， 2009.

[4] 周偉明.多核計(jì)算與程序設(shè)計(jì)[M]. 武漢：華中科技大學(xué)出版社，2009.

[5] Wilkinson B， Allen M.并行程序設(shè)計(jì) [M]. 陸鑫達(dá)，譯.2版.北京：機(jī)械工業(yè)出版社， 2005.

[6] 鐘誠(chéng).并行散列選擇算法[J].計(jì)算機(jī)工程與科學(xué)， 2000，22（3）.

[7] 朱戰(zhàn)立.數(shù)據(jù)結(jié)構(gòu)—java語(yǔ)言描述[M].北京：清華大學(xué)出版社， 2005.