一種基于劃分與歸并的并行快速排序算法?

賈思禹

（天津工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院 天津 300387）

1 引言

排序操作對(duì)于大數(shù)據(jù)分析顯得尤為重要，這種重要性尤其體現(xiàn)在數(shù)據(jù)挖掘，商業(yè)化應(yīng)用程序，大規(guī)?？茖W(xué)計(jì)算等領(lǐng)域。在所有的排序算法中，快速排序（QuickSort）算法［1］作為一種技術(shù)人員廣為熟知的優(yōu)秀算法，相對(duì)于現(xiàn)存的其它各類(lèi)排序算法而言，在實(shí)際生產(chǎn)過(guò)程中，具有速度快，效率高等優(yōu)點(diǎn)［2～3］，且近年來(lái)被國(guó)內(nèi)外學(xué)者從各種不同的角度進(jìn)行了改進(jìn)與優(yōu)化。

2 研究背景

現(xiàn)如今，大多數(shù)的并行體系結(jié)構(gòu)計(jì)算機(jī)都曾被用于執(zhí)行快速排序算法，早期研究顯示［4～5］排序算法可以執(zhí)行在一種名為multi-ring 的可重構(gòu)多處理器網(wǎng)絡(luò)中。而近年來(lái)又出現(xiàn)了大量增強(qiáng)經(jīng)典快速排序算法的并行快速排序算法。2003 年，P Tsigas和Y Zhang［6］提出了一種實(shí)現(xiàn)在具有cache 一致性機(jī)制的共享地址空間微處理器之上的并行快速排序算法，這一算法中數(shù)據(jù)可以適應(yīng)L1 cache。Codish M［7］等從標(biāo)準(zhǔn)排序函數(shù)庫(kù)的排序算法網(wǎng)絡(luò)入手，對(duì)排序算法底層實(shí)現(xiàn)進(jìn)行優(yōu)化，性能提升明顯。D Koch 和J Torresen［8］在2011 年提出了一種實(shí)現(xiàn)在現(xiàn)場(chǎng)可編程邏輯門(mén)陣列（FPGA）之上的利用運(yùn)行時(shí)重構(gòu)的高性能排序體系結(jié)構(gòu)，在這一架構(gòu)上運(yùn)行的排序?qū)嶒?yàn)結(jié)果顯示，使用FPGA 片上存儲(chǔ)器時(shí)可以達(dá)到2GB/s 的排序數(shù)據(jù)吞吐量，在使用外部存儲(chǔ)器的時(shí)候也可以達(dá)到1GB/s 的數(shù)據(jù)吞吐量。圖形處理器（GPU）內(nèi)部的成千上萬(wàn)個(gè)處理核心都可作為協(xié)處理器用于進(jìn)行基于單指令多數(shù)據(jù)流（SIMD）并行機(jī)制的快速排序算法，例如運(yùn)行在英特爾Xeon Phi 處理器上的Bitonic-Merge 排序算法［9］，又例如E Manca［10］等又將快速排序算法實(shí)現(xiàn)在了CUDA 并行計(jì)算架構(gòu)之上，CUDATM是一種由NVIDIA 推出的通用并行計(jì)算架構(gòu)，該架構(gòu)使GPU 能夠解決復(fù)雜的計(jì)算問(wèn)題，他們實(shí)現(xiàn)的兩種算法：基于GPU 的快速排序以及基于CUDA 的快速排序，他們的實(shí)驗(yàn)結(jié)果表明基于CUDA 的快速排序速度是基于GPU 的快速排序的四倍以上。

近年來(lái)，國(guó)內(nèi)學(xué)者也從各種不同的角度對(duì)基本快速排序進(jìn)行了改進(jìn)與優(yōu)化。

庹清等［11］從混合快速排序與其他排序的角度進(jìn)行優(yōu)化，其算法思想是將基本快速排序與計(jì)數(shù)排序混合，從而構(gòu)造高效的排序方法。其算法效率遠(yuǎn)高于一般快速排序，缺點(diǎn)是在降低算法時(shí)間復(fù)雜度的同時(shí)提高了空間復(fù)雜度，其算法的本質(zhì)是用更多的空間來(lái)?yè)Q取更快的速度。

湯亞玲等［12］從概率學(xué)的角度，先對(duì)待排序數(shù)據(jù)進(jìn)行統(tǒng)計(jì)并選取出最佳的樞軸元素，以確?？焖倥判虻拿恳淮蝿澐治恢枚颊锰幱诖判蛐蛄械恼虚g。其算法的本質(zhì)是先選取合適的樞軸，再進(jìn)行基本快速排序，而選取合適的樞軸本身就是一個(gè)很浪費(fèi)時(shí)間的操作，因此其方法只能在某些特定情況下提高排序效率，而在另一些情況下反而效率低于基本快速排序。

2.1 OpenMP并行函數(shù)庫(kù)

