基于多線程歸并排序算法設(shè)計

孫琳琳，侯秀萍，朱 波，孫士明，高 燦

(1.長春工業(yè)大學(xué)計算機(jī)科學(xué)與工程學(xué)院，長春130012;2.蘇州大學(xué)附屬第一醫(yī)院，江蘇蘇州215006)

0 引言

近年來，處理器的發(fā)展已經(jīng)由單核處理器轉(zhuǎn)為多核處理器，由單一主頻的提高轉(zhuǎn)為由多個處理核心進(jìn)行并行計算提高計算性能［1］。雖然多核處理器已經(jīng)成為主要發(fā)展趨勢，但傳統(tǒng)的串行程序并不能在多核處理器結(jié)構(gòu)下獲得性能的提升。為了使串行程序能有效利用多核處理器硬件方面的優(yōu)勢，需要對串行程序進(jìn)行并行化處理。目前比較流行的并行編程模型OpenMp，通過在源程序代碼中添加編譯制導(dǎo)語句，編譯器識別這種標(biāo)識會自動創(chuàng)建線程對程序進(jìn)行并行化。同時在多核處理器系統(tǒng)中，多個線程可以同時在不同的處理核心上運(yùn)行，以達(dá)到真正并行的效果，從而有效提高程序的效率［2］。

排序是處理數(shù)據(jù)過程中常用的運(yùn)算，因此，提升排序算法的執(zhí)行效率具有重要的現(xiàn)實(shí)意義。歸并算法作為排序算法中比較穩(wěn)定的算法，已經(jīng)有很多學(xué)者對其進(jìn)行研究，但大多數(shù)的研究都是基于串行程序的改進(jìn)，如姜忠華等［3］提出了根據(jù)數(shù)據(jù)本身具有的規(guī)律對待排序列進(jìn)行智能歸并排序的劃分方法。白宇等［4］基于分治策略，使用深度優(yōu)先的方法，提出了一種用于線性表的穩(wěn)定原地歸并排序算法，算法在時間復(fù)雜度和空間復(fù)雜度以及排序穩(wěn)定性上達(dá)到了較好的平衡。筆者采用OpenMp編譯制導(dǎo)語句在多核處理器下使用多線程完成對數(shù)據(jù)的排序。

1 并行設(shè)計理論

1.1 數(shù)據(jù)依賴關(guān)系

將串行程序改寫成并行程序，或利用編譯工具將其并行化，都要保證程序的正確性［5］。保證程序的正確性就是使程序中原有的數(shù)據(jù)依賴關(guān)系保持不變。

定義［6］讀集R(pi):表示程序pi在執(zhí)行期間所需參考的所有變量的集合。

寫集W(pi):表示程序pi在執(zhí)行期間要改變的所有變量的集合。

數(shù)據(jù)依賴關(guān)系主要分析數(shù)據(jù)流的相關(guān)性，下面給出數(shù)據(jù)依賴的相關(guān)定義，若pi與pj滿足下列3個條件之一，則稱pi依賴于pj，否則pi與pj之間不存在依賴關(guān)系［5］。

流相關(guān):若W(pi)∩R(pj)≠?，稱pj流依賴于pi，記作▽f。

反相關(guān):若R(pi)∩W(pj)≠?，稱pj反依賴于pi，記作▽u。

輸出相關(guān):若W(pi)∩W(pj)≠?，稱pj輸出依賴于pi，記作▽o。

因此，判斷兩個或多個程序能否并發(fā)執(zhí)行，需要分析它們的數(shù)據(jù)依賴關(guān)系，若不存在數(shù)據(jù)依賴關(guān)系，則能并發(fā)執(zhí)行，且具有可再現(xiàn)性。

1.2 OpenMp任務(wù)分擔(dān)指令

為將任務(wù)合理分配給多個線程，OpenMp提供了for和sections任務(wù)分擔(dān)指令。

1)for指令語法:

for指令指定緊隨它的循環(huán)語句由線程組并行執(zhí)行，將一個for循環(huán)任務(wù)分配到多個線程，此時各個線程各自分擔(dān)其中一部分工作［7，8］。使用for語句將循環(huán)分配到多個線程中是由系統(tǒng)自動進(jìn)行的。

