石 嵩 李宏亮 朱 巍

（江南計(jì)算技術(shù)研究所 江蘇無(wú)錫 214083）（shisong1990＠163．com）

陣列眾核處理器上的高效歸并排序算法

石 嵩 李宏亮 朱 巍

（江南計(jì)算技術(shù)研究所 江蘇無(wú)錫 214083）
（shisong1990＠163．com）

排序是計(jì)算機(jī)科學(xué)中最基本的問(wèn)題之一，隨著眾核處理器結(jié)構(gòu)的不斷發(fā)展，設(shè)計(jì)眾核結(jié)構(gòu)上的高效排序算法具有重要意義．眾核處理器的一個(gè)重要方向是陣列眾核處理器，根據(jù)陣列眾核處理器的結(jié)構(gòu)特點(diǎn)，提出了2種面向陣列眾核結(jié)構(gòu)的高效歸并排序算法，通過(guò)利用DMA（direct memory access）多緩沖機(jī)制提高訪存效率、深度平衡歸并策略保持眾多核心之間的負(fù)載均衡、SIMD（single instruction multiple data）歸并方法提高歸并計(jì)算效率以及片上交換歸并策略提高片上數(shù)據(jù)重用率，大幅度提高了陣列眾核處理器的排序性能．在異構(gòu)融合陣列眾核處理器DFMC（deeply－fused many－core）原型系統(tǒng)的實(shí)驗(yàn)結(jié)果表明，算法排序速度達(dá)647MKeys?s（million keys per second），其排序效率（排序速度?峰值性能）是NVIDIA GPU上最快的歸并排序算法（GTX580平臺(tái)）的3．3倍，是Intel Xeon Phi上最快的歸并排序算法的2．7倍．最后，建立了陣列眾核處理器上歸并排序算法的性能分析模型，利用該模型分析了主要結(jié)構(gòu)參數(shù)與算法性能的關(guān)系，對(duì)陣列眾核處理器的研究有一定的指導(dǎo)意義．

排序是計(jì)算機(jī)科學(xué)及算法研究中最基本、最重要的研究問(wèn)題之一［1］，是數(shù)據(jù)庫(kù)、圖運(yùn)算、科學(xué)計(jì)算以及大數(shù)據(jù)等諸多重要應(yīng)用的基礎(chǔ)，排序效率對(duì)這些應(yīng)用程序的性能有重要的影響，在不同計(jì)算平臺(tái)和環(huán)境上不斷提高排序的性能，具有重要的現(xiàn)實(shí)意義．

近年來(lái)，眾核處理器在學(xué)術(shù)界和工業(yè)界得到了廣泛關(guān)注和蓬勃發(fā)展，已在多個(gè)領(lǐng)域得到了廣泛應(yīng)用．當(dāng)前主要的眾核處理器和眾核結(jié)構(gòu)包括NVIDIA的GPU系列、AMD的GPU?APU系列、Intel的MIC（many integrated core）和SCC（single－chip cloud computer）構(gòu)架，以及Tilera［2］，PACS－G［3］，epiphany［4］，MPPA［5］，Godson－T［6］，DFMC［7］等．其中Tilera，PACS－G，epiphany，MPPA，Godson－T，DFMC等屬于陣列眾核處理器，它們的共同特點(diǎn)是以陣列方式組織眾多計(jì)算核心，具有可擴(kuò)展性好、實(shí)現(xiàn)代價(jià)低的優(yōu)點(diǎn)，是眾核處理器發(fā)展的重要方向．

隨著這些新型眾核處理器的不斷涌現(xiàn)，需要重新設(shè)計(jì)適應(yīng)特定體系結(jié)構(gòu)的排序算法，才能最大限度地發(fā)揮出處理器的運(yùn)算潛力．國(guó)內(nèi)外學(xué)者在GPU和Intel Xeon Phi（屬于MIC結(jié)構(gòu)）上開(kāi)展了大量研究工作，并取得了很好的效果［8－11］，但陣列眾核結(jié)構(gòu)上排序算法的研究尚較少．

盡管陣列眾核處理器提供了強(qiáng)大的計(jì)算能力，但是要發(fā)揮好性能需要用戶利用更多的底層硬件特征．針對(duì)排序算法，需要解決3個(gè)關(guān)鍵的問(wèn)題：1）訪存問(wèn)題，陣列眾核中核心數(shù)目多，單個(gè)核心所能分得的帶寬資源少，導(dǎo)致存儲(chǔ)墻問(wèn)題嚴(yán)重；2）眾多核心之間的負(fù)載均衡問(wèn)題；3）開(kāi)發(fā)SIMD級(jí)并行性的問(wèn)題，雖然陣列眾核的計(jì)算核心通常提供SIMD指令以增加并行性，但是以SIMD方式實(shí)現(xiàn)排序并不容易．

本文首先建立了陣列眾核處理器結(jié)構(gòu)的共性抽象模型，然后設(shè)計(jì)了面向陣列眾核結(jié)構(gòu)的高效歸并排序算法．算法通過(guò)利用DMA多緩沖機(jī)制提高訪存效率、深度平衡歸并策略保持核心間的負(fù)載均衡、SIMD歸并方法開(kāi)發(fā)SIMD并行性以及片上交換歸并策略重用片上數(shù)據(jù)，有效提升了排序性能．算法在DFMC原型系統(tǒng)上的實(shí)驗(yàn)結(jié)果優(yōu)于NVIDIA眾核以及Intel Xeon Phi眾核上的基于比較的排序算法．最后，本文建立了算法性能分析模型，并用該模型討論和分析了陣列眾核結(jié)構(gòu)與算法性能的關(guān)系，為陣列眾核結(jié)構(gòu)的研究提供了參考．

1 相關(guān)工作

排序問(wèn)題由來(lái)已久，經(jīng)過(guò)半個(gè)多世紀(jì)的發(fā)展，串行排序算法的研究已經(jīng)非常成熟且許多算法如快速排序、基數(shù)排序等已接近理論最優(yōu)．近些年來(lái)，研究人員主要將精力集中在結(jié)構(gòu)相關(guān)特別是新型體系結(jié)構(gòu)如GPU和MIC等眾核結(jié)構(gòu)上的排序算法的優(yōu)化上，取得了許多進(jìn)展．這些排序算法主要分為2類：基數(shù)排序和基于比較的排序．

基數(shù)排序是最為高效的排序之一，對(duì)于d位的鍵值，其時(shí)間復(fù)雜度是O（dN），文獻(xiàn)［8，12－14］分別提出和實(shí)現(xiàn)了GPU上的基數(shù)排序算法，其中Merrill等人［8］的基數(shù)排序被集成到了Thrust庫(kù)中，是當(dāng)前最快的基數(shù)排序算法．Satish等人［10］實(shí)現(xiàn)了MIC結(jié)構(gòu)上的基數(shù)排序算法，有很好的性能．然而，基數(shù)排序的時(shí)間開(kāi)銷隨著鍵值長(zhǎng)度的增加而增長(zhǎng)，而且，基數(shù)排序不是基于比較的排序，通用性不足．

