賈思禹

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

1 引言

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

2 研究背景

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

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

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

湯亞玲等［12］從概率學(xué)的角度，先對待排序數(shù)據(jù)進(jìn)行統(tǒng)計并選取出最佳的樞軸元素，以確保快速排序的每一次劃分位置都正好處于待排序序列的正中間。其算法的本質(zhì)是先選取合適的樞軸，再進(jìn)行基本快速排序，而選取合適的樞軸本身就是一個很浪費時間的操作，因此其方法只能在某些特定情況下提高排序效率，而在另一些情況下反而效率低于基本快速排序。

2.1 OpenMP并行函數(shù)庫

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

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

圖1 fork-join模型示意圖

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

圖2 SIMD指令集基本原理

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

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

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

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

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

3 并行快速排序算法

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

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

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

初期，一個未經(jīng)排序的數(shù)組a=a0，a1，…an-1，在基準(zhǔn)點（pivot）位置被劃分為兩個獨立的子數(shù)組，基準(zhǔn)點位置由MedianOfThree（）函數(shù)所確定，而不是像一般快速排序函數(shù)一樣簡單地使用第一個元素作為基準(zhǔn)點，也沒有采用隨機選取基準(zhǔn)點的方式，因為這種方式在最壞的情況下，也可能導(dǎo)致快速排序的時間復(fù)雜度降低至O（n2）。三數(shù)取中法（MedianOfThree）的基本做法是使用最左端、最右端和中心位置上的三個元素的中值作為樞紐元，三數(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)采用了右移位運算實現(xiàn)，這是因為在大多數(shù)處理器上，執(zhí)行除法指令速度較慢，需要30 個時鐘周期左右，而移位操作只需要1 個或幾個時鐘周期。而且在對大樣本排序的過程中，需要對大量的子數(shù)組進(jìn)行三數(shù)取中操作，故采用移位操作將大大提升程序執(zhí)行效率。其次，本文所提出算法的實現(xiàn)代碼中所有的交換操作均采用了宏定義函數(shù)的方式進(jìn)行實現(xiàn)，即#define SWAP（a，b）｛a=a+b；b=a-b；a=a-b｝，這是由于交換操作在算法實現(xiàn)的過程中大量使用，如果采用普通函數(shù)的方式來實現(xiàn)的話，每當(dāng)程序流程執(zhí)行到交換函數(shù)時，為了切換并保護(hù)現(xiàn)場，交換函數(shù)就會被壓入系統(tǒng)棧，而執(zhí)行結(jié)束之后又會被彈出系統(tǒng)棧，處理器堆棧操作將會被反復(fù)執(zhí)行，而宏函數(shù)只是在源代碼文件上的文本替換，沒有一個切換并保護(hù)現(xiàn)場的過程，因此可顯著提高代碼的執(zhí)行效率。

在確定了基準(zhǔn)點位置p 之后，就劃分出了基準(zhǔn)點左側(cè)的左子數(shù)組和基準(zhǔn)點右側(cè)的右子數(shù)組。隨后左右子數(shù)組將在雙線程下同時進(jìn)行一般的劃分操作，使用相同的基準(zhǔn)點ap。當(dāng)左右子數(shù)組劃分操作結(jié)束以后將返回劃分結(jié)束時的索引位置，最終的原數(shù)組將被基準(zhǔn)點和左右結(jié)束索引劃分為四個子數(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)點位置p變量的副本，使用pragma 編譯器指示字指示編譯器執(zhí)行OpenMP 并行編程，總線程數(shù)為2，因為d在兩個線程之間需要進(jìn)行互斥訪問，所以將其設(shè)置為線程私有化變量。在兩個OpenMP 任務(wù)中將左右兩個子數(shù)組劃分為四個子數(shù)組，id，jd 保存劃分結(jié)束的位置下標(biāo)，用于左右子數(shù)組的再劃分。

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

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

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

其中x，y為子數(shù)組的兩端下標(biāo)，y ≥x。以其中一種情況為例，當(dāng)?shù)诙糠肿訑?shù)組較短時，應(yīng)首先將需要交換的長度length 設(shè)置為較短子數(shù)組的長度，將較長子數(shù)組中超出長度length 部分元素中下標(biāo)最大的元素同基準(zhǔn)點元素進(jìn)行數(shù)據(jù)交換，并更新基準(zhǔn)點位置變量，再使用一個臨時局部變量temp存儲更新后的第三部分子數(shù)組的最左端位置。隨后將循環(huán)地進(jìn)行交換操作，從第二部分子數(shù)組最左端位置和temp位置同時開始，循環(huán)進(jìn)行l(wèi)ength次數(shù)據(jù)交換即可完成兩子數(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 指令，此時循環(huán)執(zhí)行過程中，多次迭代過程將會使用處理器的simd 指令進(jìn)行并行執(zhí)行，如果處理器不支持SIMD指令集，則編譯器會將此指令作為注釋處理，不會影響程序的正常執(zhí)行。

3.3 Qsort函數(shù)

該函數(shù)遞歸地實現(xiàn)了對排序過程中的每個子數(shù)組進(jìn)行劃分與歸并操作，遞歸結(jié)束的條件為每個分塊的大小已經(jīng)小于切割長度變量u，之所以定義切割長度變量u，目的是為了防止過度劃分而影響排序操作的整體性能，根據(jù)快速排序原理可知，對于一個長度不大且進(jìn)行過劃分操作的數(shù)組再使用標(biāo)準(zhǔn)庫快速排序函數(shù)進(jìn)行排序，速度提升明顯。Qsort函數(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 僅對劃分操作與歸并操作依次調(diào)用，因此不再過多贅述，由以上代碼可知當(dāng)一個劃分塊的長度小于u 時，程序會遞歸地對劃分塊進(jìn)行劃分與歸并操作，直至劃分塊長度大于等于u 時，退出遞歸，對劃分塊使用標(biāo)準(zhǔn)庫快速排序函數(shù)進(jìn)行排序。

4 實驗設(shè)計

4.1 硬件選擇

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

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

4.2 實驗平臺詳細(xì)設(shè)計

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

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

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

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

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

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

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

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

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

2）切割塊長度控制說明

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

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

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

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

4.2.3 實驗平臺其他設(shè)計

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

表3 實驗參數(shù)集

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

5 實驗驗證及結(jié)果分析

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

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

表4 Intel Core i7-4790處理器平臺實驗結(jié)果

表5 Intel Core i7-2630QM處理器平臺實驗結(jié)果

表6 Intel Core 2 Quad Q9400處理器平臺實驗結(jié)果

5.1 加速比

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

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

5.2 并行執(zhí)行時間

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

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

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

6 結(jié)語

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