OpenMP并行函數(shù)庫(kù)是一款非常知名的并行函數(shù)庫(kù)，使用它可以在多核處理器架構(gòu)之上開(kāi)發(fā)并行應(yīng)用程序。它為共享存儲(chǔ)多核處理器平臺(tái)提供了一套基于線程并行機(jī)制的應(yīng)用程序編程接口（API）。這些API 中包括了一系列編譯器指令，庫(kù)函數(shù)，以及環(huán)境變量等，用以支持在多種并行架構(gòu)上使用FORTRAN 或C/C++語(yǔ)言開(kāi)發(fā)并行應(yīng)用程序。OpenMP使用fork-join 模型作為其多線程執(zhí)行模型，所謂fork-join 模型是指在一個(gè)并行區(qū)域里，多個(gè)線程并發(fā)地執(zhí)行指令。使用OpenMP 的最大優(yōu)點(diǎn)是所有的處理器核心都可以共享地訪問(wèn)到相同的存儲(chǔ)器數(shù)據(jù)，即所有的處理器核心訪問(wèn)存儲(chǔ)單元有著相同的延遲和帶寬，換言之，OpenMP相對(duì)于其它非共享存儲(chǔ)并行計(jì)算解決方案（如集群計(jì)算、網(wǎng)格計(jì)算）來(lái)說(shuō)用于通信的額外開(kāi)銷(xiāo)極小，而且?guī)缀鯖](méi)有通信延遲。

OpenMP程序運(yùn)行開(kāi)始后只有主線程會(huì)立即執(zhí)行，當(dāng)執(zhí)行到使用OpenMP 指令定義的并行區(qū)域時(shí)，多個(gè)線程才能并行執(zhí)行并行區(qū)域中的代碼，而當(dāng)程序執(zhí)行完并行區(qū)域的代碼后，進(jìn)入串行區(qū)域后，主線程繼續(xù)單獨(dú)執(zhí)行代碼，直至遇到下一個(gè)并行區(qū)域，即在兩個(gè)并行區(qū)域之間，除了主線程執(zhí)行代碼外，其他任何線程將不執(zhí)行。fork-join 模型示意圖如圖1所示。

圖1 fork-join模型示意圖

2008 年5 月，OpenMP3.0 版本問(wèn)世，其中Task結(jié)構(gòu)在此版本中首次被提出，此結(jié)構(gòu)用于定義一個(gè)顯式的任務(wù)。當(dāng)一個(gè)線程在執(zhí)行過(guò)程中遇到Task結(jié)構(gòu)時(shí)，相關(guān)的結(jié)構(gòu)代碼塊就會(huì)生成為一個(gè)顯式的任務(wù)。此外Task 結(jié)構(gòu)允許嵌套，也就是說(shuō)可以在外圍Task 結(jié)構(gòu)中定義內(nèi)嵌Task 結(jié)構(gòu)。2013 年7月，OpenMP4.0版本問(wèn)世，此時(shí)的OpenMP已經(jīng)可以支持單指令多數(shù)據(jù)流（Single Instruction Multiple Data，SIMD），SIMD 是指多核處理器可以同時(shí)的對(duì)多組數(shù)據(jù)執(zhí)行相同的操作。SIMD 指令集基本原理如圖2所示。

圖2 SIMD指令集基本原理

圖2 中R1 和R2 分別為兩個(gè)SIMD 專用寄存器，每個(gè)寄存器整體長(zhǎng)度為128 位，用于存儲(chǔ)需要處理的操作數(shù)。一條指令同時(shí)啟動(dòng)4 個(gè)整型數(shù)相加操作，兩個(gè)寄存器在同一指令周期內(nèi)分別提供四個(gè)32 位操作數(shù)經(jīng)過(guò)硬件加法器相加后，將結(jié)果保存到R3 寄存器中，R3 寄存器同樣也是SIMD 專用128 位寄存器，此時(shí)僅有一條加法指令，但卻對(duì)四組數(shù)據(jù)執(zhí)行了加法操作，這便是單指令多數(shù)據(jù)流的基本原理。

2.2 現(xiàn)有研究成果及比較

DUHU MAN［13］等開(kāi)發(fā)了一種可以兼容標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)qsort 的psort 算法，他們的算法將待排序數(shù)據(jù)集劃分為多個(gè)數(shù)據(jù)塊，并對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行qsort 排序，但在歸并時(shí)使用了額外空間，其算法效率雖然遠(yuǎn)高于一般的快速排序，但是在減低算法時(shí)間復(fù)雜度的同時(shí)提高了空間復(fù)雜度。

Mahafzah B A［14］使用pthread 并行函數(shù)庫(kù)實(shí)現(xiàn)了一種并行快速排序算法，pthread 并行函數(shù)庫(kù)會(huì)在程序啟動(dòng)時(shí)創(chuàng)建一束線程，隨后將工作分配到線程束上。然而這種方式需要相當(dāng)多的線程指定代碼，而且不能保證線程隨著可用處理器的數(shù)量而合理地進(jìn)行擴(kuò)充。相對(duì)地，OpenMP 不會(huì)將工作事先鎖定在設(shè)定的線程數(shù)量中，修改代碼中的配置信息即可。