基于比較的排序是一類通用的排序方法，包括雙調(diào)排序、快速排序、采樣排序（sample sort）和歸并排序等，其時(shí)間復(fù)雜度的下界是O（Nlog N）．

雙調(diào)排序是由Batcher［15］于20世紀(jì)60年代提出的一種排序網(wǎng)絡(luò)算法，采用分治法歸并序列，時(shí)間復(fù)雜度是O（Nlog2N），雖然不是漸進(jìn)最優(yōu)，但是由于其并行性好，且具有訪存連續(xù)、對(duì)界的優(yōu)點(diǎn)，所以在GPU上有很好的運(yùn)用．文獻(xiàn)［16－17］在GPU上實(shí)現(xiàn)了雙調(diào)排序，Greb等人［18］設(shè)計(jì)實(shí)現(xiàn)了GPU上自適應(yīng)雙調(diào)排序（adaptive bitonic sort）算法，將時(shí)間復(fù)雜度從O（Nlog2N）降低到O（Nlog N）．雙調(diào)排序較高的時(shí)間復(fù)雜度限制了其在數(shù)據(jù)量很大的排序中的應(yīng)用．

Sengupta等人［12］首先實(shí)現(xiàn)了GPU上的快速排序算法，隨后Cederman等人［19－20］進(jìn)一步做了改進(jìn)．采樣排序是快速排序的一種推廣，它一次將輸入劃分成多個(gè)部分而非快速排序中的2部分，然后獨(dú)立地排序各個(gè)部分．Leischner等人［21］在GPU上實(shí)現(xiàn)了采樣排序．盡管快速排序的時(shí)間復(fù)雜度是O（Nlog N），但是其并行程序?qū)崿F(xiàn)復(fù)雜，且性能表現(xiàn)不突出．

歸并排序的時(shí)間復(fù)雜度是O（Nlog N），由于并行性好且時(shí)間復(fù)雜度低，是GPU上廣泛使用的排序算法之一［9，14，22－23］，這些工作主要針對(duì)GPU的結(jié)構(gòu)特點(diǎn)在訪存、同步、通信上對(duì)算法做優(yōu)化，使歸并排序算法更適合GPU結(jié)構(gòu)．其中Davidson等人［9］的歸并排序是當(dāng)前GPU上最快的歸并排序算法．Tian等人［11］設(shè)計(jì)了Intel Xeon Phi眾核上的歸并排序算法，是目前最快的歸并排序算法．

由于基數(shù)排序的通用性不夠，而基于比較的其他算法如雙調(diào)排序、快速排序等具有時(shí)間復(fù)雜度高或者并行化困難且并行程序效率不高的缺點(diǎn)，所以本文選取歸并排序進(jìn)行研究．

2 陣列眾核處理器結(jié)構(gòu)

陣列眾核結(jié)構(gòu)最主要的特征是多個(gè)計(jì)算核心以陣列方式（mesh）組織，可以分為同構(gòu)陣列眾核和異構(gòu)陣列眾核2類，其中同構(gòu)陣列眾核全部由計(jì)算核心陣列構(gòu)成，異構(gòu)陣列眾核在計(jì)算核心陣列外還有額外的管理核心，后者可視為前者的一般化情形，本文抽象的陣列眾核結(jié)構(gòu)采用后者，但是所設(shè)計(jì)的算法對(duì)于2種結(jié)構(gòu)均適用．

陣列眾核處理器的整體結(jié)構(gòu)如圖1所示，包括管理核心MPE（management processing element）、計(jì)算核心陣列CPA（computing processing array）、存控和系統(tǒng)接口，通過(guò)片上網(wǎng)絡(luò)NoC互連．

Fig．1 The array－based manycore architecture．圖1 陣列眾核結(jié)構(gòu)

其中MPE是功能完整的通用核心，負(fù)責(zé)提供一些標(biāo)準(zhǔn)服務(wù)如IO代理和消息代理等，也適合運(yùn)行程序的串行部分．CPA由若干計(jì)算核心CPE（computing processing elements）以陣列方式組織構(gòu)成，陣列內(nèi)的CPE可通過(guò)高速的顯式或者隱式的片上通信（如消息）交換數(shù)據(jù)．CPE是功能簡(jiǎn)單的運(yùn)算核心，支持SIMD指令以開(kāi)發(fā)細(xì)粒度的并行性、提高峰值性能，用以加速大規(guī)模的并行任務(wù)．

陣列眾核處理器中CPA的數(shù)據(jù)存儲(chǔ)構(gòu)架如圖2所示．CPE內(nèi)具有片上存儲(chǔ)器SPM（scratched pad memory），或CPA中共享片上存儲(chǔ)器（本文敘述采用前者）．SPM可配置為數(shù)據(jù)Cache結(jié)構(gòu)，也可配置為由軟件顯式管理的局部存儲(chǔ)器，配置為Cache結(jié)構(gòu)可以減輕軟件編程的負(fù)擔(dān)，但是由于需要保持眾多核心之間的Cache一致性，效率比作為局部存儲(chǔ)器低．本文將SPM視為局部存儲(chǔ)器，SPM與主存之間通過(guò)軟件顯式管理的DMA傳輸數(shù)據(jù)．

Fig．2 The data memory hierarchy of CPA．圖2 CPA的數(shù)據(jù)存儲(chǔ)構(gòu)架

從陣列眾核結(jié)構(gòu)可以看出，陣列眾核提供了2種粒度的并行性，核心或陣列之間的粗粒度線程級(jí)并行性SPMD（single program，multiple data）和核心內(nèi)的細(xì)粒度并行性SIMD，因此設(shè)計(jì)陣列眾核上的并行算法要充分利用這2種并行性才能充分發(fā)揮處理器的性能．另外，陣列眾核結(jié)構(gòu)提供的陣列內(nèi)高速片上通信使算法可以通過(guò)交換核心間的數(shù)據(jù)而減少訪存操作．

3 陣列眾核處理器上的歸并排序算法

歸并是指將2個(gè)有序序列合并成1個(gè)新的有序序列．歸并排序是基于歸并操作的排序，它采用分治的策略先將待排序序列分成若干小的子序列，將各個(gè)子序列排序后，利用歸并操作將各子序列逐步歸并成有序序列．對(duì)于長(zhǎng)度為N的序列，串行算法的時(shí)間復(fù)雜度是O（Nlog N），空間復(fù)雜度是O（N）．

3．1 基本的并行歸并排序算法

歸并排序是一種自底向上的分治算法，并行歸并排序算法將數(shù)據(jù)劃分到各個(gè)CPE，各CPE用串行歸并排序算法對(duì)自己所持?jǐn)?shù)據(jù)進(jìn)行排序后，相互協(xié)作將各有序子序列歸并成整體有序的序列．基本并行歸并排序的流程如下：

步驟1．將N個(gè)數(shù)據(jù)均勻劃分到C個(gè)陣列；

步驟2．各陣列將數(shù)據(jù)均勻劃分給陣列內(nèi)的P個(gè)核心；

步驟3．各核心使用歸并排序完成N?（C×P）個(gè)數(shù)據(jù)的排序；

