多核計(jì)算環(huán)境下快速排序并行算法的實(shí)現(xiàn).pdf

《多核計(jì)算環(huán)境下快速排序并行算法的實(shí)現(xiàn).pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、多核計(jì)算環(huán)境下快速排序并行算法的實(shí)現(xiàn)游佐勇羅省賢(成都理工大學(xué)信息工程學(xué)院，四川成都610059)[摘要]研究了快速排序算法，并在其基礎(chǔ)上提出了基于多核技術(shù)的OpenMP并行編程模型的快速排序算法。實(shí)驗(yàn)結(jié)果表明，該并行算法具有較高的并行加速比和并行效率?！娟P(guān)鍵詞]多核處理器；OpenMP；并行算法；快速排序I．引言現(xiàn)代計(jì)算機(jī)的多核、眾核技術(shù)正在快速發(fā)展，如何利用多核實(shí)現(xiàn)并行計(jì)算提高計(jì)算效率，已成為高性能計(jì)算技術(shù)領(lǐng)域研究的熱點(diǎn)。對(duì)于配置了多核CPU的共享存儲(chǔ)計(jì)算機(jī)系統(tǒng)，目前OpenMV已是一種共享存儲(chǔ)并行編程模型

2、的工業(yè)標(biāo)準(zhǔn)，具有良好的可編程性，能夠顯著提高編程和計(jì)算效率。本文分析OpenMP的并行編程模型特點(diǎn)，應(yīng)用OpenMP設(shè)計(jì)和實(shí)現(xiàn)一種快速排序并行算法，并進(jìn)行OpenMP并行程序與串行程序性能比較，驗(yàn)證本文所采用的OpenMP并行編程方法的有效性。2．OpengP并行編程簡(jiǎn)介計(jì)算機(jī)多核技術(shù)的發(fā)展帶動(dòng)了并行編程方法的研究和發(fā)展，其中以O(shè)penMP為代表的并行編程方法是多核計(jì)算機(jī)并行編程的主要方式。OpenMP具有簡(jiǎn)單、移植性好和可擴(kuò)展等優(yōu)點(diǎn)，由一組與平臺(tái)無(wú)關(guān)的編譯指導(dǎo)命令(directives)、環(huán)境變量(envir

3、onmentvariables)和運(yùn)行庫(kù)(runtimelibrary)組成。OpenMP的縮主語(yǔ)言目前支持Fortran、C和C++語(yǔ)言，當(dāng)前最新版本為3．0。OpenMP是通過(guò)編譯器對(duì)程序中編譯指導(dǎo)語(yǔ)句的翻譯來(lái)實(shí)現(xiàn)并行計(jì)算的。例如在C／C++語(yǔ)言中，用語(yǔ)句#pragmaompparallel來(lái)標(biāo)識(shí)一段并行執(zhí)行的程序塊。Openl舊編譯指導(dǎo)語(yǔ)句可以根據(jù)需要包含多個(gè)子句項(xiàng)，在沒(méi)有其它約束的條件下，子項(xiàng)可以無(wú)序和任意選擇。例如撐pragmaompparallelfor[子句?】是使用最為頻繁的編譯指導(dǎo)語(yǔ)句，并且可

4、以搭配使用private，firstprivate，if，lastprivate．reduction，schedule等多種子句。OpenMe并行編稃模式主要有兩種：@fork-join模型，常用于開(kāi)發(fā)計(jì)算任務(wù)中內(nèi)在的循環(huán)級(jí)并行性。其中fork負(fù)責(zé)建立多線程，啟動(dòng)多個(gè)線程完成并行計(jì)算量的任務(wù)：ioin使各線程匯集于主線程，由主線程完成串行計(jì)算量的任務(wù)，這種模式較為簡(jiǎn)單直觀。②編寫(xiě)類(lèi)似SPMD形式的程序，利用OpenMP的庫(kù)函數(shù)omp_get_num_threads()和omp_get_thread_num()可

5、以進(jìn)行任務(wù)劃分。本文主要采用第二種方式。3．Oper■P快速排序并行算法作者簡(jiǎn)介：游佐勇，男，重慶人，項(xiàng)士研究生。研究方向：并行計(jì)算。一60一3．1問(wèn)題描述快速排序(quick．sort)算法足對(duì)冒泡排序算法的一種改進(jìn)，由C．A．R．Hoare在1962年提出。它的基本思想是：通過(guò)～次排序?qū)?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按照此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸并行處理，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。3．2串行算法描述設(shè)要排序的數(shù)組為A[O

6、】．．?·A[N-l】，首先任意選取一個(gè)數(shù)據(jù)(通常選用第～個(gè)數(shù)據(jù))作為關(guān)鍵數(shù)據(jù)，然后將所有比它小的數(shù)都放到它之前，所有比它大的數(shù)放到它之后，這個(gè)過(guò)程稱為一次排序。一次排序的算法描述如下：(1)設(shè)有兩個(gè)變?nèi)譏、J，排序開(kāi)始的時(shí)候：I=0，J=N．1；(2)以第一個(gè)數(shù)組元素作為關(guān)鍵數(shù)據(jù)，賦值給key，即key=A[0]：(3)從J開(kāi)始向前搜索，即由后開(kāi)始向前搜索(J-J．1)，找到第一個(gè)小于key的值A(chǔ)【J】，并與A[I】交換；(4)從I開(kāi)始向后搜索，即由前向后搜索(I=I+1)，找到第一個(gè)大于key的A【I】，與

7、A【J】交換：(5)重復(fù)第3、4步，直到I=J；(6)將數(shù)據(jù)A【0】放置到l處；排序的整個(gè)算法采用遞歸調(diào)用一次排序的過(guò)程。設(shè)一次捧序的函數(shù)為qlcpassO，則遞歸形式快速排序算法如下：PROCQuicksort(Arraydata，Integerlow，Integerhigh)(本算法對(duì)data[10w?high]ee的數(shù)據(jù)進(jìn)行快速排序IFlow

8、nd環(huán)ENDPRoC3．3快速捧序并行算法的設(shè)計(jì)與實(shí)現(xiàn)通過(guò)對(duì)傳統(tǒng)快速j{}序串行算法并行化，可以形成快速捧序OpenMP并行算法。首先分析計(jì)算問(wèn)題的數(shù)據(jù)依賴關(guān)系，挖掘其內(nèi)在并行性，然后進(jìn)行數(shù)據(jù)分割，創(chuàng)建N個(gè)線程，為每個(gè)線程分配一份分割后的數(shù)據(jù)，各線程分別對(duì)各自的數(shù)據(jù)進(jìn)行排序后，再利用歸并排序算法進(jìn)行排序。具體過(guò)程如圖l所示。l到N個(gè)線程并行執(zhí)行圖10pengP快速排序流程圖由圖1所示的