Rashid L［15］等致力于優(yōu)化并行過(guò)程中產(chǎn)生的數(shù)據(jù)依賴對(duì)性能的影響，他們所提出的算法雖然將快速排序的性能提升了4.17倍，但在測(cè)試過(guò)程中并沒(méi)有考慮處理器的超線程技術(shù)（Hyper-Threading，HT）對(duì)于算法執(zhí)行效率的影響。

3 并行快速排序算法

下面將對(duì)本文中提出的基于劃分與歸并的并行快速排序算法進(jìn)行詳細(xì)介紹，詳細(xì)介紹了該算法的實(shí)現(xiàn)過(guò)程。本文中提出的快速排序算法的基本思想是將一個(gè)未排序的原始數(shù)組經(jīng)過(guò)劃分操作劃分為多個(gè)部分有序數(shù)組，這些部分有序數(shù)組隨后會(huì)經(jīng)過(guò)標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)qsort 以O(shè)penMP 任務(wù)的形式分別進(jìn)行獨(dú)立排序，直至最后原數(shù)組整體有序?；趧澐峙c歸并的并行快速排序算法的框圖如圖3所示。

圖3 基于劃分與歸并的并行快速排序算法框圖

3.1 劃分函數(shù)詳細(xì)設(shè)計(jì)

初期，一個(gè)未經(jīng)排序的數(shù)組a=a0，a1，…an-1，在基準(zhǔn)點(diǎn)（pivot）位置被劃分為兩個(gè)獨(dú)立的子數(shù)組，基準(zhǔn)點(diǎn)位置由MedianOfThree（）函數(shù)所確定，而不是像一般快速排序函數(shù)一樣簡(jiǎn)單地使用第一個(gè)元素作為基準(zhǔn)點(diǎn)，也沒(méi)有采用隨機(jī)選取基準(zhǔn)點(diǎn)的方式，因?yàn)檫@種方式在最壞的情況下，也可能導(dǎo)致快速排序的時(shí)間復(fù)雜度降低至O（n2）。三數(shù)取中法（MedianOfThree）的基本做法是使用最左端、最右端和中心位置上的三個(gè)元素的中值作為樞紐元，三數(shù)取中法實(shí)現(xiàn)代碼如下：

unsigned int mid=low+（（high-low）＞＞1）；

if（arr［mid］＞arr［high］）｛

SWAP（arr［mid］，arr［high］）；｝

if（arr［low］＞arr［high］）｛

SWAP（arr［low］，arr［high］）；｝

if（arr［low］＞arr［mid］）｛

SWAP（arr［mid］，arr［low］）；｝

return mid；

首先，為取到中心位置下標(biāo)采用了右移位運(yùn)算實(shí)現(xiàn)，這是因?yàn)樵诖蠖鄶?shù)處理器上，執(zhí)行除法指令速度較慢，需要30 個(gè)時(shí)鐘周期左右，而移位操作只需要1 個(gè)或幾個(gè)時(shí)鐘周期。而且在對(duì)大樣本排序的過(guò)程中，需要對(duì)大量的子數(shù)組進(jìn)行三數(shù)取中操作，故采用移位操作將大大提升程序執(zhí)行效率。其次，本文所提出算法的實(shí)現(xiàn)代碼中所有的交換操作均采用了宏定義函數(shù)的方式進(jìn)行實(shí)現(xiàn)，即#define SWAP（a，b）｛a=a+b；b=a-b；a=a-b｝，這是由于交換操作在算法實(shí)現(xiàn)的過(guò)程中大量使用，如果采用普通函數(shù)的方式來(lái)實(shí)現(xiàn)的話，每當(dāng)程序流程執(zhí)行到交換函數(shù)時(shí)，為了切換并保護(hù)現(xiàn)場(chǎng)，交換函數(shù)就會(huì)被壓入系統(tǒng)棧，而執(zhí)行結(jié)束之后又會(huì)被彈出系統(tǒng)棧，處理器堆棧操作將會(huì)被反復(fù)執(zhí)行，而宏函數(shù)只是在源代碼文件上的文本替換，沒(méi)有一個(gè)切換并保護(hù)現(xiàn)場(chǎng)的過(guò)程，因此可顯著提高代碼的執(zhí)行效率。

在確定了基準(zhǔn)點(diǎn)位置p 之后，就劃分出了基準(zhǔn)點(diǎn)左側(cè)的左子數(shù)組和基準(zhǔn)點(diǎn)右側(cè)的右子數(shù)組。隨后左右子數(shù)組將在雙線程下同時(shí)進(jìn)行一般的劃分操作，使用相同的基準(zhǔn)點(diǎn)ap。當(dāng)左右子數(shù)組劃分操作結(jié)束以后將返回劃分結(jié)束時(shí)的索引位置，最終的原數(shù)組將被基準(zhǔn)點(diǎn)和左右結(jié)束索引劃分為四個(gè)子數(shù)組，具體代碼實(shí)現(xiàn)如下：

