并行排序的編程方法與應用

黃逸

摘 要：為了發揮多核微型計算機的計算效能，文章在Visual C++和OpenMP環境中探討了并行排序算法的設計和實現方法。首先，將整體排序任務按處理器上的核數均衡地進行分組；然后，在各個計算核中以選擇排序的方式獨立完成子序列的排序；最后，以并行歸并的方式將各個有序子序列形成一個整體的有序序列。實驗表明，并行排序較傳統的串行排序而言，其計算效能有了顯著的提升。

關鍵詞：并行排序；多核計算；選擇排序；歸并排序

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

1 并行排序的編程設計與實現

1.1 OpenMP模型的編程原理

OpenMP（Open Multi Processing）模型是一種共享存儲體系結構上的編程模型，它包含一套編譯指導語句及一個支持函數庫，目前已應用到Unix/Linux，Windows等多種操作系統上，支持的編程語言有Fortran，C/C++等。OpenMP模型的設計初衷是為了提供存儲共享的體系結構和編程平臺，并為編程用戶提供可行的串行程序轉并行化的設計方案[2]。

OpenMP是基于線程技術的并行編程模型，采用“fork-join”方式執行程序。如圖1所示，程序開始時在一個主線程中執行，遇到可并行執行的區域時，便創建一組線程，這些線程可以執行相同的代碼塊；也可以使用共享存儲的方式，并行執行不同的任務[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”編譯指導語句把一個沒有先后相依關系的for循環語句以并行方式執行。由于for循環語句是以并行的方式執行，為此，循環體中的打印輸出語句沒有以順序形式輸出；此外，根據上述的“fork-join”工作原理可知，僅當for并行循環語句執行結束后，程序才輸出“The program is close”。

1.2 并行排序算法的設計

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

（1）提取處理器的核數：在Windows操作系統中，可以調用API函數GetSystemInfo（ ）來提取運行機器其處理器所擁有的核數，相關代碼如下：

int MyModel：：_GetNoOfProcessors（）

{

SYSTEM_INFO kn；

GetSystemInfo（&kn）；

return kn.dwNumberOfProcessors；

}

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

#pragma omp parallel sections

{

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

for（i1=0；i1

{

k=i1；

for（j=i1+1；j

{/*存儲最小數的位置*/

if（a[j]

k=j；

}

if（i1！=k）

{t=a[i1]；a[i1]=a[k]；a[k]=t；}/*完成a[i1]與a[k]數據交換*/

}

.

.

.

#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個有序的子序列，不難發現，可以在微處理器的各個計算核中，用復制的方法把兩個不同的有序子序列歸并為一個有序序列，從而得到2m-1×n個有序的子序列；繼續兩兩歸并，……，如此重復，直至歸并出一個整體的有序序列。相關代碼如下：

#pragma omp parallel sections{

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

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

{/*sub1[]和sub2[]為需要歸并的有序子序列*/

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

if（sub1[i]

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

else

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

for（k=1；k

/*按照從小至大的方式進行歸并*/

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

if（sub1[i]

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

else

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

k++；

}

.

.

.

}

2 并行排序的實驗及分析

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

從表1的實驗結果可以發現，冒泡排序算法的計算耗時最多、選擇排序算法次之，而新設計的并行排序算法為最小。由于冒泡排序和選擇排序均屬于串行算法，所以它們在不同計算核的計算耗時并沒有明顯的差異，與之形成對比的是，新設計的并行排序算法在四核和六核的計算環境中則有了約41%和56%的提升。為此，新設計的并行排序算法是正確和有效的。

3 結語

排序算法在眾多領域中有著廣泛的應用場合，而優秀的排序算法不僅要求高效而且還要求節省資源。為多核架構的微型計算機設計了一種并行的排序算法，新算法將原序列劃分為若干個子序列，然后通過并行的選擇、歸并排序方式來完成最終的排序任務，由于各個子序列的排序沒有前后的相依關系，為此能較好地發揮多核微型計算機的計算效能。

[參考文獻]

[1]周偉明.多核計算與程序設計[M].武漢：華中科技大學出版社，2009.

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

[3]梁海英，王鳳領，譚曉東.數據結構C語言版[M].北京：清華大學出版社，2017.

[4]嚴蔚敏，李冬梅，吳偉民.數據結構C語言版[M].北京：清華大學出版社，2015.