步驟4．陣列內(nèi)將各個(gè)有序子序列歸并成1個(gè)有序序列；

步驟5．C個(gè)陣列協(xié)作將C個(gè)有序子序列歸并成有序序列．

根據(jù)該流程本節(jié)首先實(shí)現(xiàn)一種基本的并行歸并排序算法作為參照，該算法不使用SIMD與片上通信，沒(méi)有顯式管理訪存，CPE內(nèi)的排序使用一般的串行歸并排序算法，CPE間的歸并過(guò)程如算法1所示：

算法1．核間基本歸并算法．

基本并行歸并排序算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，但是該算法沒(méi)有考慮陣列眾核的結(jié)構(gòu)特點(diǎn)，存在以下3個(gè)問(wèn)題：1）沒(méi)有使用SPM導(dǎo)致訪存延遲大且存儲(chǔ)帶寬效率低；2）雖然使用了SPMD，但是各核心間存在負(fù)載不均衡，分析算法1可知，隨著歸并級(jí)數(shù)遞增1級(jí)，參加歸并的CPE的數(shù)目減半；3）沒(méi)有使用處理器提供的SIMD和片上通信對(duì)算法進(jìn)行加速．

根據(jù)陣列眾核的結(jié)構(gòu)特點(diǎn)，本節(jié)接下來(lái)從不同層面解決和優(yōu)化了這些問(wèn)題和算法，在訪存管理上設(shè)計(jì)了DMA多緩沖機(jī)制提高訪存效率，在線程級(jí)并行層次設(shè)計(jì)了深度平衡歸并策略保持核心間的負(fù)載均衡，在SIMD層次設(shè)計(jì)了SIMD歸并方法提高歸并計(jì)算速度，以及利用片上通信提高片上數(shù)據(jù)重用率，獲得了很好的性能提升，最終實(shí)現(xiàn)了2種優(yōu)化的歸并排序算法CPEB－MS（CPE－based merge sort）和CPAB－MS（CPA－based merge sort）．其中CPEB－MS以CPE為單元，即各CPE先將自己所持?jǐn)?shù)據(jù)排序，然后各CPE之間進(jìn)行歸并．CPAB－MS則以CPA為單元，即CPA作為一個(gè)整體將自己所持?jǐn)?shù)據(jù)排序，然后CPA間進(jìn)行歸并．

3．2 CPEB－MS算法

CPEB－MS的整體流程與基本算法相似，先將數(shù)據(jù)分配給各CPE，CPE先用歸并排序?qū)⑺謹(jǐn)?shù)據(jù)排序，然后CPE間協(xié)作完成歸并．該算法從3個(gè)層面——訪存管理、線程級(jí)并行和SIMD——進(jìn)行了優(yōu)化．

3．2．1 訪存管理——DMA多緩沖機(jī)制

基本歸并排序算法的訪存問(wèn)題主要是由于CPE直接讀寫主存（使用LD?ST指令），一方面小數(shù)據(jù)量的訪存操作造成存儲(chǔ)帶寬的利用率低，另一方面計(jì)算過(guò)程和訪存過(guò)程不能實(shí)現(xiàn)并發(fā)執(zhí)行，從而算法整體性能差．

DMA多緩沖機(jī)制在SPM中開(kāi)辟2個(gè)讀緩沖bufA，bufB和1個(gè)寫緩沖bufC，每個(gè)緩沖分為2份，構(gòu)成雙緩沖．以bufA為例，分為bufA0和bufA1，初始時(shí)使用DMA將數(shù)據(jù)裝填到bufA0中，之后CPE使用bufA0中的數(shù)據(jù)進(jìn)行計(jì)算，同時(shí)利用DMA將數(shù)據(jù)裝填到bufA1中；當(dāng)CPE計(jì)算完bufA0的數(shù)據(jù)后等待bufA1的裝填結(jié)果，若已裝填好，則CPE使用bufA1中的數(shù)據(jù)同時(shí)裝填bufA0，持續(xù)這個(gè)過(guò)程直到完成所有數(shù)據(jù)的歸并．

DMA多緩沖的運(yùn)用一方面使得主存的訪問(wèn)次數(shù)大為減少，提高了存儲(chǔ)帶寬的實(shí)際效率，CPE的數(shù)據(jù)訪問(wèn)延遲大為減??；另一方面，多緩沖使得歸并的訪存時(shí)間和計(jì)算時(shí)間重疊，最大限度掩蓋了訪存延遲．

3．2．2 核心負(fù)載均衡——深度平衡歸并策略

使用多線程主要需要考慮的2個(gè)問(wèn)題是負(fù)載均衡和通信，歸并算法需要的核間通信很少，因此主要要解決負(fù)載均衡的問(wèn)題．基本歸并排序算法中的核間歸并過(guò)程會(huì)造成CPE間負(fù)載不均衡的問(wèn)題，即在步驟3中，歸并級(jí)數(shù)每增加1級(jí)，參與歸并的CPE就減少一半（如圖3（a）所示）．針對(duì)這一問(wèn)題，設(shè)計(jì)了一種基于采樣劃分的深度平衡歸并策略，保證在歸并過(guò)程中，所有CPE都始終參與歸并．

采樣劃分通過(guò)采樣的方法將2個(gè)有序序列A和B各劃分成p個(gè)不相交的塊A0，A1，…，Ap－1和B0，B1，…，Bp－1，當(dāng)i≠j時(shí)，Ai和Bj不相交．其中劃分元的選取過(guò)程如算法2所示，根據(jù)p－1個(gè)劃分元，分別將A和B劃分成p塊（長(zhǎng)度可能為0），下標(biāo)相同的塊屬于同一組，完成劃分．

Fig．3 The basic merging processing and the deeplybalanced merging processing（different textures are merging by different CPE）．圖3 基本歸并與深度平衡歸并示意圖

算法2．采樣選取劃分元算法．

可以證明采樣劃分后各個(gè)組的數(shù)據(jù)量是均勻分布（除第1組和最后1組有偏斜）．深度平衡歸并策略如圖3（b）所示，在第k級(jí)（最底層為第0級(jí)），用采樣劃分將2個(gè)子序列劃分成2k組，分別分給2k個(gè)CPE，然后各CPE對(duì)分給自己的數(shù)據(jù)進(jìn)行歸并．從圖3（b）可以看出，每一級(jí)歸并的CPE數(shù)目不變且各CPE的任務(wù)量相當(dāng)，保持了負(fù)載均衡．

3．2．3 使用SIMD——SIMD并行歸并方法

傳統(tǒng)歸并過(guò)程中的循環(huán)體1次寫回1個(gè)數(shù)據(jù)，SIMD并行歸并的目標(biāo)是1次寫回K（SIMD寬度）個(gè)數(shù)據(jù)，從而減少每個(gè)數(shù)據(jù)的時(shí)間攤銷．