p=MedianOfThree（arr，iL，jR）；

unsigned int d=p；

iR=p-1；

jL=p+1；

#pragma omp parallel num_threads（2）private（d）

｛

#pragma omp task

id=partition（arr，d，iL，iR）；

#pragma omp task

jd=partition（arr，d，jL，jR）；

｝

iL=id+1；

jR=jd-1；

其中iL，iR jL，jR 分別代表了左右子數(shù)組的最左端、最右端下標(biāo)，局部變量d 則保存了基準(zhǔn)點(diǎn)位置p變量的副本，使用pragma 編譯器指示字指示編譯器執(zhí)行OpenMP 并行編程，總線程數(shù)為2，因?yàn)閐在兩個(gè)線程之間需要進(jìn)行互斥訪問(wèn)，所以將其設(shè)置為線程私有化變量。在兩個(gè)OpenMP 任務(wù)中將左右兩個(gè)子數(shù)組劃分為四個(gè)子數(shù)組，id，jd 保存劃分結(jié)束的位置下標(biāo)，用于左右子數(shù)組的再劃分。

3.2 歸并函數(shù)詳細(xì)設(shè)計(jì)

首先，劃分操作結(jié)束后，根據(jù)快速排序函數(shù)劃分操作的特點(diǎn)可知第二部分子數(shù)組（大于部分）和第三部分子數(shù)組（小于等于部分）的長(zhǎng)度是未必相等的，可能出現(xiàn)長(zhǎng)度大于、小于、等于三類(lèi)情況，因此在進(jìn)行交換操作之前，應(yīng)先對(duì)兩個(gè)字?jǐn)?shù)組的長(zhǎng)度進(jìn)行比較，根據(jù)比較結(jié)果進(jìn)行不同的處理。由于長(zhǎng)度計(jì)算操作頻繁出現(xiàn)，因此本文所提出的算法中，計(jì)算數(shù)組長(zhǎng)度操作同樣采用宏函數(shù)LEN實(shí)現(xiàn)，用于提高代碼執(zhí)行效率，代碼實(shí)現(xiàn)如下。

#define LEN（x，y）（（y）-（x）+1）

其中x，y為子數(shù)組的兩端下標(biāo)，y ≥x。以其中一種情況為例，當(dāng)?shù)诙糠肿訑?shù)組較短時(shí)，應(yīng)首先將需要交換的長(zhǎng)度length 設(shè)置為較短子數(shù)組的長(zhǎng)度，將較長(zhǎng)子數(shù)組中超出長(zhǎng)度length 部分元素中下標(biāo)最大的元素同基準(zhǔn)點(diǎn)元素進(jìn)行數(shù)據(jù)交換，并更新基準(zhǔn)點(diǎn)位置變量，再使用一個(gè)臨時(shí)局部變量temp存儲(chǔ)更新后的第三部分子數(shù)組的最左端位置。隨后將循環(huán)地進(jìn)行交換操作，從第二部分子數(shù)組最左端位置和temp位置同時(shí)開(kāi)始，循環(huán)進(jìn)行l(wèi)ength次數(shù)據(jù)交換即可完成兩子數(shù)組的交換操作。其它兩種情況以此類(lèi)推，實(shí)現(xiàn)代碼如下：

unsigned int temp=0；

unsigned int length=0；

if（LEN（iL，p-1）＜LEN（p+1，jR））｛

length=LEN（iL，p-1）；

SWAP（arr［p］，arr［jR-length］）；

temp=p+1；

｝else if（LEN（iL，p-1）＞LEN（p+1，jR））｛

temp=p+1；

length=LEN（p+1，jR）；

SWAP（arr［p］，arr［iL+length］）；

p=iL+length；

｝else｛

temp=p+1；

length=LEN（p+1，jR）；

｝

unsigned int i=0；

#pragma omp parallel for simd num_threads（2）

for（i=0；i ＜length；i++）｛

SWAP（arr［iL+i］，arr［temp+i］）；

｝

其中，在循環(huán)操作上使用了simd 指令，此時(shí)循環(huán)執(zhí)行過(guò)程中，多次迭代過(guò)程將會(huì)使用處理器的simd 指令進(jìn)行并行執(zhí)行，如果處理器不支持SIMD指令集，則編譯器會(huì)將此指令作為注釋處理，不會(huì)影響程序的正常執(zhí)行。

3.3 Qsort函數(shù)

