并行排序的編程方法與應(yīng)用

黃逸

摘 要：為了發(fā)揮多核微型計(jì)算機(jī)的計(jì)算效能，文章在Visual C++和OpenMP環(huán)境中探討了并行排序算法的設(shè)計(jì)和實(shí)現(xiàn)方法。首先，將整體排序任務(wù)按處理器上的核數(shù)均衡地進(jìn)行分組；然后，在各個(gè)計(jì)算核中以選擇排序的方式獨(dú)立完成子序列的排序；最后，以并行歸并的方式將各個(gè)有序子序列形成一個(gè)整體的有序序列。實(shí)驗(yàn)表明，并行排序較傳統(tǒng)的串行排序而言，其計(jì)算效能有了顯著的提升。

關(guān)鍵詞：并行排序；多核計(jì)算；選擇排序；歸并排序

在不同領(lǐng)域的信息處理過程中，經(jīng)常需要按照某種線性序（如數(shù)的小于關(guān)系）對(duì)一些對(duì)象進(jìn)行排序，以便高效地完成信息的分析和處理。常見的計(jì)算機(jī)排序算法有冒泡排序、選擇排序、插入排序、歸并排序和基數(shù)排序等，通常，可用計(jì)算耗時(shí)指標(biāo)來評(píng)價(jià)這些排序算法的效率和性能。由于現(xiàn)有的排序算法是以串行的工作方式來完成排序的，因此，直接在多核架構(gòu)的微型計(jì)算機(jī)上執(zhí)行，是無法發(fā)揮處理器既有的多核并發(fā)計(jì)算效能的，于是有必要對(duì)現(xiàn)有的排序算法進(jìn)行多核并行運(yùn)算的改進(jìn)[1]。

1 并行排序的編程設(shè)計(jì)與實(shí)現(xiàn)

1.1 OpenMP模型的編程原理

OpenMP（Open Multi Processing）模型是一種共享存儲(chǔ)體系結(jié)構(gòu)上的編程模型，它包含一套編譯指導(dǎo)語句及一個(gè)支持函數(shù)庫，目前已應(yīng)用到Unix/Linux，Windows等多種操作系統(tǒng)上，支持的編程語言有Fortran，C/C++等。OpenMP模型的設(shè)計(jì)初衷是為了提供存儲(chǔ)共享的體系結(jié)構(gòu)和編程平臺(tái)，并為編程用戶提供可行的串行程序轉(zhuǎn)并行化的設(shè)計(jì)方案[2]。

OpenMP是基于線程技術(shù)的并行編程模型，采用“fork-join”方式執(zhí)行程序。如圖1所示，程序開始時(shí)在一個(gè)主線程中執(zhí)行，遇到可并行執(zhí)行的區(qū)域時(shí)，便創(chuàng)建一組線程，這些線程可以執(zhí)行相同的代碼塊；也可以使用共享存儲(chǔ)的方式，并行執(zhí)行不同的任務(wù)[3]。

下面代碼是基于C語言的OpenMP編程示例：

int main（）

{

#pragma omp parallel for

for（int j=0；j<100；j++ ）

{

printf（″j=%d＼n″， j）；

}

printf（″The program is close＼n″）；

}

在上面的示例代碼中，OpenMP使用“#pragma omp parallel for”編譯指導(dǎo)語句把一個(gè)沒有先后相依關(guān)系的for循環(huán)語句以并行方式執(zhí)行。由于for循環(huán)語句是以并行的方式執(zhí)行，為此，循環(huán)體中的打印輸出語句沒有以順序形式輸出；此外，根據(jù)上述的“fork-join”工作原理可知，僅當(dāng)for并行循環(huán)語句執(zhí)行結(jié)束后，程序才輸出“The program is close”。

1.2 并行排序算法的設(shè)計(jì)

為了發(fā)揮多核微型計(jì)算機(jī)的并行計(jì)算能力，結(jié)合OpenMP模型的“fork-join”工作特點(diǎn)，設(shè)計(jì)了如圖2所示的并行排序算法。算法首先提取運(yùn)行機(jī)器其處理器的核數(shù)n，然后把整體序列均衡地分為若干個(gè)子序列；并以選擇排序的方式在各個(gè)計(jì)算核中并行地完成各個(gè)子序列的排序；待各個(gè)子序列的排序結(jié)束后，繼續(xù)用歸并排序的方式并行地歸并出一個(gè)整體的有序序列[4]。算法的設(shè)計(jì)要點(diǎn)如下。

（1）提取處理器的核數(shù)：在Windows操作系統(tǒng)中，可以調(diào)用API函數(shù)GetSystemInfo（ ）來提取運(yùn)行機(jī)器其處理器所擁有的核數(shù)，相關(guān)代碼如下：

int MyModel：：_GetNoOfProcessors（）

{

SYSTEM_INFO kn；

GetSystemInfo（&kn）；

return kn.dwNumberOfProcessors；

}