20世紀(jì)60年代，Batcher等人［15］提出了基于Batcher比較器的歸并網(wǎng)絡(luò)，如奇偶?xì)w并網(wǎng)絡(luò)、雙調(diào)歸并網(wǎng)絡(luò)，可在O（log N）的時(shí)間內(nèi)完成歸并．圖4顯示了一個(gè)長(zhǎng)度為8的雙調(diào)歸并網(wǎng)絡(luò)，垂直線表示比較器，上（下）端輸出較小（大）值，網(wǎng)絡(luò)通過(guò)lb（8）＝3級(jí)比較操作，可以將2個(gè)長(zhǎng)度為4的有序序列A［0，1，2，3］和B［0，1，2，3］歸并成1個(gè)有序序列．

Fig．4 Bitonic merge network．圖4 雙調(diào)歸并網(wǎng)絡(luò)

利用歸并網(wǎng)絡(luò)，可以實(shí)現(xiàn)1次輸出多個(gè)數(shù)據(jù)的目標(biāo)，長(zhǎng)度為2 K的雙調(diào)歸并網(wǎng)絡(luò)，每次可輸出K個(gè)結(jié)果（較小的K個(gè)數(shù)據(jù)），另外的K個(gè)數(shù)據(jù)則繼續(xù)和接下來(lái)讀入的K個(gè)數(shù)據(jù)進(jìn)行歸并，重復(fù)該過(guò)程直到歸并完所有數(shù)據(jù)．歸并網(wǎng)絡(luò)可映射成SIMD指令實(shí)現(xiàn)，如圖4中，A和B分別放置在2個(gè)向量寄存器中，則每一級(jí)的4個(gè)比較器可以用CPE中SIMD指令集中的1條vmax（取較大值）指令和1條vmin（取較小值）指令實(shí)現(xiàn)，而在1次比較之后，2個(gè)寄存器的值可通過(guò)混洗指令vshuffle混洗，以滿足下一級(jí)比較的輸入位置要求．

為了運(yùn)用SIMD歸并網(wǎng)絡(luò)，需要先將輸入序列排成長(zhǎng)K有序的子序列．該過(guò)程可通過(guò)基于排序網(wǎng)絡(luò)和混洗操作的寄存器排序完成，如圖5所示，將K2個(gè)元素放置在K個(gè)寄存器中，首先用長(zhǎng)度為K的奇偶?xì)w并排序網(wǎng)絡(luò)將它們（如A［0，1，2，3］）排序成K個(gè)長(zhǎng)K有序的序列（如a0，a1，a2，a3），如圖5（a）所示，然后通過(guò)Klb（K）次vshuffle操作將各有序序列混洗到單個(gè)寄存器中（圖5（b））．

Fig．5 In－register sort with SIMD．圖5 SIMD寄存器排序

3．2．4 CPEB－MS算法流程

結(jié)合上述3．2．1～3．2．3小節(jié)的內(nèi)容，總結(jié)出CPEB－MS算法整體流程如下：

步驟1．將N個(gè)數(shù)據(jù)均勻劃分給各CPE（C個(gè)CPA，每個(gè)CPA中P個(gè)CPE，共C×P個(gè)CPE），每個(gè)核心有N?（C×P）個(gè)數(shù)據(jù)；

步驟2．各CPE使用步驟2．1～2．2完成N?（C×P）個(gè)數(shù)據(jù)的排序：

2．1）將所持?jǐn)?shù)據(jù)分為N?（C×P）?M個(gè)組，每組M個(gè)數(shù)據(jù)（可以存放于SPM緩沖中），使用步驟2．1．1～2．1．2對(duì)每一組進(jìn)行排序：

2．1．1）用寄存器排序?qū)⑿蛄信判虺砷L(zhǎng)K（SIMD寬度）有序的序列；

2．1．2）使用lb（M?K）次SIMD歸并，逐步將長(zhǎng)K有序的子序列歸并成1條有序序列；

2．2）各CPE使用lb（N?（C×P）?M）次SIMD歸并將自己所有的長(zhǎng)為M的有序子序列歸并成1個(gè)有序序列（讀寫數(shù)據(jù)使用DMA多緩沖技術(shù)）；

步驟3．CPA內(nèi)各CPE利用lb（P）次深度平衡歸并策略將P個(gè)有序子序列歸并成1個(gè)有序序列（讀寫數(shù)據(jù)使用DMA多緩沖技術(shù)）；

步驟4．C個(gè)CPA繼續(xù)應(yīng)用lb（C）次深度平衡歸并策略將C個(gè)有序子序列歸并成整體有序序列（讀寫數(shù)據(jù)使用DMA多緩沖技術(shù)）．

3．3 CPAB－MS算法

CPEB－MS中各CPE首先將所持?jǐn)?shù)據(jù)排序成有序序列然后CPE間進(jìn)行歸并的流程沒(méi)能利用陣列眾核結(jié)構(gòu)提供的片上通信支持來(lái)減少訪存次數(shù)．因此本文繼續(xù)設(shè)計(jì)了CPAB－MS算法，它將CPA視為一個(gè)整體，算法將數(shù)據(jù)分給各CPA，各CPA先將所持?jǐn)?shù)據(jù)排序，然后CPA之間進(jìn)行歸并．

3．3．1 使用片上通信——片上交換歸并策略

在CPEB－MS算法流程中的步驟2．1中，各CPE排序M個(gè)元素后即將其寫回主存，接著處理后M個(gè)元素．與此不同，片上交換歸并的策略是，各CPE排序完M個(gè)元素后不直接寫回主存，而是由陣列選出P－1個(gè)劃分元，各CPE根據(jù)劃分元?jiǎng)澐炙值腗個(gè)元素，將各分塊發(fā)送到其他對(duì)應(yīng)的CPE（數(shù)據(jù)交換），數(shù)據(jù)交換后，歸并所接收的各分塊，然后CPA內(nèi)利用前綴和計(jì)算出各CPE所持?jǐn)?shù)據(jù)的偏移位置，將其寫回主存，得到長(zhǎng)為P×M的有序序列．

其中，劃分元的選取和深度平衡歸并中的方法類似，不同的是，這里為了降低空間復(fù)雜度采用2級(jí)采樣劃分策略：行劃分和列劃分．首先是行劃分，每個(gè)CPE選取P－1個(gè)代表元發(fā)送到本行第1列的核心Px0（x＝0，1，…，P－1），Px0對(duì)這些數(shù)據(jù)進(jìn)行排序后選取P－1個(gè)代表元發(fā)送給P00，P00對(duì)其排序后選出P－1個(gè)劃分元廣播給所有CPE，完成劃分元的選取．與直接采樣劃分策略相比，這里的2級(jí)劃分策略的空間復(fù)雜度從P2降低到了P3?2．