該函數(shù)遞歸地實(shí)現(xiàn)了對(duì)排序過(guò)程中的每個(gè)子數(shù)組進(jìn)行劃分與歸并操作，遞歸結(jié)束的條件為每個(gè)分塊的大小已經(jīng)小于切割長(zhǎng)度變量u，之所以定義切割長(zhǎng)度變量u，目的是為了防止過(guò)度劃分而影響排序操作的整體性能，根據(jù)快速排序原理可知，對(duì)于一個(gè)長(zhǎng)度不大且進(jìn)行過(guò)劃分操作的數(shù)組再使用標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)進(jìn)行排序，速度提升明顯。Qsort函數(shù)實(shí)現(xiàn)代碼如下。

if（iL+u ＜jR）｛

p=ParallelPartition（arr，iL，jR）；

#pragma omp task

Qsort（arr，iL，p-1，u）；

#pragma omp task

Qsort（arr，p+1，jR，u）；

｝else｛

qsort（arr，LEN（iL，jR），sizeof（DATA_TYPE），compare）；｝

其中ParallelPartition 僅對(duì)劃分操作與歸并操作依次調(diào)用，因此不再過(guò)多贅述，由以上代碼可知當(dāng)一個(gè)劃分塊的長(zhǎng)度小于u 時(shí)，程序會(huì)遞歸地對(duì)劃分塊進(jìn)行劃分與歸并操作，直至劃分塊長(zhǎng)度大于等于u 時(shí)，退出遞歸，對(duì)劃分塊使用標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)進(jìn)行排序。

4 實(shí)驗(yàn)設(shè)計(jì)

4.1 硬件選擇

本文中所設(shè)計(jì)的實(shí)驗(yàn)是將算法在三款處理器上進(jìn)行測(cè)試，這三款處理器分別為Intel Core i7-4790、Intel Core i7-2630QM 以 及Intel Core 2 Quad Q9400，表1 對(duì)這些多核處理器的詳細(xì)參數(shù)進(jìn)行了說(shuō)明。

表1 多核處理器詳細(xì)參數(shù)表

4.2 實(shí)驗(yàn)平臺(tái)詳細(xì)設(shè)計(jì)

4.2.1 樣本生成詳細(xì)設(shè)計(jì)

在本文所設(shè)計(jì)的實(shí)驗(yàn)中，主要對(duì)三種數(shù)據(jù)類(lèi)型的大樣本數(shù)據(jù)進(jìn)行排序，這三種數(shù)據(jù)類(lèi)型分別是unsigned int，unsigned long long 和double，即無(wú)符號(hào)32 位整型數(shù)據(jù)，無(wú)符號(hào)64 位整型數(shù)據(jù)以及64 位浮點(diǎn)型數(shù)據(jù)，數(shù)據(jù)均由C++語(yǔ)言編寫(xiě)的生成函數(shù)生成得來(lái)。

值得一提的是，數(shù)據(jù)生成函數(shù)可以生成三種類(lèi)型的數(shù)據(jù)，僅需要經(jīng)過(guò)簡(jiǎn)單的宏常量配置即可實(shí)現(xiàn)切換，且其中任意一種類(lèi)型的數(shù)據(jù)在本文提出的算法中均有三種表示形式，下表2 分別列出了三種數(shù)據(jù)類(lèi)型的三種表示形式。

表2 基本數(shù)據(jù)類(lèi)型表示法

不僅出現(xiàn)在隨機(jī)數(shù)生成函數(shù)中，在本文提及的所有函數(shù)中幾乎都實(shí)現(xiàn)了使用宏常量切換測(cè)試數(shù)據(jù)類(lèi)型的設(shè)計(jì)方式，這種設(shè)計(jì)方式大大提升了算法的通用性。實(shí)驗(yàn)測(cè)試數(shù)據(jù)的數(shù)據(jù)類(lèi)型之所以采用生成類(lèi)型和生成碼同時(shí)描述是因?yàn)?，在某些情況下，僅使用單一形式宏常量描述，在編譯預(yù)處理語(yǔ)句中使用可能會(huì)產(chǎn)生問(wèn)題。

4.2.2 執(zhí)行線程數(shù)與切割塊長(zhǎng)度控制

本文所提出的算法中，執(zhí)行線程數(shù)以及大樣本切割分塊長(zhǎng)度都可以使用宏常量進(jìn)行設(shè)置。

1）執(zhí)行線程數(shù)控制說(shuō)明

OpenMP 規(guī)范定義了用于控制OpenMP 程序執(zhí)行線程數(shù)的環(huán)境變量OMP_NUM_THREADS，以及控制啟用或禁用線程數(shù)動(dòng)態(tài)調(diào)整的環(huán)境變量OMP_DYNAMIC，這兩個(gè)環(huán)境變量均可通過(guò)顯式的庫(kù)函數(shù)omp_set_num_threads 以及omp_set_dynamic對(duì)其值進(jìn)行動(dòng)態(tài)調(diào)整。在默認(rèn)條件下，線程數(shù)動(dòng)態(tài)調(diào)整被定義為禁用，但由于本文所設(shè)計(jì)的實(shí)驗(yàn)需要在不同的線程數(shù)條件下進(jìn)行，需要手動(dòng)啟動(dòng)線程數(shù)動(dòng)態(tài)調(diào)整機(jī)制。