2)section指令語法:

sections制導(dǎo)指令用來實(shí)現(xiàn)多個代碼段的并行執(zhí)行，可并行執(zhí)行的代碼段需要用section指令做標(biāo)記，表示分配每個section到不同的線程。使用section劃分線程是一種手工劃分線程的方式，最終并行性的好壞依賴于程序員［9］。

2 多線程歸并排序算法設(shè)計

2.1 歸并算法并行性分析

設(shè)待排數(shù)組為source［low…h(huán)igh］，其中l(wèi)ow和high表示數(shù)組起始位置和結(jié)束位置下標(biāo)，temp為臨時數(shù)組。采用遞歸方式進(jìn)行歸并排序，排序算法如下:

對程序進(jìn)行數(shù)據(jù)依賴分析:

可得R(S6)∩W(S7)=?，R(S7)∩W(S6)=?，W(S6)∩W(S7)=?，因此S6與S7不存在依賴關(guān)系，相互獨(dú)立，可以并行執(zhí)行。

R(S8)={source［low…mid］，source［mid+1…h(huán)igh］}，W(S8)={source［low…h(huán)igh］}，可得 R(S8)∩W(S6)={source［low…mid］}≠? 且R(S8)∩W(S7)={source［mid+1…h(huán)igh］}≠?，因此 S8流依賴于 S6和S7，S8需要S6與S7都執(zhí)行完畢后才能執(zhí)行。

對于S5，S6，S7，S8可以得到如圖1所示的程序依賴關(guān)系前驅(qū)圖，S6與S7可以并行執(zhí)行，因此歸并排序算法具有并行性。

圖1 程序依賴關(guān)系前驅(qū)圖Fig.1 The program dependence graph of precursor

2.2 歸并算法直接并行化

S6與S7沒有數(shù)據(jù)依賴關(guān)系，理想情況下在雙核處理器系統(tǒng)中設(shè)置兩個線程對其并行執(zhí)行。

使用OpenMp編譯制導(dǎo)指令sections對S6、S7進(jìn)行任務(wù)分擔(dān)，編譯器通過識別section，自動創(chuàng)建兩個線程對S6、S7進(jìn)行并行執(zhí)行。

主要代碼如下所示:

直接并行化是根據(jù)算法本身具有并行的特征，該過程也可理解為將待排序列均勻分成兩組，每組的排序操作互不影響，最后將兩組操作的結(jié)果進(jìn)行合并。

當(dāng)處理器核數(shù)增多，這種直接并行化的方法并不能使處理器資源達(dá)到充分利用。在數(shù)據(jù)量較大的情況下，可以考慮將待排序列分成更多的組，并使用更多的線程同時對數(shù)據(jù)進(jìn)行操作，這樣才能發(fā)揮多核處理器的作用。下面采用分組歸并的方法實(shí)現(xiàn)多線程并行操作。

2.3 分組歸并方法

采用分組的方法將待排序近乎均勻地劃分為n組，為每組分配一個線程，使n個線程并行對每組進(jìn)行歸并排序。當(dāng)n個線程執(zhí)行完畢后，產(chǎn)生n個局部有序的序列，再將n個序列逐步地進(jìn)行合并，最終得到一個整體有序的序列。

由于合并過程是將兩個相鄰的有序組進(jìn)行合并，為了使每次合并時不出現(xiàn)剩余的小組，將n設(shè)置為2N(N≥1的整數(shù))，使用omp_set_num_threads(n)設(shè)置并行域中的線程個數(shù)。

分組過程:每個線程獲取其對應(yīng)的線程編號p=omp_get_thread_num()，計算每組對應(yīng)的數(shù)組下標(biāo)始末位置low=pl/n，high=(p+1)l/n－1(假設(shè)隨機(jī)數(shù)組中有l(wèi)個元素)。

合并過程:n個局部有序序列第1次兩兩合并時需要n/2個線程，第2次合并時需要n/4個線程，直到最后一次合并需要一個線程為止。