數(shù)據(jù)交換過(guò)程是一個(gè)全局通信操作，由于各CPE待交換的數(shù)據(jù)長(zhǎng)度可能不一致，通信過(guò)程非常復(fù)雜．為了解決該問(wèn)題，本文設(shè)計(jì)了基于握手的點(diǎn)對(duì)點(diǎn)通信策略來(lái)完成全局通信：共P－1次點(diǎn)對(duì)點(diǎn)通信，每次通信在數(shù)據(jù)傳輸之前源節(jié)點(diǎn)先將子序列長(zhǎng)度發(fā)送給目的節(jié)點(diǎn)（握手）．第i 槡P＋j次通信中（如圖6所示），節(jié)點(diǎn)Pm，n發(fā)送第（mi）槡P＋（nj）塊數(shù)據(jù)Ami，nj①給Pmi，nj，而從Pmi，nj那里接收數(shù)據(jù)，如果這2個(gè)節(jié)點(diǎn)不同行且不同列，則Pm，n與Pmi，nj（Pmi，nj）之間的通信需要1個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)Pmi，n（Pm，nj）轉(zhuǎn)發(fā)，源節(jié)點(diǎn)先把數(shù)據(jù)發(fā)送到轉(zhuǎn)發(fā)節(jié)點(diǎn)上，然后由轉(zhuǎn)發(fā)節(jié)點(diǎn)發(fā)送至目的節(jié)點(diǎn)．該通信模式可以保證所有CPE能并發(fā)進(jìn)行點(diǎn)對(duì)點(diǎn)通信，不會(huì)出現(xiàn)空閑或者死鎖的狀態(tài)．

Fig．6 Data communication processing．圖6 數(shù)據(jù)發(fā)送過(guò)程示意圖

3．3．2 CPAB－MS算法流程

綜合3．2節(jié)和3．3．1節(jié)所設(shè)計(jì)的4項(xiàng)優(yōu)化技術(shù)，總結(jié)出CPAB－MS算法整體流程如下：

步驟1．將N個(gè)數(shù)據(jù)均勻劃分到C個(gè)CPA，每個(gè)陣列有N?C個(gè)數(shù)據(jù)；

步驟2．各CPA將所持?jǐn)?shù)據(jù)分為（N?C）?（P× M）個(gè)組，每組P×M個(gè)數(shù)據(jù)（可以存放于CPA內(nèi)各CPE的SPM中），使用步驟2．1～2．2對(duì)每一組數(shù)據(jù)進(jìn)行排序：

2．1）每個(gè)CPE讀取M個(gè)數(shù)據(jù)到SPM，使用步驟2．1．1～2．1．2完成M個(gè)數(shù)據(jù)的排序：

2．1．1）用寄存器排序?qū)⑿蛄信判虺砷L(zhǎng)K（SIMD寬度）有序的序列；

2．1．2）使用lb（M?K）次SIMD歸并，逐步將長(zhǎng)K有序的子序列歸并成1條有序序列；

2．2）CPA內(nèi)各CPE通過(guò)片上交換歸并策略將P×M個(gè)數(shù)據(jù)排成有序序列；

步驟3．CPA內(nèi)各CPE利用lb（N?（C×P× M））次深度平衡歸并策略將N?（C×P×M）個(gè)有序子序列歸并成1個(gè)有序序列（讀寫數(shù)據(jù)使用DMA多緩沖技術(shù)）；

步驟4．C個(gè)CPA繼續(xù)應(yīng)用lb（C）次深度平衡歸并策略將C個(gè)有序子序列歸并成整體有序序列（讀寫數(shù)據(jù)使用DMA多緩沖技術(shù)）．

4 實(shí)驗(yàn)結(jié)果與分析

4．1 實(shí)驗(yàn)環(huán)境

異構(gòu)融合陣列眾核處理器DFMC的結(jié)構(gòu)包括4個(gè)MPE，4個(gè)CPA共256個(gè)CPE，主頻1．0GHz，支持128b（2個(gè)64b整數(shù)或浮點(diǎn)運(yùn)算）的SIMD指令，每個(gè)CPE擁有32KB局存，局存訪問(wèn)延遲3周期，局存與主存間支持多種DMA模式傳輸，CPA內(nèi)支持片上通信，單次主存訪問(wèn)延遲約100周期，主存帶寬102．4GBps，芯片32位整數(shù)運(yùn)算峰值性能512GOps（giga operations per second）．軟件配置是，MPE運(yùn)行在內(nèi)核為2．6．28版本的Linux系統(tǒng)上，CPE的系統(tǒng)是一個(gè)輕量級(jí)的定制系統(tǒng)，編程環(huán)境是定制的提供并行編程的C語(yǔ)言．

目前DFMC原型系統(tǒng)采用FPGA構(gòu)建，時(shí)鐘頻率2．6MHz，如圖7所示．實(shí)驗(yàn)在該原型系統(tǒng)上進(jìn)行，所得的實(shí)驗(yàn)結(jié)果根據(jù)真實(shí)的時(shí)鐘頻率進(jìn)行校準(zhǔn)．

4．2 優(yōu)化效果

實(shí)驗(yàn)中待排序的數(shù)據(jù)是均勻分布的32位整數(shù)序列，數(shù)據(jù)量從220增長(zhǎng)到256×220，實(shí)驗(yàn)算法包括基本并行歸并、CPEB－MS和CPAB－MS三種．圖8顯示了3種算法的排序速率（序列長(zhǎng)度與排序時(shí)間的比值），結(jié)果表明，與基本算法相比，CPEB－MS和CPAB－MS的排序速度得到了巨大的提升，平均分別提升了158倍和194倍．CPAB－MS的排序速度相對(duì)CPEB－MS平均提升了23%，這是因?yàn)镃PABMS通過(guò)片上通信重用片上數(shù)據(jù)減少了訪存次數(shù)．然而，CPAB－MS中片上通信是有代價(jià)的，將在第5，6節(jié)進(jìn)一步分析．

Fig．7 DFMC FPGA prototype system．圖7 FPGA搭建的DFMC原型系統(tǒng)

Fig．8 Sorting rates of the three merge sort algorithms for varying sequence sizes．圖8 3種歸并排序算法的排序速率

其中各項(xiàng)優(yōu)化技術(shù)所提供的加速比如表1所示．從表1可以看出，多緩沖和深度平衡歸并所提供的加速比非常大，說(shuō)明基本算法中由于訪存低效和負(fù)載不均衡導(dǎo)致的性能問(wèn)題非常嚴(yán)重．與之相比，SIMD歸并和片上交換歸并策略所提供的性能增益相對(duì)較小，這是因?yàn)橥ㄟ^(guò)前2項(xiàng)技術(shù)后，存儲(chǔ)帶寬的利用率已接近極限，此時(shí)，SIMD計(jì)算所帶來(lái)的性能提升受限于訪存瓶頸，而片上交換歸并所減少的訪存次數(shù)受限于CPA內(nèi)各CPE的SPM大小之和．

Table1 Speedups of All Optimization Techniques表1 各優(yōu)化技術(shù)加速比

4．3 與其他平臺(tái)排序算法的比較

實(shí)驗(yàn)選取了近幾年來(lái)眾核處理器上效率最高的幾種比較型排序算法進(jìn)行對(duì)比．在GPU方面，選取了NVIDIA GTX580上的歸并排序（GPU Merge）［9］、NVIDIA Tesla C1060上的采樣排序（GPU Sample）［21］、CPU－GPU（Intel i7 980＋GTX580）混合結(jié)構(gòu)上的采樣排序（Hybrid Sample）［24］；在Intel Xeon Phi眾核上，選取了歸并排序（Xeon Phi Merge）［11］進(jìn)行比較，實(shí)驗(yàn)數(shù)據(jù)均來(lái)源于公開(kāi)發(fā)表的文獻(xiàn)．表2顯示了這些處理器的性能參數(shù)．