2）切割塊長(zhǎng)度控制說(shuō)明

本文所設(shè)計(jì)的實(shí)驗(yàn)對(duì)大樣本切割分塊長(zhǎng)度進(jìn)行設(shè)置的目的，是為了使算法在不同的多核處理器架構(gòu)下都可以對(duì)性能產(chǎn)生積極影響，當(dāng)切割分塊長(zhǎng)度小于等于高速緩存（cache）容量時(shí)，算法運(yùn)行過(guò)程中的遞歸和迭代過(guò)程的性能就會(huì)得到大大的提升。所謂cache是低容量、高速度的存儲(chǔ)器，通常集成在CPU內(nèi)部，由于主存的數(shù)據(jù)傳輸速度遠(yuǎn)遠(yuǎn)低于CPU 運(yùn)算速度，所以高速緩存就顯得必不可少，因此在大多數(shù)情況下，高速緩存能夠緩解主存帶來(lái)的影響?，F(xiàn)代處理器通常設(shè)有至少兩級(jí)cache，分別被稱作L1 cache 和L2 cache。L1 cache 在一般情況下被分為兩個(gè)部分，即指令cache（L1I）和數(shù)據(jù)cache（L1D）。而L2 cache 并未做此類(lèi)區(qū)分，存儲(chǔ)數(shù)據(jù)和存儲(chǔ)指令通常是相同的。當(dāng)CPU 發(fā)出讀請(qǐng)求（加載）時(shí)，傳輸一個(gè)數(shù)據(jù)項(xiàng)到寄存器中，L1 cache邏輯檢查該數(shù)據(jù)項(xiàng)是否已經(jīng)存放在其中。如果在，則稱為cache命中，且請(qǐng)求能夠被立即響應(yīng)，然而在cache未命中的情況下，數(shù)據(jù)需要從外層cache中取出，最糟糕的情況下需要從主存中獲得。如果所有的cache 都被占用，則需要有硬件實(shí)現(xiàn)的算法來(lái)進(jìn)行數(shù)據(jù)替換，用新的數(shù)據(jù)替換cache 中原有的數(shù)據(jù)。實(shí)驗(yàn)中所使用的三種多核處理器的架構(gòu)示意圖如下圖4所示。

圖4 Haswell和Sandy Bridge處理器架構(gòu)示意圖

圖5 Yorkfield處理器架構(gòu)示意圖

在算法執(zhí)行過(guò)程中，為了提高程序的執(zhí)行效率，使大樣本切割分塊長(zhǎng)度小于等于cache 容量便可以減少仿存次數(shù)，這對(duì)于性能的提高有著至關(guān)重要的作用。對(duì)于圖4 所示的架構(gòu)，應(yīng)使得分塊長(zhǎng)度小于L2 cache，這是因?yàn)長(zhǎng)1 cache 是CPU 的第一層高速緩存，它距離CPU寄存器最近，帶寬最大，延遲最低，管理開(kāi)銷(xiāo)最小，不過(guò)高速緩存均由靜態(tài)RAM組成，結(jié)構(gòu)較復(fù)雜，在CPU 管芯面積不能太大的情況下，L1 級(jí)高速緩存的容量不可能做得太大，因此不能隨L1 cache 將大樣本切割為極小的分塊。而L3 cache 雖然容量極大，但被四個(gè)處理器核心所共享，在算法執(zhí)行的過(guò)程中自然會(huì)產(chǎn)生大量的額外開(kāi)銷(xiāo)用于四個(gè)處理器核之間的通信，因此也不應(yīng)將分塊大小以L3 cache作為標(biāo)尺。而對(duì)于圖5所示的架構(gòu)，是由兩個(gè)雙核處理器組成的四核處理器芯片。每個(gè)雙核處理器具有共享的L2 cache 和獨(dú)立的L1 cache，共有兩組雙核L2高速緩存，因此應(yīng)使得分塊長(zhǎng)度小于L2 cache，因?yàn)殡m然雙核處理器共享的L2 cache 也是存在通信開(kāi)銷(xiāo)的，但是要比四核共享cache 的開(kāi)銷(xiāo)小的多。至于不能隨L1 cache 將大樣本切割為極小的分塊，理由同上。

4.2.3 實(shí)驗(yàn)平臺(tái)其他設(shè)計(jì)