主要代碼如下:

以4個線程為例演示分組歸并操作過程(見圖2)。

將待排序列近乎均勻分成4組，使用4個線程對4個組同時進(jìn)行串行歸并排序，當(dāng)4個線程都執(zhí)行完畢，形成4個有序的子序列 A1，A2，A3，A4。再將子序列進(jìn)行合并，由于每次將相鄰的兩個子序列進(jìn)行合并，因此，第1次合并時設(shè)置兩個線程即可，一個線程對A1、A2進(jìn)行合并，形成有序序列B1，一個線程對

A3、A4進(jìn)行合并，形成有序序列B2。當(dāng)兩個線程都執(zhí)行完畢后，再設(shè)置一個線程將B1和B2進(jìn)行合并，最終形成一個整體有序的序列。

由于OpenMp采用fork/join并行模式，只有并行域中的線程全部執(zhí)行完畢，才能執(zhí)行后面非并行部分的代碼［10］。如果各線程操作數(shù)據(jù)的時間相差較多，則最慢完成任務(wù)的線程會造成其他線程的阻塞，這樣會降低處理器效率。采用分組的方法，使各線程操作的數(shù)據(jù)量近乎相等，達(dá)到各線程計算任務(wù)的負(fù)載均衡。

圖2 分組歸并操作圖Fig.2 Packet merge operation diagram

3 實(shí)驗結(jié)果分析

實(shí)驗環(huán)境:使用單核處理器AMD Athlon(主頻2.21 GHz，內(nèi)存1 GByte)、雙核處理器AMD Athlon(主頻2.09 GHz，內(nèi)存1 GByte)、四核處理器AMD Athlon(主頻3.00 GHz，內(nèi)存3 GByte)3臺計算機(jī)，并在Windows Xp操作系統(tǒng)下使用VS2010軟件進(jìn)行實(shí)驗驗證。

實(shí)驗所需要的數(shù)據(jù)是隨機(jī)產(chǎn)生的10萬、50萬、100萬個整數(shù)，分別統(tǒng)計串行、2個線程、4個線程、8個線程、16個線程和32個線程情況下排序所用的時間。由于操作系統(tǒng)內(nèi)部的狀態(tài)隨時在變化，不能保證每次的實(shí)驗結(jié)果都一致，因此實(shí)驗結(jié)果取10次運(yùn)行結(jié)果的平均值。在單核處理器系統(tǒng)中測得串行程序排序所用時間分別為31 ms、188 ms、421.4 ms。表1為多核處理器排序運(yùn)行時間統(tǒng)計表。圖3和圖4分別為雙核、四核加速比統(tǒng)計圖。

表1 多核處理器排序運(yùn)行時間統(tǒng)計表Tab.1 Sort multi－core processor running time table (ms)

從表1可看出，多核處理器下采用多線程分組歸并方法可提高算法的運(yùn)行速度，并且當(dāng)線程數(shù)目與處理器核數(shù)基本相同時，算法運(yùn)行所用的時間最少。若并行過程中使用的線程數(shù)目過多，將導(dǎo)致線程間不斷切換，系統(tǒng)開銷增大，算法并行運(yùn)行時間比串行運(yùn)行的時間更多。

圖3 雙核處理器加速比統(tǒng)計圖Fig.3 Dual－core processor speedup chart

圖4 四核處理器加速比統(tǒng)計圖Fig.4 Quad－core processor speedup chart

從圖3和圖4可以看出，線程數(shù)目一定，數(shù)據(jù)量增大，加速比會隨著增大，即多線程更適合于數(shù)據(jù)量較大的情況。

因此，數(shù)據(jù)量較大使用多線程分組歸并方法時，盡量設(shè)置與處理器核數(shù)相近的線程數(shù)目，這樣才能充分利用處理器資源，使算法運(yùn)行的速度達(dá)到最快。

4 結(jié) 語