（2）并行選擇排序：在獲取處理器的核數(shù)后，便可以把待排序任務(wù)均衡地分為2m×n（m>1，m∈N）個(gè)子任務(wù)，對(duì)于這些子序列的排序而言，由于它們之間并沒有前后的相依關(guān)系，所以可在各計(jì)算核中并行地完成排序?？紤]到排序的主要操作是元素的比較和交換，為了避免元素的頻繁交換，這里以選擇排序作為各并行排序任務(wù)的基本算法。相關(guān)代碼如下：

#pragma omp parallel sections

{

#pragma omp section /*“fork”域*/

for（i1=0；i1

{

k=i1；

for（j=i1+1；j

{/*存儲(chǔ)最小數(shù)的位置*/

if（a[j]

k=j；

}

if（i1！=k）

{t=a[i1]；a[i1]=a[k]；a[k]=t；}/*完成a[i1]與a[k]數(shù)據(jù)交換*/

}

.

.

.

#pragma omp section /*“fork”域*/

for（in=0；i2

{

k=in；

for（j=in+1；j

{

if（a[j]

k=j；

}

if（in！=k）

{t=a[in]；a[in]=a[k]；a[k]=t；}

}

}

（3）并行歸并排序：利用上述的并行選擇排序可以得到2m×n個(gè)有序的子序列，不難發(fā)現(xiàn)，可以在微處理器的各個(gè)計(jì)算核中，用復(fù)制的方法把兩個(gè)不同的有序子序列歸并為一個(gè)有序序列，從而得到2m-1×n個(gè)有序的子序列；繼續(xù)兩兩歸并，……，如此重復(fù)，直至歸并出一個(gè)整體的有序序列。相關(guān)代碼如下：

#pragma omp parallel sections{

#pragma omp section/*“fork”域*/

void Merge（float sub1[]，sub2[]，float dest[]）/*按照從小至大的方式進(jìn)行歸并*/

{/*sub1[]和sub2[]為需要?dú)w并的有序子序列*/

i=0；j=0；k=0；

if（sub1[i]

{dest[k]=sub1[i]；i++}

else

{dest[k]=sub2[j]；j++}

for（k=1；k

/*按照從小至大的方式進(jìn)行歸并*/

{ Sub1_Len和Sub2_Len分別為sub1[]和sub2[]序列的長度

if（sub1[i]

{dest[k]=sub1[i]；i++；}

else

{dest[k]=sub2[j]；j++；}

k++；

}

.

.

.

}

2 并行排序的實(shí)驗(yàn)及分析

實(shí)驗(yàn)的硬件環(huán)境是：Intel core i5-6600K四核CPU/Intel core i7 6800K六核CPU、DDR4 2133MHZ 16GB RAM、金士頓SUV400S37/240G固態(tài)硬盤；軟件環(huán)境為：Windows 7專業(yè)版64位、Microsoft visual studio 2015中文版；實(shí)驗(yàn)中需要進(jìn)行對(duì)比的算法有冒泡排序算法、選擇排序算法和新設(shè)計(jì)的并行排序算法。實(shí)驗(yàn)過程中，用rand（）函數(shù)隨機(jī)產(chǎn)生一個(gè)長度為5 000的實(shí)數(shù)序列，然后分別用上述3種算法完成序列的排序；實(shí)驗(yàn)重復(fù)100次，取平均計(jì)算耗時(shí)作為度量各種算法的效能。實(shí)驗(yàn)的具體結(jié)果如表1所示。

從表1的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，冒泡排序算法的計(jì)算耗時(shí)最多、選擇排序算法次之，而新設(shè)計(jì)的并行排序算法為最小。由于冒泡排序和選擇排序均屬于串行算法，所以它們?cè)诓煌?jì)算核的計(jì)算耗時(shí)并沒有明顯的差異，與之形成對(duì)比的是，新設(shè)計(jì)的并行排序算法在四核和六核的計(jì)算環(huán)境中則有了約41%和56%的提升。為此，新設(shè)計(jì)的并行排序算法是正確和有效的。

3 結(jié)語

排序算法在眾多領(lǐng)域中有著廣泛的應(yīng)用場(chǎng)合，而優(yōu)秀的排序算法不僅要求高效而且還要求節(jié)省資源。為多核架構(gòu)的微型計(jì)算機(jī)設(shè)計(jì)了一種并行的排序算法，新算法將原序列劃分為若干個(gè)子序列，然后通過并行的選擇、歸并排序方式來完成最終的排序任務(wù)，由于各個(gè)子序列的排序沒有前后的相依關(guān)系，為此能較好地發(fā)揮多核微型計(jì)算機(jī)的計(jì)算效能。

[參考文獻(xiàn)]

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

[2]雷洪，胡許冰.多核并行高性能計(jì)算OpenMP[M].北京：冶金工業(yè)出版社，2016.

[3]梁海英，王鳳領(lǐng)，譚曉東.數(shù)據(jù)結(jié)構(gòu)C語言版[M].北京：清華大學(xué)出版社，2017.

[4]嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)C語言版[M].北京：清華大學(xué)出版社，2015.