實(shí)驗(yàn)進(jìn)行于Microsoft Windows 10 操作系統(tǒng)之上，使用集成開(kāi)發(fā)環(huán)境Dev-C++內(nèi)嵌的TDM-GCC 4.9.2 64-bit Release 編譯器對(duì)算法代碼進(jìn)行了編譯和連接，為了使算法可以支持SIMD指令集，代碼中使用了OpenMP4.0 并行函數(shù)庫(kù)。算法性能的評(píng)估方式是將其與串行標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)運(yùn)行時(shí)間進(jìn)行對(duì)比，從而得到加速比。實(shí)驗(yàn)數(shù)據(jù)集包括三種類(lèi)型的數(shù)據(jù)，它們分別是無(wú)符號(hào)32 位整型（Uint32），無(wú)符號(hào)64 位整型（Uint64）以及雙精度浮點(diǎn)型（Double）數(shù)據(jù)，這些數(shù)據(jù)集在開(kāi)始排序前都已經(jīng)由生成程序生成為了數(shù)據(jù)集文件，因此可以保證每種算法都可以對(duì)相同的數(shù)據(jù)集進(jìn)行排序。所有的實(shí)驗(yàn)參數(shù)詳見(jiàn)下表3。

表3 實(shí)驗(yàn)參數(shù)集

表3 中將所有平臺(tái)下實(shí)驗(yàn)的切割塊大小都定義為200K，這樣做的目的，一方面是為了在硬件方面可以兼容所有的處理器緩存，另一方面也是為結(jié)果分析提前控制了變量。此外，線程數(shù)為1 的實(shí)驗(yàn)指的是標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)實(shí)驗(yàn)，它與切割塊的大小是無(wú)關(guān)的，僅僅為了對(duì)本文實(shí)現(xiàn)的快速排序進(jìn)行性能評(píng)估。

5 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

這一部分詳細(xì)地描述了在不同的實(shí)驗(yàn)參數(shù)下，排序算法的并行執(zhí)行時(shí)間、串行執(zhí)行時(shí)間、加速比等，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了相關(guān)的統(tǒng)計(jì)分析，各種處理器平臺(tái)下的實(shí)驗(yàn)結(jié)果如下表4所示。

三組實(shí)驗(yàn)結(jié)果包含了本文所提出的算法運(yùn)行在三種處理器平臺(tái)上的并行執(zhí)行時(shí)間，串行執(zhí)行時(shí)間以及加速比。其中加速比是由串行執(zhí)行時(shí)間除以并行執(zhí)行時(shí)間所得的結(jié)果，它代表了本文所提出的算法對(duì)于標(biāo)準(zhǔn)庫(kù)串行快速排序性能的提升。

表4 Intel Core i7-4790處理器平臺(tái)實(shí)驗(yàn)結(jié)果

表5 Intel Core i7-2630QM處理器平臺(tái)實(shí)驗(yàn)結(jié)果

表6 Intel Core 2 Quad Q9400處理器平臺(tái)實(shí)驗(yàn)結(jié)果

5.1 加速比

對(duì)比三組數(shù)據(jù)，不難發(fā)現(xiàn)Uint32數(shù)據(jù)類(lèi)型的加速比一般優(yōu)于Uint64和Double數(shù)據(jù)類(lèi)型，而在三種處理器平臺(tái)中，除Intel Core 2 Quad Q9400 不支持超線程技術(shù)（即Q9400雖有四核心但僅有四個(gè)物理線程同時(shí)執(zhí)行）外，其余兩種處理器平臺(tái)均支持超線程技術(shù)（即四核心八線程），因此它們的加速比一般優(yōu)于非超線程技術(shù)處理器。當(dāng)然也有例外情況產(chǎn)生，這是由于OpenMP 并行函數(shù)庫(kù)OMP_DYNAMIC 環(huán)境變量的定義所導(dǎo)致的，定義該環(huán)境變量之后就允許了對(duì)執(zhí)行線程數(shù)的動(dòng)態(tài)調(diào)整，在任務(wù)調(diào)度的過(guò)程中，會(huì)動(dòng)態(tài)地將任務(wù)劃分為多個(gè)部分，每個(gè)任務(wù)將不可中斷地自始至終執(zhí)行下去，同一個(gè)任務(wù)的不同部分會(huì)根據(jù)當(dāng)前系統(tǒng)資源使用情況受到調(diào)度而同步地執(zhí)行下去，而同時(shí)執(zhí)行的線程個(gè)數(shù)以及任務(wù)不同部分的執(zhí)行順序是不得而知的。使用void omp_set_dynamic（int dynamic_threads）函數(shù)可以覆蓋OMP_DYNAMIC 環(huán)境變量的定義，一旦參數(shù)dynamic_threads被定義為非零值，當(dāng)前任務(wù)的動(dòng)態(tài)調(diào)整即被啟用了，此時(shí)線程組線程數(shù)量根據(jù)系統(tǒng)的資源狀態(tài)動(dòng)態(tài)調(diào)整，因此出現(xiàn)了加速比提升的例外情況。