筆者設(shè)計了一種多線程歸并排序的方法，統(tǒng)計串行排序時間和并行排序時間以及并行加速比，可以看出，在多核處理器下使用多線程分組歸并方法可以有效提高算法的運(yùn)行速度，該方法相對于串行算法可充分利用多個處理器資源，同時設(shè)置與處理器核數(shù)相近的線程數(shù)目，算法的運(yùn)行速度快。

［1］張劍.多核處理器架構(gòu)下軟件運(yùn)行時驗證方法研究［D］.南京:南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，2010.ZHANG Jian.Research Authentication Method Software Running under the Multi－Core Processor Architecture［D］.Nanjing:School of Computer Science and Technology，Nanjing University of Aeronautics and Astronautics，2010.

［2］徐金棒.基于多核多線程的FFT算法和堆排序算法的并行優(yōu)化和實(shí)現(xiàn)［D］.鄭州:鄭州大學(xué)信息工程學(xué)院，2011.XU Jinbang.The Parallel Optimization and Implementation of FFT Algorithm and the Heap Sort Algorithm Based on Multi－Core and Multi－Threaded ［D］.Zhengzhou:College of Information Technology，Zhengzhou University，2011.

［3］姜忠華，徐文麗，劉家文，等.智能歸并排序［J］.電子設(shè)計工程，2011，19(21):53－55.JIANG Zhonghua，XU Wenli，LIU Jiawen，et al.Intelligently Merge Sort［J］.Electronic Design Engineering，2011，19(21):53－55.

［4］白宇，郭顯娥.深度優(yōu)先穩(wěn)定原地歸并排序的高效算法［J］.計算機(jī)應(yīng)用，2013，33(4):1039－1042.BAI Yu，GUO Xiane.Efficient Algorithm of Depth－First Stable in－Place Merge Sort［J］.Journal of Computer Applications，2013，33(4):1039－1042.

［5］郭龍，陳閎中，葉青.構(gòu)造串行程序?qū)?yīng)的并行任務(wù)(DAG)圖［J］.計算機(jī)工程與應(yīng)用，2007，43(1):41－43.GUO Long，CHEN Hongzhong，YE Qing.Develop Direct Acyclic Graph(DAG)Corresponding to Serial Program ［J］.Computer Engineering and Applications，2007，43(1):41－43.

［6］湯子瀛，哲鳳屏，湯小丹.計算機(jī)操作系統(tǒng)［M］.西安:西安電子科技大學(xué)出版社，1996.TANG Ziying，ZHE Fengping，TANG Xiaodan.Computer Operating System ［M］.Xi'an:Xi'an Electronic and Science University Press，1996.

［7］羅秋明，明仲，劉剛，等.OpenMp編譯原理及實(shí)現(xiàn)技術(shù)［M］.北京:清華大學(xué)出版社，2012.LUO Qiuming，MING Zhong，LIU Gang，et al.OpenMp Compiler Theory and Implementation Techniques［M］.Beijing:Tsinghua University Press，2012.

［8］李建偉.基于多核多線程技術(shù)的通信網(wǎng)仿真算法研究［D］.南京:南京郵電大學(xué)通信與信息工程學(xué)院，2011.LI Jianwei.Based on the Simulation Algorithm Multicore Multithreaded Technology Communication Network［D］.Nanjing:School of Telecommunication and Information Engineering，Nanjing University of Posts and Telecommunications，2011.

［9］蔡佳佳，李名世，鄭鋒.多核微機(jī)基于OpenMP的并行計算［J］.計算機(jī)技術(shù)與發(fā)展，2007，17(10):87－91.CAI Jiajia，LI Mingshi，ZHENG Feng.OpenMp－Based Parallel Computation on Multi－Core PC［J］.Computer Technology and Development，2007，17(10):87－91.

［10］龔向堅，鄒臘梅，胡義香.基于OpenMP的多核系統(tǒng)并行程序設(shè)計方法研究［J］.南華大學(xué)學(xué)報:自然科學(xué)版，2013，27(1):62－64.GONG Xiangjian，ZOU Lamei，HU Yixiang.The Research of Multi－Core System Parallel Program Design Methods Based on OpenMp ［J］.Journal of University of South China:Science and Technology，2013，27(1):62－64.