Table 2 The Parameters of Referred Processors表2 處理器參數(shù)

實(shí)驗(yàn)結(jié)果如圖9所示，可以看出，在所有這些比較型排序中，DFMC上的實(shí)驗(yàn)結(jié)果是最好的，如數(shù)據(jù)量為16×220時(shí)，DFMC Merge的排序速度達(dá)到647MKeys?s，是GPU Merge的2．7倍，是GPU Sample的5．5倍，是CPU－GPU混合結(jié)構(gòu)上Hybrid Sample的2．4倍；比Xeon Phi上歸并排序排序快36%．折算成同等峰值性能，DFMC上的歸并排序的排序效率（排序速率與峰值性能的比值）是GTX580歸并排序的3．3倍，是Xeon Phi上歸并排序的2．7倍．CPAB－MS算法比其他處理器上比較型排序算法效率高的主要原因是CPAB－MS充分利用了陣列眾核結(jié)構(gòu)的硬件特征，最大限度地發(fā)揮了處理器的性能．

Fig．9 Sorting performance of different methods on different platforms．圖9 不同平臺(tái)排序算法性能比較

5 算法性能模型

本節(jié)建立算法性能的分析模型，用以指導(dǎo)算法的優(yōu)化以及分析陣列眾核結(jié)構(gòu)與算法性能之間的關(guān)系．

5．1 模型建立

陣列眾核上并行歸并程序的執(zhí)行時(shí)間主要包括訪存時(shí)間、計(jì)算時(shí)間和片上通信時(shí)間（針對(duì)CPABMS）．設(shè)τm是歸并過(guò)程中單次單個(gè)元素的平均訪存時(shí)間，τc是歸并過(guò)程中單次單個(gè)元素的平均計(jì)算時(shí)間，τs是單個(gè)元素的平均寄存器排序時(shí)間，τi是單個(gè)元素的平均片上通信時(shí)間．則CPEB－MS算法框架中步驟2的時(shí)間是

其中N，M，K分別表示數(shù)據(jù)量、SPM緩沖中可容納的元素?cái)?shù)目和SIMD寬度，C表示陣列數(shù)，P表示每個(gè)陣列中的核心數(shù)．max（2τm，τc）是由于多緩沖使得計(jì)算時(shí)間和訪存時(shí)間重疊，總的執(zhí)行時(shí)間是這二者的最大值，τm前的系數(shù)2說(shuō)明讀寫2次操作．步驟3和步驟4的時(shí)間之和是

其中Talltoall是片上通信時(shí)間，片上通信時(shí)間與數(shù)據(jù)分布有關(guān)，最好的情形，即已經(jīng)完全有序，無(wú)需通信，Talltoall＝O（1）；最壞的情形，每次點(diǎn)對(duì)點(diǎn)通信的傳輸數(shù)據(jù)量達(dá)到N?（C×P），Talltoall＝P×N?（C×P）×2τi；一般情形，平均時(shí)間是Talltoall，ave＝N?（C×P）×2τi．

CPAB－MS算法的總執(zhí)行時(shí)間是這3個(gè)步驟執(zhí)行時(shí)間之和：

式（3）、式（6）～（8）可以作為陣列眾核上歸并排序算法的性能模型，通過(guò)調(diào)整系數(shù)，可以表示不同結(jié)構(gòu)上的性能模型．例如，若眾核不支持SIMD指令，則K＝1；若眾核具有共享片上存儲(chǔ)，則Talltoall＝0．

5．2 性能模型誤差

我們?cè)贒FMC原型系統(tǒng)上檢驗(yàn)了算法性能模型的準(zhǔn)確度．性能模型中的τm，τc，τs，τi可通過(guò)程序代碼、存儲(chǔ)帶寬和時(shí)鐘頻率計(jì)算出來(lái)，其他系數(shù)可由結(jié)構(gòu)參數(shù)得到，從而算出執(zhí)行時(shí)間的估計(jì)值．估計(jì)值和實(shí)驗(yàn)值的結(jié)果如圖10所示．其中CPEB－MS算法性能模型的平均誤差在5%以內(nèi)，CPAB－MS算法性能模型的平均誤差會(huì)達(dá)到11%，這是因?yàn)镃PABMS中片上通信過(guò)程里有大量的同步操作，帶來(lái)一些額外的不確定性時(shí)間．

Fig．10 Comparison between estimated values and experimental values．圖10 實(shí)驗(yàn)值與理論值比較

從實(shí)驗(yàn)結(jié)果可以看出，算法性能模型的準(zhǔn)確度高，可以用來(lái)分析不同結(jié)構(gòu)參數(shù)下的算法性能．

6 進(jìn)一步討論

本節(jié)利用第5節(jié)建立的算法性能模型，對(duì)算法優(yōu)化以及算法性能與眾核結(jié)構(gòu)之間的關(guān)系進(jìn)行一些分析和探索．

在算法優(yōu)化方面，可以分析出如下結(jié)論：

1）陣列眾核上歸并排序算法的時(shí)間復(fù)雜度是O（Nlb（N）?（C×P）），降低并行歸并排序時(shí)間的主要途徑是降低τm和τc．本文設(shè)計(jì)的多緩沖策略和SIMD歸并方法即是降低了τm和τc．

2）從式（8）可以看出τm和τc的系數(shù)之和是與算法無(wú)關(guān)的恒定值．對(duì)于核數(shù)較多的眾核結(jié)構(gòu)，通常τm比τc大，因此提高排序性能的一種策略是減少a而增加b來(lái)降低整個(gè)執(zhí)行時(shí)間，即以增加計(jì)算來(lái)減少訪存時(shí)間，本文中CPAB－MS與CPEB－MS相比就是通過(guò)重用片上數(shù)據(jù)減小訪存次數(shù)來(lái)提高性能．

3）CPAB－MS的執(zhí)行時(shí)間中Talltoall受待排序序列數(shù)據(jù)分布的影響，最壞情形的通信開(kāi)銷大，性能將比CPEB－MS差，而一般情形時(shí)，其性能比CPEBMS好．

陣列眾核結(jié)構(gòu)中的核心數(shù)目、存儲(chǔ)帶寬、SPM大小以及SIMD寬度，與算法性能密切相關(guān)，可以依據(jù)算法性能模型進(jìn)行定量分析．

6．1 核心數(shù)目與存儲(chǔ)帶寬

核心數(shù)目對(duì)排序性能的影響有2方面，一方面核心數(shù)目越多，計(jì)算能力越強(qiáng)，單位時(shí)間可完成的比較操作越多；另一方面，核心數(shù)目的增加會(huì)導(dǎo)致單個(gè)核心所分得的存儲(chǔ)帶寬減小，從而排序容易陷入訪存瓶頸．

在第4節(jié)的陣列眾核歸并排序性能模型中，式（3）和式（6）中的τm是和存儲(chǔ)帶寬以及核心數(shù)目有關(guān)的變量，設(shè)帶寬為B（單位為Bps），CPE數(shù)目為P，存儲(chǔ)帶寬利用率為ρ，鍵值大小為w（單位為B），則