對(duì)每組數(shù)據(jù)中的加速比按數(shù)據(jù)類(lèi)型進(jìn)行橫向?qū)Ρ?，不難發(fā)現(xiàn)加速比隨著線程數(shù)的提高而不斷提高，即線程數(shù)越高，算法的性能提升越明顯。但在某些特殊情況下出現(xiàn)了加速比小于1 的情況，即算法執(zhí)行效率低于同條件下標(biāo)準(zhǔn)庫(kù)快速排序函數(shù)執(zhí)行效率，經(jīng)觀察發(fā)現(xiàn)，這種情況大多數(shù)出現(xiàn)在定義的執(zhí)行線程數(shù)低于處理器邏輯線程數(shù)的情況下，究其原因可總結(jié)為兩點(diǎn)：1）由于Intel Core 2 Quad Q9400 處理器自身的特點(diǎn)（即兩個(gè)處理器核心共享同一個(gè)L2 cache），故在雙線程情況下，如果其中一個(gè)線程清空了cache 中的內(nèi)容，那么另一個(gè)線程如果需要訪問(wèn)原cache 中的內(nèi)容，只能等待到處理器將數(shù)據(jù)項(xiàng)再次加載到cache 中后，才能繼續(xù)執(zhí)行操作。2）本文中所提出的算法使用了SIMD指令處理循環(huán)部分操作，但是使用SIMD 指令并不總能帶來(lái)性能的提升，使用SIMD指令，只會(huì)大大加快寄存器到寄存器操作的性能，但是會(huì)大大延長(zhǎng)寄存器從內(nèi)存子系統(tǒng)中獲取新數(shù)據(jù)的時(shí)間，這一情況在數(shù)據(jù)長(zhǎng)度過(guò)高（Uint64、Double數(shù)據(jù)類(lèi)型長(zhǎng)度均為64位）且執(zhí)行線程數(shù)過(guò)低的情形下顯得尤為突出。

5.2 并行執(zhí)行時(shí)間

在三種處理器平臺(tái)下，并行執(zhí)行時(shí)間均與線程數(shù)的遞增成反比，即并行執(zhí)行線程數(shù)越高，并行執(zhí)行時(shí)間反而越低，執(zhí)行效率越高。隨著線程數(shù)的增高，程序并行執(zhí)行時(shí)間近似線性，算法可擴(kuò)展性良好。以Uint32數(shù)據(jù)類(lèi)型為例，三種處理器平臺(tái)下算法的并行執(zhí)行時(shí)間如下圖6所示。

對(duì)每組數(shù)據(jù)中的加速比按并行執(zhí)行時(shí)間進(jìn)行縱向?qū)Ρ瓤梢园l(fā)現(xiàn)，并行執(zhí)行時(shí)間與處理器主頻有關(guān)，但在Intel Core i7-2630QM 與Intel Core 2 Quad Q9400 兩處理器平臺(tái)上在數(shù)據(jù)類(lèi)型為Uint32 時(shí)又出現(xiàn)了相差不大的情況，綜合考慮各方面因素，出現(xiàn)這一情況可能由于英特爾睿頻加速技術(shù)在算法執(zhí)行過(guò)程中的影響，英特爾睿頻加速技術(shù)是英特爾酷睿i7 處理器和英特爾酷睿i5 處理器的獨(dú)有特性。該技術(shù)可以智能地加快處理器速度，從而為高負(fù)載任務(wù)提供最佳性能——即最大限度地有效提升性能以匹配工作負(fù)載。CPU 會(huì)確定當(dāng)前工作功率、電流和溫度是否已達(dá)到最高極限，如仍有多余空間，CPU 會(huì)逐漸提高活動(dòng)內(nèi)核的頻率，以進(jìn)一步提高當(dāng)前任務(wù)的處理速度，當(dāng)程序只用到其中的某些核心時(shí)，CPU 會(huì)自動(dòng)關(guān)閉其它未使用的核心，睿頻加速技術(shù)無(wú)需用戶干預(yù)，自動(dòng)實(shí)現(xiàn)。

圖6 三種處理器平臺(tái)下算法的并行執(zhí)行時(shí)間

6 結(jié)語(yǔ)

為了提升排序操作的性能，使用靈活的OpenMP 并行函數(shù)庫(kù)以及C/C++語(yǔ)言標(biāo)準(zhǔn)庫(kù)中提供的快速排序函數(shù)qsort 實(shí)現(xiàn)了一種可以運(yùn)行于任意共享存儲(chǔ)多核計(jì)算機(jī)上的并行快速排序算法。在循環(huán)操作上使用了simd 指令，循環(huán)執(zhí)行過(guò)程中，多次迭代過(guò)程使用處理器的simd 指令進(jìn)行并行執(zhí)行，縮短了算法執(zhí)行時(shí)間，提高了算法執(zhí)行效率。并且在實(shí)驗(yàn)設(shè)計(jì)中，使大樣本切割分塊長(zhǎng)度小于等于cache 容量減少了仿存次數(shù)，并行執(zhí)行線程數(shù)量越多，速度提升越明顯，提高了程序的執(zhí)行效率。