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

石 嵩 李宏亮 朱 巍

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

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

石 嵩 李宏亮 朱 巍

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

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

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

近年來，眾核處理器在學術(shù)界和工業(yè)界得到了廣泛關(guān)注和蓬勃發(fā)展，已在多個領(lǐ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等屬于陣列眾核處理器，它們的共同特點是以陣列方式組織眾多計算核心，具有可擴展性好、實現(xiàn)代價低的優(yōu)點，是眾核處理器發(fā)展的重要方向．

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3．2 CPEB－MS算法

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

3．2．1 訪存管理——DMA多緩沖機制

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了運用SIMD歸并網(wǎng)絡，需要先將輸入序列排成長K有序的子序列．該過程可通過基于排序網(wǎng)絡和混洗操作的寄存器排序完成，如圖5所示，將K2個元素放置在K個寄存器中，首先用長度為K的奇偶歸并排序網(wǎng)絡將它們（如A［0，1，2，3］）排序成K個長K有序的序列（如a0，a1，a2，a3），如圖5（a）所示，然后通過Klb（K）次vshuffle操作將各有序序列混洗到單個寄存器中（圖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個數(shù)據(jù)均勻劃分給各CPE（C個CPA，每個CPA中P個CPE，共C×P個CPE），每個核心有N?（C×P）個數(shù)據(jù)；

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

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

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

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

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

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

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

3．3 CPAB－MS算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實驗結(jié)果與分析

4．1 實驗環(huán)境

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

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

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

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

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種歸并排序算法的排序速率

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

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

4．3 與其他平臺排序算法的比較

實驗選取了近幾年來眾核處理器上效率最高的幾種比較型排序算法進行對比．在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］進行比較，實驗數(shù)據(jù)均來源于公開發(fā)表的文獻．表2顯示了這些處理器的性能參數(shù)．

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

實驗結(jié)果如圖9所示，可以看出，在所有這些比較型排序中，DFMC上的實驗結(jié)果是最好的，如數(shù)據(jù)量為16×220時，DFMC Merge的排序速度達到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 不同平臺排序算法性能比較

5 算法性能模型

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

5．1 模型建立

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

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

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

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

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

5．2 性能模型誤差

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

Fig．10 Comparison between estimated values and experimental values．圖10 實驗值與理論值比較

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

6 進一步討論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6．2 片上存儲大小

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

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

6．3 SIMD寬度

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

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

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

7 總 結(jié)

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

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

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

［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）（鐘誠，陳國良．Multisets排序的最優(yōu)并行算法［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）（鄭方，張昆，鄔貴明，等．面向高性能計算的眾核處理器結(jié)構(gòu)級高能效技術(shù)［J］．計算機學報，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

國家“八六三”高技術(shù)研究發(fā)展計劃基金項目（2014AA01A301）；“核高基”國家科技重大專項基金項目（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)絡；單指令多數(shù)據(jù)流；單程序多數(shù)據(jù)流；片上通信