以式（3）為例，當(dāng)N很大時(shí)，執(zhí)行時(shí)間主要是由式中第2項(xiàng)決定，記為Tcpe，second．而當(dāng)2τm＞τc時(shí)，將式（9）代入，有

由式（10）可看出Tcpe，second與P無(wú)關(guān)，即使增加P也無(wú)法再減少Tcpe，second，繼而對(duì)Tcpe的影響非常有限．因此，2τm＝τc是一個(gè)臨界條件，即

若2τm＜τc說(shuō)明排序是計(jì)算受限的，而2τm＞τc則是訪存受限．當(dāng)未來(lái)陣列眾核處理器核心數(shù)目和存儲(chǔ)帶寬的擴(kuò)展關(guān)系滿足式（11）時(shí)，算法有很好的可擴(kuò)展性．

根據(jù)當(dāng)前DFMC的配置情況，可以算出P＝42是臨界點(diǎn)，即當(dāng)前DFMC結(jié)構(gòu)為訪存受限．單個(gè)CPA上使用不同CPE數(shù)目的CPEB－MS算法的實(shí)驗(yàn)結(jié)果如圖11所示（數(shù)據(jù)量為16×220）．從圖11可以看出臨界CPE數(shù)在32～64之間，之后，執(zhí)行時(shí)間隨CPE數(shù)目增加的下降速度變緩慢．根據(jù)式（11），DFMC單個(gè)CPA的帶寬應(yīng)當(dāng)提高約50%，才能最大限度發(fā)揮64個(gè)CPE的計(jì)算性能，此時(shí)，算法的排序速度將提高25%．

Fig．11 Sorting time for varying number of CPEs．圖11 排序時(shí)間與CPE數(shù)目關(guān)系

6．2 片上存儲(chǔ)大小

根據(jù)算法性能模型式（6），可算出DFMC結(jié)構(gòu)上排序時(shí)間與片上存儲(chǔ)開(kāi)辟的緩沖區(qū)大小的關(guān)系，如圖12所示（數(shù)據(jù)量為16×220）．從圖12可以看出，排序時(shí)間隨緩沖區(qū)大小增長(zhǎng)呈對(duì)數(shù)級(jí)下降，可見(jiàn)，通過(guò)增大SPM大小可以提升排序性能，但空間有限．

Fig．12 Sorting time for varying buffer sizes．圖12 排序時(shí)間隨緩沖大小關(guān)系

6．3 SIMD寬度

SIMD歸并算法中，對(duì)于寬度為K的SIMD指令，歸并K個(gè)元素需要1個(gè)lb（2 K）級(jí)的歸并網(wǎng)絡(luò)，每級(jí)網(wǎng)絡(luò)需要2次比較操作和2次混洗操作，所以前面性能模型中的τc可表示成

其中Θ表示緊致界［25］，由式（12）結(jié)合式（3）、式（6）可以看出，訪存理想的情況下，排序時(shí)間會(huì)隨著K的增加而呈式（12）下降．但實(shí)際的情況是，當(dāng)隨著K的增加，算法會(huì)達(dá)到訪存受限，之后執(zhí)行時(shí)間的下降空間有限．圖13顯示了DFMC結(jié)構(gòu)上排序時(shí)間與SIMD寬度的關(guān)系，當(dāng)前DFMC的SIMD寬度為2，由于存儲(chǔ)帶寬的限制，SIMD寬度的進(jìn)一步加大所帶來(lái)的性能提升有限．但是，如果存儲(chǔ)帶寬增加1倍，同時(shí)SIMD寬度增加1倍，將使得排序速度提升71%．

Fig．13 Sorting time for varying SIMD width．圖13 排序時(shí)間隨SIMD寬度關(guān)系

7 總 結(jié)

陣列眾核處理器是眾核處理器發(fā)展的重要方向，能夠提供很高的峰值性能，但如何利用其多級(jí)并行性（SPMD和SIMD）和SPM的結(jié)構(gòu)特點(diǎn)、充分發(fā)揮其峰值性能，對(duì)并行算法的設(shè)計(jì)提出了較高的要求．

本文通過(guò)分析陣列眾核處理器的結(jié)構(gòu)特點(diǎn)，設(shè)計(jì)了多種相應(yīng)的優(yōu)化策略，大幅度提高了陣列眾核結(jié)構(gòu)上的歸并排序算法性能，實(shí)驗(yàn)結(jié)果優(yōu)于其他眾核處理器上基于比較的排序算法．本文的優(yōu)化過(guò)程說(shuō)明了，并行算法的設(shè)計(jì)要和特定的處理器結(jié)構(gòu)緊密結(jié)合起來(lái)才能最大限度地發(fā)揮處理器的性能．本文所展示的陣列眾核結(jié)構(gòu)上歸并排序算法的優(yōu)化過(guò)程對(duì)于其他處理器上并行算法的設(shè)計(jì)和優(yōu)化也有很好的借鑒意義．

本文最后分析了陣列眾核結(jié)構(gòu)與代表數(shù)據(jù)密集型應(yīng)用的歸并排序算法的性能之間的關(guān)系，相信這些分析對(duì)陣列眾核結(jié)構(gòu)的研究是一個(gè)有益的參考．

［1］Zhong Cheng，Chen Guoliang．An optimal parallel sorting algorithm for multisets［J］．Journal of Computer Research and Development，2003，40（2）：336 341（in Chinese）（鐘誠(chéng)，陳國(guó)良．Multisets排序的最優(yōu)并行算法［J］．計(jì)算機(jī)研究與發(fā)展，2003，40（2）：336 341）

［2］Ramey C．Tile－gx100manycore processor：Acceleration interfaces and architecture［OL］．San Jose，CA：Tilera Corporation，2011［2014－10－25］．http：??www．hotchips．org? wp－content?uploads?hc＿archives?hc23?HC23．18．2－security? HC23．18．220－TILE－GX100－Ramey－Tilera－e．pdf

［3］Mitsuhisa S．Feasibility study on future HPC infrastructure［OL］．Tsukuba，Janpan：University of Tsukuba，2014［2014－10－25］．http：??www．ccs．tsukuba．a(chǎn)c．jp?files?exreview?FS－ccs－eval－2014．pdf

［4］Gwennup L．Adapteva：More flops，less watts［OL］．Mountain View，CA：The Linley Group，2011［2014－10－25］．http：??www．a(chǎn)dapteva．com?wp－content?uploads?2011? 06?adapteva＿mpr．pdf

［5］Dinechin B D，Ayrignac R，Beaucamps P E，et al．A clustered manycore processor architecture for embedded and accelerated applications［C］??Proc of the 17th IEEE Conf on High Performance Extreme Computing．Piscataway，NJ：IEEE，2013：1 6

［6］Fan D R，Yuan N，Zhang J C，et al．Godson－T：An efficient many－core architecture for parallel program executions［J］．Journal of Computer Science and Technology，2009，24（6）：1061 1073

［7］Zheng Fang，Zhang Kun，Wu Guiming，et al．Architecture techniques of many－core processor for energy－efficient in high performance computing［J］．Chinese Journal of Computers，2014，37（10）：2176 2186（in Chinese）（鄭方，張昆，鄔貴明，等．面向高性能計(jì)算的眾核處理器結(jié)構(gòu)級(jí)高能效技術(shù)［J］．計(jì)算機(jī)學(xué)報(bào)，2014，37（10）：2176 2186）

［8］Merrill D G，Grimshaw A S．Revisiting sorting for GPGPU stream architectures［C］??Proc of the 19th Int Conf on Parallel Architectures and Compilation Techniques．New York：ACM，2010：545 546

［9］Davidson A，Tarjan D，Garland M，et al．Efficient parallel merge sort for fixed and variable length keys［C］??Proc of Innovative Parallel Computing．Piscataway，NJ：IEEE，2012：1 9

［10］Satish N，Kim C，Chhugani J，et al．Fast sort on CPUs，GPUs and Intel MIC architectures［OL］．Santa Clara，CA：Intel Labs，2010［2014－10－25］．http：??www．intel．com? content?www?us?en?research?intel－labs－radix－sort－mic－report．html

［11］Tian X，Kamil R，Reiji S．Register level sort algorithm on multi－core SIMD processors［C］??Proc of the 3rd Workshop on Irregular Applications：Architecture and Algorithms．New York：ACM，2013：No 9

［12］Sengupta S，Harris M，Zhang Yao，et al．Scan primitives for GPU computing［C］??Proc of the 22nd ACM SIGGRAPH? EUROGRAPHICS Symp on Graphics hardware．Aire－la－Ville，Switzerland：Eurographics Association，2007：97 106

［13］Satish N，Harris M，Garland M．Designing efficient sorting algorithms for manycore GPUs，NVR－2008－001［R］．Santa Clara，CA：NVIDIA Corporation，2008

［14］Satish N，Harris M，Garland M．Designing efficient sorting algorithms for manycore GPUs［C］??Proc of the 23rd IEEE Int Symp on Parallel ＆Distributed Processing．Piscataway，NJ：IEEE，2009：1 10

［15］Batcher K E．Sorting networks and their applications［C］?? Proc of the Spring Joint Computer Conf．New York：ACM，1968：307 314

［16］Purcell T J，Donner C，Cammarano M，et al．Photon mapping on programmable graphics hardware［C］??Proc of the ACM SIGGRAPH?EUROGRAPHICS Conf on Graphics hardware．Aire－la－Ville，Switzerland：Eurographics Association，2003：41 50

［17］Peters H，Schulz－Hildebrandt O，Luttenberger N．Fast inplace，comparison－based sorting with CUDA：A study with bitonic sort［J］．Concurrency and Computation：Practice and Experience，2011，23（7）：681 693

［18］Greb A，Zachmann G．GPU－ABiSort：Optimal parallel sorting on stream architectures［C］??Proc of the 20th Int Conf on Parallel and Distributed Processing．Piscataway，NJ：IEEE，2006：45 54

［19］Cederman D，Tsigas P．A practical quicksort algorithm for graphics processors［G］??LNCS 5193：Proc of the 16th Annual European Symp on Algorithms．Berlin：Springer，2008：246 258

［20］Cederman D，Tsigas P．GPU－quicksort：A practical quicksort algorithm for graphics processors［J］．Journal of Experimental Algorithmics（JEA），2009，14（4）：1 22

［21］Leischner N，Osipov V，Sanders P．GPU sample sort［C］?? Proc of the 24th IEEE Int Symp on Parallel Distributed Processing．Piscataway，NJ：IEEE，2010：1 10

［22］Sintorn E，Assarsson U．Fast parallel GPU－sorting using a hybrid algorithm［J］．Journal of Parallel and Distributed Computing，2008，68（10）：1381 1388

［23］Ye X，F(xiàn)an D，Lin W，et al．High performance comparisonbased sorting algorithm on many－core GPUs［C］??Proc of the 24th IEEE Int Symp on Parallel Distributed Processing．Piscataway，NJ：IEEE，2010：1 10

［24］Banerjee D S，Sakurikar P，Kothapalli K．Fast，scalable parallel comparison sort on hybrid multicore architectures［C］??Proc of the 27th IEEE Int Symp on Parallel and Distributed Processing Workshops ＆PhD Forum．Piscataway，NJ：IEEE，2013：1060 1069

［25］Cormen T H，Leiserson C E，Rivest R L，et al．Introduction to Algorithms［M］．Cambridge，MA：MIT Press，2001

Shi Song，born in 1990．MSc．Member of China Computer Federation．His research interests include computer architecture，microprocessor design and high－performance computing．

Li Hongliang，born in 1975．PhD，associate professor．Member of China Computer Federation．His main research interests include computer architecture，microprocessor design and high－performance computing（hongliangli＠263．net）．

Zhu Wei，born in 1976．MSc，senior engineer．His main research interests include microprocessor design and integrated circuit verification（zw84611＠sina．com）．

Efficient Merge Sort Algorithms on Array－Based Manycore Architectures

Shi Song，Li Hongliang，and Zhu Wei
（Jiangnan Institute of Computing Technology，Wuxi，Jiangsu214083）

Sorting is one of the most fundamental problems in the field of computer science．With the rapid development of manycore processors，it shows great importance to design efficient sort algorithms on manycore architecture．An important trend of manycore processors is array－based manycore architecture．This paper presents two efficient merge sort algorithms on array－based manycore architectures．Our algorithms achieve high performance by using DMA（direct memory access）multi－buffering strategy to improve the memory accessing efficiency，deeply balanced merging strategy to keep load－balancing between cores，SIMD（single instruction multiple data）merging method to exploit fine－grained parallelism and on－chip swap merging strategy to reuse on－chip data．Experimental results on DFMC（deeply－fused many－core）prototype system achieve a sorting rate of 647MKeys?s（million keys per second），and the sorting efficiency（sorting rate?peak performance）is 3．3xhigher than state－of－the－art GPU merge sort on GTX580，and 2．7xhigher than the fastest merge sort on Intel Xeon Phi．Additionally，this paper establishes an analytical model to characterize the performance of our algorithms．Based on the analytical model，we analyze the influence of the main structural parameters to the performance of the algorithms，which will contribute to the study of many－core architecture．

array－based manycore；merge sort；sort network；SIMD；SPMD；on－chip communication

TP302

2014－11－14；

2015－07－21

國(guó)家“八六三”高技術(shù)研究發(fā)展計(jì)劃基金項(xiàng)目（2014AA01A301）；“核高基”國(guó)家科技重大專項(xiàng)基金項(xiàng)目（2013zx0102－8001－001－001）

This work was supported by the National High Technology Research and Development Program of China（863Program）（2014AA01A301）and the National Science and Technology Major Projects of Hegaoji（2013zx0102－8001－001－001）．

關(guān)鍵詞 陣列眾核；歸并排序；排序網(wǎng)絡(luò)；單指令多數(shù)據(jù)流；單程序多數(shù)據(jù)流；片上通信