基于FPGA 的排序加速方法綜述

孔 浩 盧文巖 陳 巖 鄢貴海 李曉維

1 （處理器芯片全國重點(diǎn)實(shí)驗(yàn)室（中國科學(xué)院計(jì)算技術(shù)研究所） 北京 100190）

2 （中國科學(xué)院大學(xué) 北京 100049）

3 （中科馭數(shù)（北京）科技有限公司 北京 100094）

排序作為最基礎(chǔ)同時(shí)又應(yīng)用最廣泛的操作之一，其高性能設(shè)計(jì)一直是眾多研究工作追求的目標(biāo).排序在人工智能、數(shù)據(jù)挖掘和分布式數(shù)據(jù)庫等數(shù)據(jù)驅(qū)動型應(yīng)用中發(fā)揮著至關(guān)重要的作用，如分布式框架Spark 的瓶頸操作混洗（shuffle），在其讀過程中需要將從不同結(jié)點(diǎn)拉取到的數(shù)據(jù)在聚合后進(jìn)行排序；數(shù)據(jù)庫中最為常見的操作之一是基于排序的連接（sortmerge join），其也需要數(shù)據(jù)先經(jīng)過排序階段.盡管CPU 單核性能在不斷提升，多核、眾核等新型架構(gòu)也在持續(xù)演進(jìn)優(yōu)化，但在爆炸式增長的數(shù)據(jù)規(guī)模下，與排序相關(guān)的計(jì)算開銷和訪存要求也愈加顯著，使得排序很容易成為瓶頸操作，因此對于排序的加速也越發(fā)重要，而現(xiàn)場可編程門陣列（field programmable gate array，F(xiàn)PGA）憑借其可重配置、高并行等特性能很好地彌補(bǔ)這一缺陷.

基于FPGA 的排序加速已經(jīng)得到了廣泛地研究與應(yīng)用，表1 列舉了近年來的代表性工作，從中可以看出FPGA 排序加速的多種發(fā)展趨勢，主要體現(xiàn)在以下方面：多種排序算法已有相應(yīng)的加速方案，如歸并排序[6-9,11,13,17,24,26]、 線性排序[2]、 基于地址的排序[3]等.排序數(shù)據(jù)規(guī)模逐漸增大，從最初的MB 量級發(fā)展到如今的TB 量級的外部排序.靈活支持多種數(shù)據(jù)類型，數(shù)據(jù)寬度不局限于32 b 或64 b 的常規(guī)數(shù)據(jù)類型位寬，如Bonsai[23]可支持至多512 b 的數(shù)據(jù)位寬，對于超出硬件數(shù)據(jù)位寬的情況，可采用軟件編碼（如哈希）的方法進(jìn)行解決.除全卸載外，軟硬件協(xié)同配合的半卸載使得主機(jī)端不再只扮演數(shù)據(jù)生成和收集的角色，而是和硬件加速器協(xié)同配合實(shí)現(xiàn)整體性能加速.基于新硬件的排序加速也在逐漸涌現(xiàn)，引入了各種新型存儲和接口，如HBM[23]，SmartSSD[26,28]等.

Table 1 Schemes of Sort Acceleration Using FPGAs表1 基于FPGA 的排序加速方案

目前大多數(shù)排序加速方案均集中在歸并算法領(lǐng)域，少部分涉及插入排序[4]、基數(shù)排序[29]、采樣排序[25]等其他排序工作.原因主要在于歸并算法自身“分治”和“空間換時(shí)間”的設(shè)計(jì)思想，適合在FPGA 上并行實(shí)現(xiàn)，其控制邏輯相比起其他非歸并類算法也更加簡單.在基于比較的排序當(dāng)中，歸并排序的時(shí)間復(fù)雜度趨近最優(yōu)值，同時(shí)可預(yù)測的、連續(xù)的訪存模式使其非常適合突發(fā)傳輸和存儲空間合并等.對于歸并類排序加速設(shè)計(jì)，從架構(gòu)上來說，主要分為排序網(wǎng)絡(luò)（sorting network, SN）、基于FIFO 的歸并排序（FIFO merge sort, FMS） 和歸并樹（merge tree, MT） 3 類[4]，大多數(shù)研究工作也都是基于這3 種架構(gòu)進(jìn)行優(yōu)化設(shè)計(jì).

在基于FPGA 進(jìn)行排序加速時(shí)離不開各種性能評估指標(biāo)，包括延時(shí)、吞吐率、功耗、硬件利用率和帶寬利用率等.基于FPGA 的排序加速關(guān)注的核心問題是如何延時(shí)更快、功耗更低、成本更少地排序1 組或多組任意長度、隨機(jī)分布、不定類型的數(shù)據(jù).兼顧實(shí)現(xiàn)所有目標(biāo)維度的提升是很難的，延時(shí)通常是主要的關(guān)注目標(biāo)，其他次要目標(biāo)多在不過度損害主要目標(biāo)的前提下進(jìn)行優(yōu)化.為解決該核心問題，本文后續(xù)部分將建立一項(xiàng)通用最優(yōu)化模型，并在此基礎(chǔ)上對一系列研究工作展開分析.

基于FPGA 的排序加速是一個(gè)在算法選擇、優(yōu)化設(shè)計(jì)和測試之間不斷權(quán)衡迭代的過程，如圖1 所示.設(shè)計(jì)排序加速首先需要針對問題場景明確選擇何種算法；在設(shè)計(jì)硬件加速架構(gòu)時(shí)需要考慮帶寬、硬件資源等限制條件以及延時(shí)、吞吐率等優(yōu)化目標(biāo)；在加速架構(gòu)完成之后，需要一個(gè)合適的測試基準(zhǔn)來準(zhǔn)確合理地評測性能.若未達(dá)到預(yù)期，則需要重新審視算法選擇和架構(gòu)設(shè)計(jì).本文分析歸納了各過程中所面臨的問題以及相應(yīng)優(yōu)化措施，對于設(shè)計(jì)人員來說，將能極大程度地加速這一迭代過程.

圖1 FPGA 排序加速設(shè)計(jì)流程Fig.1 Design process of FPGA sort acceleration

排序在實(shí)際應(yīng)用時(shí)會面臨新的問題與挑戰(zhàn)，需要針對性地進(jìn)行架構(gòu)的調(diào)整.在數(shù)據(jù)庫中，排序不僅是關(guān)鍵獨(dú)立操作，也用于實(shí)現(xiàn)基于排序的連接、分組（group-by）等其他操作[30]，因此本文以數(shù)據(jù)庫加速為應(yīng)用案例，探討應(yīng)用驅(qū)動下的排序加速設(shè)計(jì).對于數(shù)據(jù)庫中的排序來說[31-33]，如何在應(yīng)對與其他操作間的資源競爭的同時(shí)實(shí)現(xiàn)高效配合，如何合理地利用行式存儲與列式存儲的不同特性實(shí)現(xiàn)性能的最大化，如何處理數(shù)據(jù)庫中排序衍生而來的最大、最小和Top-K操作，以及如何處理數(shù)據(jù)庫中用戶請求多樣性等問題，均是數(shù)據(jù)庫排序加速所必須面臨的挑戰(zhàn).針對上述問題，本文分析了現(xiàn)有研究方案的解決措施，目前對于數(shù)據(jù)庫排序加速來說仍存在許多問題亟待解決.

現(xiàn)有綜述類工作缺少對基于FPGA 的排序加速設(shè)計(jì)的系統(tǒng)分析研究.郭誠欣等人[34]的工作總結(jié)了包括CPU，GPU，F(xiàn)PGA 等新型硬件上的并行內(nèi)存排序研究成果，其重點(diǎn)在于CPU 和GPU 上相關(guān)工作的比較分析，而對于FPGA 相關(guān)的排序加速方法僅簡要列舉了插入排序[35]、比較矩陣[36]、桶排序[37]、排序網(wǎng)絡(luò)[7-8]等工作.除此之外，排序作為數(shù)據(jù)庫中的關(guān)鍵操作，相關(guān)加速工作也出現(xiàn)在數(shù)據(jù)庫硬件加速領(lǐng)域.Fang 等人[38]主要關(guān)注SN，F(xiàn)MS，MT 這3 種歸并類加速的研究工作，歸納介紹了各種架構(gòu)的特點(diǎn)和瓶頸.Papaphilippou 等人[39]指出與CPU 上廣泛應(yīng)用的快排不同，F(xiàn)PGA 上的加速算法更多地集中在桶排序和歸并排序等算法領(lǐng)域，與CPU 相比性能和功耗等方面更具優(yōu)勢.

本文所做的主要貢獻(xiàn)有4 個(gè)方面：

1) 整理歸納了現(xiàn)有基于FPGA 排序加速的代表性系統(tǒng)和研究（如表1 所示），并從中梳理出性能驅(qū)動下的排序加速設(shè)計(jì)發(fā)展趨勢，主要體現(xiàn)在排序算法多樣化、排序數(shù)據(jù)規(guī)模不斷增大、數(shù)據(jù)類型更加多樣、軟硬件協(xié)同設(shè)計(jì)以及基于新型硬件設(shè)計(jì)等方面；

2) 分析了FPGA 排序加速在設(shè)計(jì)、實(shí)現(xiàn)、測評等各不同階段所面臨的問題與挑戰(zhàn)，在排序算法選擇、最優(yōu)化模型建立以及評測基準(zhǔn)的配置等方面，為如何基于FPGA 進(jìn)行排序加速設(shè)計(jì)提供指導(dǎo)和幫助；

3) 以數(shù)據(jù)庫為分析案例，闡明了排序加速在實(shí)際應(yīng)用場景中所面臨的資源競爭、數(shù)據(jù)組織方式、特有操作與用戶請求多樣性等挑戰(zhàn)與相應(yīng)架構(gòu)調(diào)整，為其他領(lǐng)域的應(yīng)用提供了借鑒；

4) 總結(jié)歸納了現(xiàn)有研究的主要問題及缺陷，現(xiàn)有排序加速普遍存在帶寬利用率低、衛(wèi)星數(shù)據(jù)處理方式不完善、資源及功耗較高等問題，并基于此提出了未來的發(fā)展方向，包括對于超大數(shù)據(jù)規(guī)模的分布式排序加速，引入數(shù)據(jù)處理器（data processing unit,DPU）等新型硬件設(shè)備進(jìn)行排序加速，以及高層次綜合等輔助工具鏈的完善對于排序加速設(shè)計(jì)迭代更新的推動作用.

1 FPGA 排序加速設(shè)計(jì)原則

1.1 排序加速算法選擇

影響排序算法選擇的因素整體上可分為內(nèi)部因素和外部因素2 類.內(nèi)部因素即排序算法自身的理論性能表現(xiàn)和資源需求；外部因素與具體應(yīng)用場景相關(guān)，不同應(yīng)用場景下的待排序數(shù)據(jù)具備不同的性質(zhì)，包括數(shù)據(jù)自身特征和傳輸方式，其中數(shù)據(jù)特征又可以進(jìn)一步分為數(shù)據(jù)規(guī)模、數(shù)據(jù)寬度和數(shù)據(jù)分布.

分析內(nèi)部因素時(shí)，可以從排序算法的時(shí)間復(fù)雜度和空間復(fù)雜度入手.時(shí)間復(fù)雜度是不同算法自身理論性能橫向比較的依據(jù)，在軟件算法層面直接反映了不同算法所需要的比較交換次數(shù).盡管不同算法可能在時(shí)間復(fù)雜度上相差不大，但是否適合在硬件上并行實(shí)現(xiàn)，將在很大程度上影響性能，如歸并排序和快排的時(shí)間復(fù)雜度均為O(nlbn)，但是歸并排序基于排序架構(gòu)實(shí)現(xiàn)時(shí)共有l(wèi)bn×(lbn+1)/2 個(gè)階段，同一階段間的n/2 個(gè)比較交換模塊可以并行工作，而快排數(shù)據(jù)間相關(guān)性較大，不利于并行流水化實(shí)現(xiàn)，因而硬件性能要差于歸并排序.空間復(fù)雜度僅能在一定程度上反映所需額外存儲空間，具體的存儲資源需求還受到具體實(shí)現(xiàn)架構(gòu)的影響.對于同一種算法，采用不同架構(gòu)所受到的資源限制也不同，如歸并排序選用排序網(wǎng)絡(luò)架構(gòu)實(shí)現(xiàn)時(shí)，會受到比較器資源需求的限制，如Virtex 5 系列至多能支持一個(gè)64輸入、數(shù)據(jù)寬度為32 b 的排序網(wǎng)絡(luò)SN 算法[5]；而選用基于FIFO 的歸并排序時(shí)，更多地受到存儲資源的限制[1].外部因素對于算法選擇的影響分成4 個(gè)方面.

1)數(shù)據(jù)規(guī)模.依據(jù)待排序序列長度是否可變，數(shù)據(jù)排序可分為動態(tài)數(shù)據(jù)規(guī)模排序和靜態(tài)數(shù)據(jù)規(guī)模排序.與軟件實(shí)現(xiàn)不同的是，許多硬件排序架構(gòu)受輸入端口數(shù)目限制并不支持動態(tài)數(shù)據(jù)規(guī)模，如排序網(wǎng)絡(luò)等并行排序器[12]；而歸并樹等串行排序器以流式數(shù)據(jù)的形式處理數(shù)據(jù)，如基于歸并樹的數(shù)據(jù)長度可適應(yīng)的架構(gòu)Bonsai 可以支持4 GB 至100 TB 等不同數(shù)據(jù)規(guī)模下的排序[23].另一方面，對于某些架構(gòu)如排序網(wǎng)絡(luò)來說，其輸入端口的數(shù)目與數(shù)據(jù)長度呈正相關(guān)，而輸入端口進(jìn)一步影響到整體的資源需求量，因此不能用于大規(guī)模數(shù)據(jù)排序.

2)數(shù)據(jù)分布.包括指數(shù)、泊松、帕累托和齊夫分布等多種數(shù)據(jù)分布[12].由于數(shù)據(jù)偏斜會引發(fā)排序阻塞和穩(wěn)定性問題，因此基排序一般用于數(shù)據(jù)取值范圍已知的情況[29,40]，否則當(dāng)數(shù)據(jù)偏斜過于嚴(yán)重時(shí)，基排序會退化成快速排序.在目前的研究工作中，尚未有歸并排序因排序阻塞而受損的情況，主要是由于在數(shù)據(jù)的逐漸歸并中，數(shù)據(jù)分布被重新調(diào)整，已與初始數(shù)據(jù)分布不一致.

3)數(shù)據(jù)寬度.數(shù)據(jù)寬度一方面與數(shù)據(jù)類型相關(guān)，另一方面排序數(shù)據(jù)一般分為“鍵”和“值”2 部分，當(dāng)“值”部分寬度過大無法與“鍵”一起搬運(yùn)時(shí)，會引發(fā)衛(wèi)星數(shù)據(jù)（satellite data）的處理問題，但一般不影響排序算法的選擇.

4)數(shù)據(jù)傳輸方式.包括流式數(shù)據(jù)傳輸和批式數(shù)據(jù)傳輸.為節(jié)省流式數(shù)據(jù)傳輸時(shí)間，一旦數(shù)據(jù)抵達(dá)即需開始排序，而非等待全部數(shù)據(jù)準(zhǔn)備完成，一般可采用錦標(biāo)賽排序[41]、 插入排序的變體[22]或者基于梳排序的變體[42].

綜合考慮上述4 個(gè)因素之后，圖2 展示了在各類因素限制下的1 種或多種表現(xiàn)較好的可行算法選擇，其中歸并排序?qū)Υ蠖嘁蛩鼐哂辛己玫倪m應(yīng)性.

圖2 排序算法選擇Fig.2 Selection of sort algorithms

1.2 排序加速優(yōu)化設(shè)計(jì)

排序算法的主要優(yōu)化目標(biāo)集中在延時(shí)、吞吐率、帶寬利用率和硬件資源占用率等方面.本節(jié)將關(guān)注各優(yōu)化目標(biāo)的基本定義并分析其優(yōu)化手段，并最終建立排序最優(yōu)化模型，本節(jié)所使用的參數(shù)如表2 所示.需要注意的是，本節(jié)所進(jìn)行的優(yōu)化設(shè)計(jì)適用于任何數(shù)據(jù)通路.具體來說，大多數(shù)FPGA 排序加速工作的數(shù)據(jù)通路形式為PCIe 加速板卡，如圖3（a）所示；少數(shù)工作以協(xié)處理器的形式出現(xiàn)[43]，如圖3（b）所示，如英特爾的Xeon+FPGA 或者ZYNQ 平臺，通過QPI總線將CPU 和FPGA 封裝在一起從而共享內(nèi)存；除此之外，近存計(jì)算如SmartSSD[26]縮短了FPGA 與大容量存儲SSD 之間的距離，如圖3（c）所示.

圖3 FPGA 排序加速的3 種數(shù)據(jù)通路Fig.3 Three data paths of sort acceleration on FPGA

Table 2 Parameter List表2 參數(shù)列表

1)延時(shí).排序加速整體可以劃分為建立階段和穩(wěn)定階段，彼此相互獨(dú)立，其中建立階段包括初始數(shù)據(jù)傳輸和多次迭代間數(shù)據(jù)的存取耗時(shí)等，穩(wěn)定階段即產(chǎn)生有效輸出的階段.Usui 等人[14]將產(chǎn)生有效輸出的時(shí)間與總處理時(shí)間的比值定義為有效率，用以反映穩(wěn)定階段占比.對于延時(shí)的優(yōu)化可以從建立階段和穩(wěn)定階段2 方面入手，二者均與吞吐率和存儲帶寬有密不可分的關(guān)系，具體如式（1）所示，其中i=0，1，…，L，i=0 時(shí)表示建立階段.對于延時(shí)的優(yōu)化，主要體現(xiàn)在減少迭代次數(shù)（如設(shè)置多組排序加速器并行執(zhí)行），提升帶寬，以及增大每輪次迭代時(shí)的吞吐率上.

2)吞吐率.吞吐率可分為平均吞吐率和瞬時(shí)吞吐率，前者即總數(shù)據(jù)量除以總延時(shí)，后者與穩(wěn)定階段每個(gè)時(shí)鐘周期輸出的數(shù)目相關(guān).大部分工作主要關(guān)注瞬時(shí)吞吐率，但存在未將二者加以區(qū)分而混用的情況.具體來說，瞬時(shí)吞吐率Throughput除受帶寬限制外，主要取決于穩(wěn)定階段每個(gè)時(shí)鐘周期輸出的數(shù)據(jù)總位寬（含衛(wèi)星數(shù)據(jù)）和工作頻率，即

因此，吞吐率的提升一方面可以通過增大穩(wěn)定階段每個(gè)時(shí)鐘周期的數(shù)據(jù)輸出數(shù)目，如歸并樹中以雙調(diào)部分歸并模塊替代比較選取模塊，如圖4 所示，圖4（b）中虛線比較選取模塊為忽略部分；另一方面，可以通過采取流水化的方法來縮短關(guān)鍵路徑以提高工作頻率，但需要注意數(shù)據(jù)之間的相關(guān)性所引起的流水線阻塞.

圖4 歸并排序常用比較器模塊Fig.4 Common comparator unit of merge sort

3)帶寬利用率.帶寬利用率為吞吐率與存儲帶寬的比值，如式（3）所示.帶寬利用率與具體存儲設(shè)備相關(guān)，不同存儲設(shè)備的帶寬利用率會存在差異.FPGA 排序加速通常會涉及多種不同的存儲設(shè)備，如BRAM、DRAM、SSD 和磁盤等，盡管在不同的迭代輪次所遇到的存儲設(shè)備不同，目前的研究工作中在進(jìn)行評估時(shí)多選用穩(wěn)定階段吞吐率與主要瓶頸存儲帶寬（如DRAM）的比值，由此得到的現(xiàn)有硬件加速引擎的帶寬利用率如圖5 所示，各種加速方案的帶寬利用率均低于30%，并且排序帶寬利用率在CPU[44]和GPU[45]上也處于一個(gè)較低的水平.

圖5 不同F(xiàn)PGA 排序加速方案的帶寬利用率Fig.5 Bandwidth-efficiency of different sort acceleration schemes on FPGA

排序作為存儲密集型的應(yīng)用，帶寬的合理利用問題是至關(guān)重要的，帶寬利用率的提升措施主要包括已有帶寬的合理利用和借助新型存儲設(shè)備和硬件接口及總線標(biāo)準(zhǔn)提高帶寬上限.帶寬的合理利用主要體現(xiàn)為盡可能地減少低層次存儲設(shè)備的存取，一方面需要盡可能地減少中間結(jié)果的數(shù)量，以防止溢出至低層次存儲設(shè)備；另一方面，不同層次間的存儲設(shè)備交互時(shí)會面臨帶寬不匹配問題，可以通過設(shè)置FIFO 來緩存數(shù)據(jù)并掩蓋延遲，即在排序的同時(shí)進(jìn)行數(shù)據(jù)的預(yù)取.對于帶寬上限提升方面，新型存儲設(shè)備可以極大程度地提升帶寬上限，如HBM 可以替代板上存儲DRAM，SmartSSD 將SSD 和FPGA 集成在一起，大數(shù)據(jù)規(guī)模下無需經(jīng)由CPU 訪問磁盤；硬件接口及總線標(biāo)準(zhǔn)如QPI，CXL，OpenCAPI[46]等也使得數(shù)據(jù)的訪問方式更加靈活、訪存帶寬得以提升，Intel Xeon+FPGA 平臺和ZYNQ 將CPU 和FPGA 通過QPI總線集成到一起，F(xiàn)PGA 可以直接訪問CPU 的內(nèi)存，而不需要進(jìn)行額外的數(shù)據(jù)搬運(yùn).

4)硬件資源占用率.硬件資源占用率指的是排序加速架構(gòu)所占用的各類硬件資源與整體的比率，主要包括LUT（或者Slice）、BRAM、DSP 和Flip Flop等，其中對排序加速影響最大的是LUT 和BRAM 占用率.BRAM 與排序架構(gòu)中各類緩存相關(guān)，一方面起到緩解不同存儲設(shè)備間帶寬差距的作用，在排序的同時(shí)傳輸數(shù)據(jù)，以此來掩蓋數(shù)據(jù)傳輸延時(shí)；另一方面能夠改善數(shù)據(jù)異常分布所造成的阻塞情況.LUT 決定了所能支持的比較器數(shù)目上限，進(jìn)而影響排序架構(gòu)規(guī)模.除LUT 之外，部分板卡所集成的DSP 模塊可以通過使用減法來代替比較操作，在一定程度上增加了所能支持的比較器數(shù)目.如圖6 所示，不同排序架構(gòu)對硬件資源的需求不同，SN 的硬件資源主要消耗在Slice 上，用以構(gòu)成比較交換模塊，而BRAM 資源占用較少；FMS 對于Slice 和BRAM 的需求量均很大；MT 對于Slice 和BRAM 占用適中，以最新研究Bonsai[23]為例，其LUT 占用率僅為33.3%，BRAM 最高的占用率為60%.

圖6 不同F(xiàn)PGA 排序加速方案的硬件資源占用率Fig.6 Resource utilization of different sort acceleration schemes on FPGA

硬件資源占用率低一方面說明空閑資源可以用來實(shí)現(xiàn)其他類型的操作加速，如數(shù)據(jù)庫中的連接、聚合等操作，也可以實(shí)現(xiàn)查找、數(shù)據(jù)劃分等輔助操作[47]，用以配合排序的進(jìn)一步加速.另一方面，硬件資源占用率低并不意味著硬件資源的有效利用率高.對于硬件資源有效利用率低的排序架構(gòu)，許多比較模塊不能同時(shí)處于有效工作狀態(tài)，這也為模塊復(fù)用留下了優(yōu)化空間，如Usui 等人[14]通過模塊復(fù)用將Slice 資源占用率降至了1.72%.

通過上述分析，我們可以得到在硬件資源約束下的排序最優(yōu)化模型，如式（4）所示.由于硬件占用率受不同架構(gòu)影響，缺乏統(tǒng)一的分析模型，此處不進(jìn)行深入展開.

該模型有助于研究人員統(tǒng)一不同工作間的研究動機(jī)和發(fā)展路徑，并且該模型也能起到實(shí)際設(shè)計(jì)空間探索指導(dǎo)作用，當(dāng)然在實(shí)際應(yīng)用中需要進(jìn)一步細(xì)化.下面，我們將以歸并樹加速設(shè)計(jì)為例，詳細(xì)介紹該模型的應(yīng)用.

在歸并樹設(shè)計(jì)中，需要明確的是歸并樹的輸入葉節(jié)點(diǎn)數(shù)目q和每個(gè)時(shí)鐘周期的輸出數(shù)目p，以及歸并樹并行擴(kuò)展數(shù)目m.假定數(shù)據(jù)規(guī)模N小于板上DRAM 容量CDRAM，每個(gè)歸并樹占用的LUT 資源為FLUT(p,q)，迭代次數(shù)L=logq(N/m)，同時(shí)為緩解帶寬不匹配問題，每一輸入葉節(jié)點(diǎn)一般配備容量為r的FIFO，由此依據(jù)式（1），我們可以得到延時(shí)的優(yōu)化模型為

約束條件為

當(dāng)部署在AWS EC2 平臺上時(shí)，BWDRAM=32 GBps，BRAM 大小為1 600 KB，LUT 總數(shù)目為862 128，運(yùn)行頻率為250 MHz，測試數(shù)據(jù)位寬b=32 b，通過該模型我們可以得到歸并樹的最優(yōu)化配置為q=256，p=32，m=1，此時(shí)與DRAM 的峰值帶寬是相匹配的.

1.3 排序加速性能測試

現(xiàn)有研究在驗(yàn)證排序架構(gòu)性能時(shí)，多采用隨機(jī)生成輸入數(shù)據(jù)的方法.對于此類方法來說，由于不同特征的測試數(shù)據(jù)對于排序性能存在影響，因此需要針對應(yīng)用場景明確數(shù)據(jù)特征，包括長度、數(shù)據(jù)類型和數(shù)據(jù)分布情況等.部分排序架構(gòu)對于輸入數(shù)據(jù)長度存在必須為2 的冪次的要求，對此一般需要補(bǔ)充特殊數(shù)據(jù)或者數(shù)據(jù)分割至長度為最接近的2 的冪次，在最終的排序結(jié)果中再將特殊數(shù)據(jù)進(jìn)行過濾或者分割結(jié)果合并，這一過程需要包含在排序的整體延時(shí)當(dāng)中.數(shù)據(jù)類型主要包括整型、浮點(diǎn)型和字符串類型，其中對于整型數(shù)據(jù)，多采用32 b 或64 b 數(shù)據(jù)位寬；對于浮點(diǎn)類型數(shù)據(jù)，一方面可以通過定點(diǎn)化處理，另一方面需要針對IEEE-754 標(biāo)準(zhǔn)進(jìn)行設(shè)計(jì)，后者將影響低功耗設(shè)計(jì)目標(biāo)；字符串類型的排序包括按照字符串長度進(jìn)行排序和按照字符字典序進(jìn)行排序，需要分別設(shè)計(jì)不同的加速架構(gòu)進(jìn)行處理.

使用獨(dú)立排序基準(zhǔn)[48]或者系統(tǒng)基準(zhǔn)程序如TPCH[49]也是一種測試排序加速性能的途徑.獨(dú)立排序基準(zhǔn)中的測試程序包括格雷排序（GraySort）（用以評估排序至少100 TB 數(shù)據(jù)時(shí)的吞吐率）、焦耳排序（JouleSort）（用以評估功耗）和數(shù)據(jù)化排序（datamation sort）（用以評估100 MB 數(shù)據(jù)延時(shí)）等.在使用時(shí)可以針對獨(dú)立排序基準(zhǔn)進(jìn)行相應(yīng)修改以適配自身架構(gòu)，如Bonsai 在實(shí)際測試時(shí)將數(shù)據(jù)進(jìn)行了哈希以減小數(shù)據(jù)位寬[23].TPC-H 提供了針對數(shù)據(jù)庫領(lǐng)域的相應(yīng)測試基準(zhǔn)，除了待排序的關(guān)鍵列數(shù)據(jù)之外，其他非關(guān)鍵列數(shù)據(jù)作為衛(wèi)星數(shù)據(jù)所引起的數(shù)據(jù)位寬問題和數(shù)據(jù)搬運(yùn)問題都需要妥善地處理，可以清晰地反映出在實(shí)際應(yīng)用場景中的排序性能.

2 FPGA 排序加速分析

FPGA 排序加速目前主要集中在歸并排序領(lǐng)域，非歸并類排序盡管在特定應(yīng)用場景下會有其獨(dú)特優(yōu)勢，但是對于應(yīng)用場景較為挑剔，相比于歸并排序而言，目前暫未系統(tǒng)性地深入研究.因此本節(jié)將主要關(guān)注于歸并排序，其代表性排序架構(gòu)設(shè)計(jì)包括排序網(wǎng)絡(luò)、基于FIFO 的排序和歸并樹3 類.通過對3 類不同排序架構(gòu)的分析，可以揭示出排序設(shè)計(jì)原則在各研究工作中的應(yīng)用.同時(shí)在2.4 節(jié)介紹了代表性的非歸并類加速工作，強(qiáng)調(diào)了其設(shè)計(jì)特點(diǎn)和應(yīng)用場景.

2.1 排序網(wǎng)絡(luò)設(shè)計(jì)分析

排序網(wǎng)絡(luò)的優(yōu)勢在于其結(jié)構(gòu)規(guī)整，具備高并行且控制邏輯簡單的優(yōu)勢，常用的高效排序網(wǎng)絡(luò)包括雙調(diào)排序和奇偶排序，如圖7 所示.排序網(wǎng)絡(luò)內(nèi)部的比較交換模塊按固定的階段順序連接，同階段內(nèi)的比較單元可以并行運(yùn)行，不同階段間可以添加寄存器進(jìn)行流水化，適合硬件實(shí)現(xiàn).對于輸入端口為N的排序網(wǎng)絡(luò)，數(shù)據(jù)長度小于N時(shí)可以通過特殊數(shù)據(jù)補(bǔ)齊，或者進(jìn)行相應(yīng)架構(gòu)調(diào)整，如圖7（c）所示.

圖7 排序網(wǎng)絡(luò)Fig.7 Sorting network

在實(shí)際應(yīng)用中大多選用雙調(diào)排序網(wǎng)絡(luò)，雙調(diào)半排序規(guī)整的結(jié)構(gòu)路徑使得其具備進(jìn)一步演進(jìn)優(yōu)化的潛力.雖然奇偶排序網(wǎng)絡(luò)占用比較器數(shù)目比雙調(diào)排序網(wǎng)絡(luò)少,但奇偶排序不同數(shù)據(jù)通路之間的路徑延遲不均衡，需要額外添加寄存器來保證所有數(shù)據(jù)到達(dá)輸出端時(shí)的時(shí)序一致.

針對排序網(wǎng)絡(luò)的優(yōu)化主要在于如何降低硬件資源占用率.由圖6 可以看出，排序網(wǎng)絡(luò)的硬件資源占用率主要集中在LUT 上，且與輸入端口數(shù)目正相關(guān)，因此排序網(wǎng)絡(luò)更多地被用于小數(shù)據(jù)規(guī)模的排序.為降低硬件資源占用率可以采用可重配置的方法復(fù)用單一階段以完整模擬整個(gè)雙調(diào)排序過程.

Layer 等人[50]利用雙調(diào)排序模塊化、階段化的設(shè)計(jì)結(jié)構(gòu)，提出了一種可重配置的設(shè)計(jì)方案，所有階段共同復(fù)用同一個(gè)架構(gòu)，將N輸入的雙調(diào)排序網(wǎng)絡(luò)所需硬件資源降至O(N)，如圖8（a）所示.通過將比較交換模塊替換為帶有控制信號的交換比較器，可以依據(jù)階段不同而控制交換比較器是否進(jìn)行排序動作，同時(shí)交換比較器與輸入寄存器之間存在一個(gè)反饋環(huán)路.該設(shè)計(jì)控制邏輯復(fù)雜度提高，需要人為事先配置好各階段控制信號；可擴(kuò)展性差，排序長度只能為N/k，k= 1, 2, 4, …,N/2.

圖8 排序網(wǎng)絡(luò)優(yōu)化方案Fig.8 Optimizations of sorting network

Sklyarov 等人[7]提出了一種奇偶轉(zhuǎn)換網(wǎng)絡(luò)（evenodd transition network），如圖8（b）所示，用于進(jìn)一步減少排序網(wǎng)絡(luò)比較器資源的需求量，同時(shí)不需要復(fù)雜的控制邏輯.該結(jié)構(gòu)可以在2 級比較交換模塊之間添加寄存器以流水化，進(jìn)一步提升運(yùn)行頻率.為優(yōu)化單一數(shù)據(jù)組輸入出現(xiàn)的流水線空拍，可以將多組彼此間沒有數(shù)據(jù)依賴的數(shù)據(jù)依次輸入，提升多組數(shù)據(jù)的整體吞吐率.每次迭代數(shù)據(jù)至多向上或向下移動2 個(gè)位置，因此最壞情況下需要N/2 次迭代才能完成全部數(shù)據(jù)的排序.為減少迭代次數(shù)，保證當(dāng)序列滿足單調(diào)性要求時(shí)提前結(jié)束，該架構(gòu)一方面額外設(shè)計(jì)了一組比較器用于判斷處于序列兩端的數(shù)據(jù)是否滿足要求，另一方面通過判斷第2 級比較交換模塊是否有數(shù)據(jù)交換，從而將輸入寄存器組的使能信號設(shè)置為有效或無效狀態(tài).

雙調(diào)排序網(wǎng)絡(luò)經(jīng)過架構(gòu)調(diào)整可以用于最大集排序和雙調(diào)半排序，如圖9 所示.最大集排序用于選出序列中最大的K個(gè)數(shù)據(jù)，而不關(guān)心K個(gè)數(shù)據(jù)彼此間的順序，最大集排序可以通過調(diào)整雙調(diào)排序網(wǎng)絡(luò)中最后一個(gè)階段來完成[51].雙調(diào)部分歸并（bitonic partial merger, BPM）如圖9（b）所示，模塊內(nèi)部不同過程間也需要相應(yīng)進(jìn)行流水以減小關(guān)鍵路徑長度進(jìn)而提升工作頻率.以P輸入的BPM 為例，其可以分為lb （P）個(gè)流水階段，但是在實(shí)際應(yīng)用過程中數(shù)據(jù)之間的依賴關(guān)系會導(dǎo)致lb （P）-1 個(gè)空閑周期，并不能實(shí)現(xiàn)每一個(gè)時(shí)鐘周期都釋放有效數(shù)據(jù).因此，一種可行的優(yōu)化措施是同時(shí)排序多個(gè)序列，序列數(shù)據(jù)之間彼此不相關(guān)，以填充流水線中的“氣泡”時(shí)段.

圖9 雙調(diào)排序衍生架構(gòu)Fig.9 Derivative architecture of bitonic sorting

在雙調(diào)半排序的基礎(chǔ)之上，歸并排序加速方案可以通過提升每個(gè)時(shí)鐘周期的輸出數(shù)目來提升吞吐率.Casper 等人[30]在進(jìn)行數(shù)據(jù)庫操作硬件加速時(shí)提出了一種含有反饋路徑的排序架構(gòu).該架構(gòu)如圖10（a）所示，包含2 組輸入FIFO、選取邏輯（比較器、多路選擇器）和歸并邏輯（反饋寄存器、歸并單元（雙調(diào)部分歸并）），選取邏輯和歸并邏輯共同構(gòu)成了關(guān)鍵路徑.選取邏輯通過比較2 組FIFO 隊(duì)首的數(shù)據(jù)，將隊(duì)首數(shù)據(jù)較小的一組數(shù)據(jù)出隊(duì)，并與反饋寄存器中的數(shù)據(jù)一起送至雙調(diào)半排序模塊進(jìn)行比較，比較結(jié)果中較小的部分輸出，而將另一部分反饋回反饋寄存器.

圖10 帶有反饋路徑的排序架構(gòu)及其優(yōu)化Fig.10 Sorting architecture with feedback datapath and its optimization

考慮到Casper 等人[30]所提架構(gòu)中的關(guān)鍵路徑含有反饋路徑，會影響到頻率的提升，許多工作對此進(jìn)行了優(yōu)化.針對關(guān)鍵路徑中的雙調(diào)半排序模塊，Mashimo等人[15]的SHMS 使用一組流水化的排序邏輯單元來替代雙調(diào)半排序網(wǎng)絡(luò)，如圖10（b）所示.進(jìn)一步，Saitoh等人[52]提出的MMS 將關(guān)鍵路徑中的反饋路徑去除，如圖10（c）所示，運(yùn)行頻率再次得以提升.但是MMS需要使用2 組歸并邏輯，為減少這一硬件資源占用，Papaphilippou 等人[19]提出的FLiMS 僅需要1 個(gè)雙調(diào)半排序模塊，在保證頻率不受損的前提下實(shí)現(xiàn)了近一半的資源節(jié)省，如圖10 （d）所示.與SHMS 和HMS的2 組輸入FIFO 的數(shù)據(jù)組織方式不同，F(xiàn)LiMS 需要P個(gè)輸入FIFO，P為雙調(diào)半排序的輸入端口數(shù)目，并且需要將2 組有序數(shù)據(jù)按循環(huán)的方式依次寫入不同的FIFO 中.在組成歸并樹時(shí)，這一特征會使得第i層歸并模塊的輸出需要先經(jīng)過一個(gè)數(shù)據(jù)調(diào)度模塊，然后才能按特定順序?qū)懭氲降趇+1 層的輸入緩存中.

2.2 基于FIFO 的歸并排序設(shè)計(jì)分析

FMS 基本結(jié)構(gòu)如圖11（a）所示，基于FMS 的排序設(shè)計(jì)所能處理的數(shù)據(jù)規(guī)模受FIFO 容量限制，F(xiàn)IFO滿溢出之后需要寫回至DRAM 或磁盤中，由此引發(fā)的額外訪存開銷使整體性能惡化.為減少FIFO 資源的消耗，Marcelino 等人[1]提出了將輸出FIFO 和1 個(gè)輸入FIFO 復(fù)用的非平衡解決方案，如圖11（b）所示.該架構(gòu)在排序32 K 個(gè)32 b 數(shù)據(jù)時(shí)，只占用了22%的BRAM 資源.

圖11 FMS 結(jié)構(gòu)Fig.11 FMS structure

對于長度為N的輸入，F(xiàn)MS 級聯(lián)結(jié)構(gòu)通過將lb （N）組FMS 級聯(lián)起來可以實(shí)現(xiàn)完整數(shù)據(jù)排序，如圖11（c）所示.該結(jié)構(gòu)級聯(lián)間的中間數(shù)據(jù)結(jié)果均需要占用FIFO資源，并且需要在上一層的輸出數(shù)據(jù)完全準(zhǔn)備好之后，才能開始下一層的數(shù)據(jù)排序.考慮到在歸并過程中，不需要關(guān)心2 序列長度是否一致以及對2 輸入有序序列的來源沒有特定要求，因此當(dāng)?shù)? 輸入端口的第1 個(gè)數(shù)據(jù)出現(xiàn)時(shí)就可以開始進(jìn)行歸并，如此可以減少輸入數(shù)據(jù)緩存的等待時(shí)間[4].

基于FIFO 的排序架構(gòu)在資源占用率和延時(shí)方面均存在明顯缺陷，在研究與實(shí)際應(yīng)用中均很少出現(xiàn).在實(shí)際使用時(shí)，多是針對數(shù)據(jù)規(guī)模不超過板上存儲的情況，借助于部署多組FMS 實(shí)現(xiàn)高并行，但隨著歸并過程的不斷迭代，任務(wù)量在FMS 之間分配不均衡，越來越多的FMS 會處于空閑狀態(tài)，直至最后一次迭代時(shí)，只能由一組FMS 單獨(dú)承擔(dān).

2.3 歸并樹設(shè)計(jì)分析

歸并樹以二叉樹的形式將歸并模塊和緩存模塊組織在一起，如圖12 （a），對于歸并樹的優(yōu)化主要集中在硬件資源占用率、延時(shí)、吞吐率和數(shù)據(jù)分布等方面.

圖12 歸并樹及其優(yōu)化Fig.12 Merge tree and its optimizations

歸并類排序加速整體可以分為預(yù)排序階段和歸并階段，其中預(yù)排序階段部署在歸并階段之前，用以產(chǎn)生有序子序列以便于歸并階段進(jìn)行歸并，進(jìn)而減少歸并階段的迭代次數(shù)，減少大量小規(guī)模數(shù)據(jù)的傳輸.相比起許多研究工作預(yù)先假設(shè)了有序子序列的存在或者將預(yù)排序任務(wù)交給CPU 來處理，單獨(dú)設(shè)計(jì)預(yù)排序階段需要考慮算法性能和硬件資源占用率等因素.預(yù)排序階段可以選用多種排序算法，如排序網(wǎng)絡(luò).預(yù)排序階段所占用的資源不能過多，需要與后續(xù)歸并階段整體進(jìn)行規(guī)劃.預(yù)排序階段在帶寬允許的情況下可以與歸并階段并行執(zhí)行，或者預(yù)排序階段完全執(zhí)行完畢之后再執(zhí)行歸并階段.后者可以復(fù)用預(yù)排序所占用的資源，如可以通過FPGA 硬件部分重配置或者預(yù)先生成比特流，待預(yù)排序階段結(jié)束，重新配置FPGA 硬件邏輯.

歸并樹存在著資源有效利用率不高的問題，限制了歸并樹規(guī)模的擴(kuò)大，對此可以采用可重配置的架構(gòu)設(shè)計(jì)[14].對于以比較交換模塊為歸并模塊的歸并樹而言，同一時(shí)鐘周期下每一層只會有1 個(gè)比較交換模塊處于工作狀態(tài)，即N輸入的歸并樹的比較器資源的有效利用率為lb （N/（N-1））.因此，每層可以只配置1 個(gè)比較交換模塊，如圖12（b）所示.為了支持這一設(shè)計(jì)結(jié)構(gòu)，層與層之間的緩存模塊也需要相應(yīng)地進(jìn)行改進(jìn)，原有的獨(dú)立FIFO 合并并加以編號形成了FIFO 陣列.對于第i+1 層來說，若其輸入來自于索引為j的緩存，則第i層歸并模塊需要從索引為2j和2j+1 的輸入緩存中獲取數(shù)據(jù)進(jìn)行比較.該設(shè)計(jì)在性能僅下降1.31 倍的同時(shí)，減少了52.4 倍的硬件資源占用.

數(shù)據(jù)分布的不確定性導(dǎo)致緩存模塊的數(shù)據(jù)消耗速率在0～P之間變動（BPM 的輸入端口數(shù)目為2×P），若使用雙端存儲實(shí)現(xiàn)緩存模塊會占用大量面積并且讀取效率低下，進(jìn)而導(dǎo)致排序加速性能受損.因此，Song 等人[12]將1 個(gè)寬FIFO 分成多個(gè)并行的窄FIFO陣列，每個(gè)窄FIFO 輸出速率為0 或1，因此每個(gè)窄FIFO 可以使用移位寄存器查找表（shift register lookup table，SRL）實(shí)現(xiàn).為保持BPM 輸入序列的雙調(diào)性,各個(gè)窄FIFO 的輸出結(jié)果需經(jīng)由一個(gè)桶形移位寄存器進(jìn)行移位再輸入至BPM 中，桶形移位的移位數(shù)由BPM 的反饋決定.該設(shè)計(jì)的平均吞吐率為24.64 GBps，相比于傳統(tǒng)的串行排序器提升了160 倍.

Samardzic 等人[23]提出的Bonsai 針對數(shù)據(jù)規(guī)模、數(shù)據(jù)位寬、計(jì)算資源、存儲帶寬和容量等因素，建立了歸并樹的最優(yōu)化模型以優(yōu)化歸并樹配置從而達(dá)到減小延時(shí)、提高吞吐率的目的.歸并樹在配置時(shí)需要確定輸入和輸出的端口數(shù)目，輸入端口數(shù)目越多，所需要的迭代次數(shù)越少，但是由于輸入端口一般會配備FIFO 用以緩存數(shù)據(jù)，輸入端口數(shù)目過大會導(dǎo)致所需要的FIFO 資源過多，同時(shí)樹的深度也會不斷增大，歸并樹整體所需要的硬件資源也會增多.而輸出端口數(shù)目盡管與歸并樹的吞吐率呈正相關(guān)，但也受到存儲帶寬限制.如圖13（a）所示，Bonsai 使用BPM 作為歸并模塊，通過最優(yōu)化模型確定輸入、輸出端口數(shù)目之后，自頂向下依次決定每一層中所使用的BPM規(guī)模，其中k-M 表示每個(gè)時(shí)鐘周期輸出k個(gè)數(shù)據(jù)的歸并模塊.Bonsai 完整的數(shù)據(jù)流如圖13（b）所示，從SSD 或Flash 中傳輸過來的數(shù)據(jù)首先經(jīng)過預(yù)排序再存儲至DRAM 中；為將DRAM 中的數(shù)據(jù)完整排序，Bonsai 并行部署了多組歸并樹（如歸并樹組1～3），同時(shí)歸并樹組內(nèi)部將多個(gè)歸并樹級聯(lián)形成流水線，以充分利用存儲帶寬；DRAM 規(guī)模的有序數(shù)據(jù)傳輸至SSD 或Flash 之后，借助歸并樹4 完成最終的歸并排序.需要指出的是，為適應(yīng)從MB 至TB 量級的不同數(shù)據(jù)規(guī)模，Bonsai 存儲架構(gòu)具體包括DRAM，HBM，SSD 等多種設(shè)備，對于不同的數(shù)據(jù)規(guī)模和存儲設(shè)備，需要使用不同的歸并樹配置，即圖13（b）中歸并樹組1～3 與歸并樹4 的配置并不一致.

圖13 Bonsai 架構(gòu)Fig.13 The architecture of Bonsai

Qiao 等人[26]在Bonsai 基礎(chǔ)上提出的FANS 將數(shù)據(jù)來源遷移至SmartSSD，以近存計(jì)算的方式實(shí)現(xiàn)排序的加速.SmartSSD 將Xilinx KU15P FPGA 和3.84 TB 的NAND flash 以U.2 的形式集成在一起，F(xiàn)PGA配有4 GB 的DRAM，并將其映射至應(yīng)用地址空間，DRAM 和SSD 控制器之間可以直接通過PCIe 進(jìn)行傳輸而無需主機(jī)端干預(yù)，進(jìn)而無需數(shù)據(jù)在主存和磁盤之間的反復(fù)搬運(yùn).與Bonsai 類似，同樣針對SmartSSD建立了最優(yōu)化模型，并且指出排序加速的關(guān)鍵性因素不僅包括Flash 的帶寬，還包括主存帶寬、排序核的配置以及中間排序結(jié)果等.為了預(yù)排序階段和歸并階段均能利用全部FPGA 資源進(jìn)而提升性能，提前將各階段的比特流綜合好，分階段下發(fā)到FPGA 上以實(shí)現(xiàn)不同階段間的切換，相比于Jun 等人[16]的工作實(shí)現(xiàn)了3 倍的性能提升.

2.4 非歸并類排序設(shè)計(jì)分析

相比歸并類排序，非歸并類排序在特定應(yīng)用場景有一定優(yōu)勢，對歸并排序起到了彌補(bǔ)作用；但處理的數(shù)據(jù)規(guī)模有限，并且缺乏統(tǒng)一的架構(gòu)模型用以分析、演進(jìn)升級.文獻(xiàn)[35] 中為利用有限的存儲容量，對于插入排序進(jìn)行了改進(jìn)，每個(gè)輸入數(shù)據(jù)都添加一個(gè)時(shí)間戳，借助類似于LRU（least recently use）的Cache替換策略，將超出時(shí)間閾值的數(shù)據(jù)淘汰.基數(shù)/桶排序是非歸并類排序中應(yīng)用較為廣泛的一類算法，被許多排序加速方案融合借鑒，如下面將要介紹的采樣排序和基于地址的排序.

基數(shù)/桶排序最原始的算法原理依據(jù)單一數(shù)據(jù)位進(jìn)行排序，排序時(shí)間與數(shù)據(jù)位寬相關(guān)，對于一個(gè)k位的數(shù)據(jù)，時(shí)間復(fù)雜度為O(N×k).因此，理論上當(dāng)排序數(shù)據(jù)滿足k＜lbN時(shí)，使用基數(shù)排序會比歸并排序更有優(yōu)勢，但由于數(shù)據(jù)分布、范圍無法預(yù)知，基數(shù)/桶排序中對于桶的劃分和每個(gè)桶內(nèi)所會分配的數(shù)據(jù)量均無法確定.對于數(shù)據(jù)偏斜非常嚴(yán)重的情況，基數(shù)/桶排序?qū)⑼嘶癁榘次槐容^的快速排序算法.基數(shù)/桶排序?qū)τ谄洗鎯π枨筝^大，依賴于大規(guī)模存儲以緩解讀寫存儲開銷[29,40].

Chen 等人[25]針對大數(shù)據(jù)規(guī)模下訪存頻繁、片內(nèi)外數(shù)據(jù)傳輸耗時(shí)的問題，設(shè)計(jì)了采樣排序（sample sort）軟硬件協(xié)同加速系統(tǒng).相比于基數(shù)/桶排序中桶大小無法確定，該系統(tǒng)借助軟件隨機(jī)采樣來應(yīng)對數(shù)據(jù)偏斜以將桶粗粒度地分成近似相等的大小，對于桶內(nèi)數(shù)據(jù)溢出的情況由軟件負(fù)責(zé)該部分?jǐn)?shù)據(jù)的排序.如圖14 所示，采樣排序算法整體分為采樣、劃分和子序列排序3 個(gè)階段.具體來說：1）由于劃分階段存在數(shù)據(jù)依賴、軟件執(zhí)行成本過高，需要借助于軟件先找出不同數(shù)據(jù)塊之間的分隔點(diǎn)，分隔點(diǎn)兩兩之間構(gòu)成桶.基于軟件的隨機(jī)采樣將數(shù)據(jù)整體劃分成彼此沒有交集的子數(shù)據(jù)塊，因此，采用任意其他排序算法獨(dú)立并行地對不同的子數(shù)據(jù)塊進(jìn)行排序，其輸出結(jié)果可以直接拼接在一起，而不需要額外的歸并階段.2）FPGA 在軟件粗粒度桶劃分的基礎(chǔ)上，進(jìn)行細(xì)粒度劃分直至子序列的大小可以在板上存儲容納，使得存儲之間的交互僅限于板上存儲資源之間.3）最終，借助于排序網(wǎng)絡(luò)并行完成各桶內(nèi)數(shù)據(jù)的排序，排序結(jié)果傳回Host 端進(jìn)行后續(xù)簡單處理.

圖14 采樣排序Fig.14 Sample sort

該系統(tǒng)[25]能夠以7.2 GBps 的速度處理230 條記錄，每條記錄包括10 B 的Key 和4 B 的index，總計(jì)14 GB.在相同數(shù)據(jù)規(guī)模下，Bonsai 的吞吐率為5.8 GBps，可以看出與歸并類排序的性能差距并不大.更重要的一點(diǎn)是，14 GB 的數(shù)據(jù)規(guī)模沒有超過大多數(shù)FPGA 開發(fā)板片上DRAM 容量，因此數(shù)據(jù)傳輸僅限于板上存儲資源內(nèi)部之間，與Host 端的數(shù)據(jù)交互可以忽略不計(jì).該軟硬協(xié)同設(shè)計(jì)方案兼顧了CPU 和FPGA 二者的算力，從而達(dá)到一個(gè)較好的加速效果，這也為其他排序加速提供了借鑒意義，如歸并排序FPGA 加速特定長度數(shù)據(jù)排序的同時(shí)，CPU 可以負(fù)責(zé)收集該數(shù)據(jù)完成最終階段的歸并.

基于地址的排序加速[3]將數(shù)據(jù)作為存儲地址，對于數(shù)據(jù)Q，將索引為“Q”的存儲區(qū)域置為有效，最終排序結(jié)果經(jīng)過解碼器/轉(zhuǎn)換器轉(zhuǎn)換產(chǎn)生，如圖15 所示.輸入二進(jìn)制形式的M位數(shù)據(jù)，需要占用一個(gè)長度為2M位的存儲區(qū)域，具體來說，對于一個(gè)64 b 的數(shù)據(jù)，就需要16 EB.因此需要將數(shù)據(jù)位劃分成2 部分，分別是低K位和剩余的高M(jìn)-K位.首先對于高M(jìn)-K位建立多叉樹，將數(shù)據(jù)按照高M(jìn)-K位的不同組合進(jìn)行劃分，地址范圍從原先的2M位縮減為2M-K位，同時(shí)每個(gè)地址與實(shí)際存儲地址之間存在映射關(guān)系，類似于基數(shù)/桶排序中桶的劃分，可以對應(yīng)多個(gè)數(shù)據(jù).

圖15 基于地址的排序Fig.15 Address-based sort

基于地址的排序缺乏對重復(fù)數(shù)據(jù)的處理能力，且瓶頸在于非連續(xù)存儲的存取開銷.當(dāng)數(shù)據(jù)散列度過大時(shí)，會出現(xiàn)大量的空閑存儲區(qū)域，因此只適用于數(shù)據(jù)散列度小、數(shù)據(jù)規(guī)模小的排序場景.為解決該布爾可滿足性問題，應(yīng)用了如下所述的樹狀行走表（tree-walk table）方法：如對于20910 來說，其二進(jìn)制是110100012，從最高位開始每2 位放在一起，分別是11，01，00，因此使用四叉樹，樹節(jié)點(diǎn)之間的邊代表如11，10，01，00，以此類推，如此能將數(shù)據(jù)按高6 位的不同組合形式分到不同的葉子節(jié)點(diǎn)上去；而對于葉子節(jié)點(diǎn)，將每一個(gè)葉子節(jié)點(diǎn)中的數(shù)據(jù)用其他排序算法進(jìn)行排序.該工作的測試基準(zhǔn)大小為576 KB（218 項(xiàng)18 b 數(shù)據(jù)）的排序，總共耗時(shí)0.7 ms.對于浮點(diǎn)數(shù)，將整數(shù)部分按上述排序方法進(jìn)行排序，而對小數(shù)部分采用其他算法進(jìn)行排序.該工作適合部署在內(nèi)容尋址存儲器（content addressed memory，CAM）上，但該工作沒有部署在CAM 上.

3 數(shù)據(jù)庫排序加速設(shè)計(jì)

排序在數(shù)據(jù)庫中至關(guān)重要，一方面為直觀地展示、分析數(shù)據(jù)結(jié)果，需要對數(shù)據(jù)進(jìn)行升序或降序排列，在TPC-H 測試集的22 條查詢語句中通過“orderBy”顯式調(diào)用排序出現(xiàn)了多達(dá)18 次[50]；另一方面分組、基于排序的連接等操作也要求在有序數(shù)據(jù)上進(jìn)行.因此，對數(shù)據(jù)庫進(jìn)行卸載加速時(shí)，排序的合理設(shè)計(jì)及優(yōu)化是必不可少的.

數(shù)據(jù)庫排序加速設(shè)計(jì)在設(shè)計(jì)、實(shí)現(xiàn)、測試等階段面臨的問題存在共通性，表3 中列舉了各代表性工作的實(shí)現(xiàn)方法及優(yōu)化結(jié)果.在算法選擇方面，同樣是歸并排序居多，這主要是由于數(shù)據(jù)庫中數(shù)據(jù)類型多樣，包括32 b 整型（INTEGER）、定長字符串（CHAR）和不定長字符串（VARCHAR）、128 b 高精度浮點(diǎn)數(shù)（DECIMAL）、64 b 整型日期（DATE），并且不同數(shù)據(jù)表或者同一數(shù)據(jù)表中不同列的數(shù)據(jù)規(guī)模跨度大.除此之外，考慮到數(shù)據(jù)已基本有序（局部有序，整體無序）這一數(shù)據(jù)庫常見情形以及流式數(shù)據(jù)傳輸方式，錦標(biāo)賽排序也適用于數(shù)據(jù)的預(yù)排序.在硬件利用率及功耗方面，排序加速模塊通常會占用較多的硬件資源且功耗較多，如Q100 中排序的功耗及其占比和排序硬件資源面積及其占比均是最高的，分別為68.2 mW（61.9%）和1.13 mm2（74.3%），而AQUOMAN 甚至需要為排序模塊配置一塊單獨(dú)的FPGA.因此，數(shù)據(jù)庫排序加速設(shè)計(jì)尤其需要注意不同操作間的資源競爭問題.

Table 3 Sort Acceleration Design of Database表3 數(shù)據(jù)庫排序加速設(shè)計(jì)

Q100 數(shù)據(jù)庫排序的數(shù)據(jù)規(guī)模僅為1 024，主要是因?yàn)樵谂判蛑霸O(shè)置了劃分，用以將每一行數(shù)據(jù)劃分至不同且唯一的分塊中，不同排序模塊并行處理不同的數(shù)據(jù)分塊，從而達(dá)到均衡多個(gè)并行排序模塊間負(fù)載的效果.劃分方法包括范圍劃分、直接劃分和哈希劃分[33,46]，其中范圍劃分可以容忍不規(guī)則數(shù)據(jù)分布，如圖16 所示，序列A和序列B在范圍劃分的基礎(chǔ)之上，分塊{a1,b1}和{a2,b2}可以并行進(jìn)行排序，2 組分塊的排序結(jié)果無需額外歸并.需要注意的是，劃分需要對數(shù)據(jù)進(jìn)行多輪次讀取以尋找合適的劃分邊界，同時(shí)劃分的硬件資源占用率也極高（Q100 中為61.9%），因此在實(shí)際部署時(shí)需要結(jié)合性能設(shè)計(jì)目標(biāo)進(jìn)行權(quán)衡取舍.

圖16 范圍劃分Fig.16 Range partition

除共通性問題之外，數(shù)據(jù)庫排序加速更加需要注意的是其獨(dú)特的要求，需要排序加速架構(gòu)進(jìn)行適應(yīng)性調(diào)整優(yōu)化.具體來說，存在5 個(gè)問題與挑戰(zhàn)：

1）排序伴生操作間合作與競爭問題.排序在數(shù)據(jù)庫中一般不單獨(dú)出現(xiàn)，伴生操作如過濾（filter）、提?。╬rojection）、連接（join）、分組（group-by）等， 不同操作間的執(zhí)行順序受DBMS 優(yōu)化策略影響，一般選擇先進(jìn)行數(shù)據(jù)的過濾、提取以縮減數(shù)據(jù)量，或者基于排序之后的結(jié)果進(jìn)行分組、連接，因此在排序的數(shù)據(jù)來源、去向方面，如何減少中間數(shù)據(jù)的規(guī)模和外部訪存次數(shù)均是需要格外注意的；在競爭方面，受FPGA資源限制，需針對各操作的靜態(tài)資源占用進(jìn)行合理分配，而排序和其他操作的動態(tài)功耗競爭問題目前尚未有合理的解決措施.

2）排序衍生特有操作優(yōu)化問題.如最大值/最小值（max/min）、選取前K項(xiàng)最值（Top-K）[54]操作和排序合并連接（sort-merge join）等，該類型操作需要對原始排序加速架構(gòu)進(jìn)行調(diào)整或者設(shè)計(jì)數(shù)據(jù)流式新型架構(gòu).

3）數(shù)據(jù)組織方式問題.具體分為數(shù)據(jù)格式和存儲組織方式.數(shù)據(jù)格式受軟硬件接口設(shè)計(jì)影響，不再是簡單的鍵-值形式，排序加速將面臨如何適應(yīng)Apache Arrow[55]，Parquet[56]，CSV[57]等數(shù)據(jù)格式、減輕（反）序列化格式轉(zhuǎn)換開銷等問題；存儲組織方面，對某一列進(jìn)行排序時(shí)，數(shù)據(jù)庫中其他列數(shù)據(jù)（衛(wèi)星數(shù)據(jù)）也需要相應(yīng)進(jìn)行位置變動，在行式和列式存儲方式下，衛(wèi)星數(shù)據(jù)的聚集（gather）/分散（scatter）操作處理會存在差異；除此之外，數(shù)據(jù)遷移到硬件板卡上時(shí)，不同的數(shù)據(jù)庫加速引擎多會自定義數(shù)據(jù)管理系統(tǒng)，如DOE中的DOMS 和RAPID 中的DMS，由此可能為排序增加額外的數(shù)據(jù)管理開銷.

4）多租戶安全與請求多樣性問題.數(shù)據(jù)庫卸載引擎需要處理多租戶請求問題，即多用戶同時(shí)進(jìn)行不同的SQL 查詢請求，除去任務(wù)調(diào)度方面的問題之外，一方面存在同一表中對多列進(jìn)行排序等請求多樣性問題，另一方面出于多租戶間數(shù)據(jù)隱私安全需要引入相應(yīng)的安全保護(hù)機(jī)制，包括數(shù)據(jù)加密、多副本容錯(cuò)和應(yīng)對如SQL 注入攻擊、敏感數(shù)據(jù)未脫敏等應(yīng)用程序業(yè)務(wù)邏輯漏洞和缺陷的數(shù)據(jù)庫防火墻等，如何平衡數(shù)據(jù)安全限制與性能要求同樣是一個(gè)值得關(guān)注的研究點(diǎn)，如為避免時(shí)間攻擊風(fēng)險(xiǎn)而設(shè)計(jì)的恒定時(shí)間歸并排序架構(gòu)[58].

5）云原生、分布式數(shù)據(jù)庫、NewSQL 等新型數(shù)據(jù)庫的出現(xiàn)帶來新的挑戰(zhàn).數(shù)據(jù)庫技術(shù)不斷發(fā)展，RDMA，NVM 等新型技術(shù)的引入將從帶寬、數(shù)據(jù)通路等多方面對數(shù)據(jù)庫中各部分操作產(chǎn)生影響；排序加速的角色、意義不局限于數(shù)據(jù)查詢分析層面，如NewSQL 下的KV存儲（key-value store）依賴于LSM-tree（log-structured tree）索引進(jìn)行快速讀取，在這一過程中，需要對寫入磁盤中的數(shù)據(jù)按鍵（key）范圍分層，歸并排序之后落盤，從而使得數(shù)據(jù)可以通過二分查找等措施便捷獲取.

上述5 個(gè)問題與數(shù)據(jù)庫卸載引擎的設(shè)計(jì)方式是密不可分的，接下來我們將結(jié)合數(shù)據(jù)庫卸載引擎架構(gòu)模型，進(jìn)一步分析其機(jī)遇和挑戰(zhàn).對于數(shù)據(jù)庫卸載引擎，可以劃分成查詢加速引擎、存儲架構(gòu)、互聯(lián)結(jié)構(gòu)、控制中心以及外設(shè)5 個(gè)部分，如圖17 所示[53].下面將從上述部分對數(shù)據(jù)庫排序加速設(shè)計(jì)的影響出發(fā)介紹排序加速架構(gòu)的適應(yīng)性調(diào)整優(yōu)化.

圖17 數(shù)據(jù)庫卸載引擎模型Fig.17 Model of database offloading engine

查詢加速引擎依據(jù)SQL 查詢計(jì)劃樹，將連接、過濾以及聚合等操作進(jìn)行提取卸載，其中與排序關(guān)系最為密切的包括最大值、最小值、Top-K、基于排序的連接操作等獨(dú)有特殊操作.最大值、最小值和Top-K操作不需要將數(shù)據(jù)全部排列有序，而只需要獲取到滿足條件的1 個(gè)或多個(gè)數(shù)據(jù)即可，因此無需保留完整的排序架構(gòu).

1）Top-K操作，如與軟件實(shí)現(xiàn)中使用的大/小頂堆算法不同，硬件實(shí)現(xiàn)上需選取便于流水線、可并行的架構(gòu)，如可以使用由雙調(diào)排序網(wǎng)絡(luò)演進(jìn)而來的最大集排序[51]；或者采用新型排序架構(gòu)，如基于數(shù)據(jù)流式架構(gòu)的插入排序[32,48]，具體如圖18（a）所示，每個(gè)PE（processing element）保留至今為止遇到的最大值，最終最大的K個(gè)值依次保留在各PE 中；或者采用文獻(xiàn)[9]中提出的帶有反饋路徑的基于FIFO 的歸并排序架構(gòu)，如圖18（b）所示.

圖18 Top-K 操作架構(gòu)Fig.18 Architecture of Top-K operation

2）對于最大值或最小值操作，可以視為K=1 時(shí)的特殊情形進(jìn)行處理.

3) 基于排序的連接如圖19 所示，數(shù)據(jù)首先經(jīng)過排序模塊將表A和表B中的列進(jìn)行排序，然后再經(jīng)由歸并模塊進(jìn)行歸并，歸并結(jié)果中相同數(shù)值會被排序到一起，最終經(jīng)過重復(fù)檢測即可得到結(jié)果，各模塊間可以并行流水進(jìn)行.

圖19 排序合并連接操作Fig.19 Sort-merge join operation

對于模型中的存儲架構(gòu)部分，將從存儲的組織方式、數(shù)據(jù)格式和自定義存儲管理3 個(gè)方面進(jìn)行介紹.首先，存儲的組織方式分為行式存儲（如Oracle，MySQL）和列式存儲（如MonetDB，PostgreSQL）.行式存儲如圖20（a）所示，其下關(guān)鍵列數(shù)據(jù)非連續(xù)性存儲，在對關(guān)鍵列進(jìn)行排序時(shí)，衛(wèi)星數(shù)據(jù)會占用訪存帶寬造成整體吞吐率下降，如IBM 的設(shè)計(jì)中當(dāng)關(guān)鍵列和衛(wèi)星數(shù)據(jù)大小超過120 B 時(shí)，吞吐率將會受限于PCIe帶寬，并且隨著衛(wèi)星數(shù)據(jù)規(guī)模的增大而衰減[31].為了減少冗余帶寬占用、妥善利用數(shù)據(jù)局部性，現(xiàn)今數(shù)據(jù)庫多采用列式存儲.對于列式存儲如圖20（b）所示，關(guān)鍵列數(shù)據(jù)連續(xù)存儲，但衛(wèi)星數(shù)據(jù)仍然需要通過行索引與關(guān)鍵列進(jìn)行關(guān)聯(lián)，因此如何應(yīng)對衛(wèi)星數(shù)據(jù)同步排序時(shí)的隨機(jī)訪問開銷，很大程度上會影響整體加速效果.尤其是當(dāng)數(shù)據(jù)表規(guī)模過大超出板上存儲時(shí)需要將表進(jìn)行切分（如圖20 中的塊1～P），排序需要對不同分塊的排序結(jié)果進(jìn)行排序，并將各分塊排序結(jié)果進(jìn)行歸并.

圖20 數(shù)據(jù)庫數(shù)據(jù)組織形式Fig.20 Data arrangement of database

不同系統(tǒng)組件在內(nèi)存中對于數(shù)據(jù)的表示會有所不同，Apache Arrow 的提出即是為了解決異構(gòu)系統(tǒng)間通信序列化的瓶頸，為大數(shù)據(jù)提供通用的內(nèi)存格式.在FPGA 排序加速時(shí)同樣會面臨這一瓶頸，并且Arrow格式在內(nèi)存中是高度連續(xù)的，也非常適用于FPGA.因此，基于Apache Arrow 模式中的數(shù)據(jù)集類型的描述，進(jìn)行FPGA 加速器設(shè)計(jì)被認(rèn)為是高效且易用的.目前，F(xiàn)letcher[59]已基于Apache Arrow 格式生成了用于FPGA 加速器的硬件接口，從而允許FPGA 加速器與各種高級軟件語言高效集成.在解決了軟硬件接口的基礎(chǔ)之上，基于Apache Arrow 數(shù)據(jù)格式的排序加速設(shè)計(jì)也值得期待.

除沿用軟件數(shù)據(jù)格式標(biāo)準(zhǔn)之外，許多數(shù)據(jù)庫卸載引擎自定義了適合其自身的存儲管理模塊.如圖21所示，DOE[53]中使用ID 而非物理地址進(jìn)行列數(shù)據(jù)的完整訪問，ID 的申請、刪除、回收等管理機(jī)制會涉及到ID 與物理地址之間的轉(zhuǎn)換開銷；如圖21(b)所示，為解決SQL 查詢分析結(jié)果規(guī)模不定的問題，需要進(jìn)行存儲空間的動態(tài)分配，因此DOE 設(shè)計(jì)了“鏈表式”的頁面管理機(jī)制.當(dāng)對該列數(shù)據(jù)再次訪問時(shí)，由硬件自行完成鏈表的檢索而掩蓋物理地址的頻繁計(jì)算，從而達(dá)到快速存取數(shù)據(jù)的目的.

圖21 DOE 數(shù)據(jù)組織形式Fig.21 Data arrangement of DOE

專用互聯(lián)結(jié)構(gòu)和外設(shè)等影響排序加速的數(shù)據(jù)通路，使排序最優(yōu)化模型緩解了帶寬限制因素.專用互聯(lián)結(jié)構(gòu)方面，由于各操作間數(shù)據(jù)傳遞方向復(fù)雜多變，保守起見需要全連通圖拓?fù)湓O(shè)計(jì)，因此Q100 中設(shè)計(jì)了2D-網(wǎng)格型片上網(wǎng)絡(luò)，帶寬可達(dá)6.3 GBps.外設(shè)方面，基于文獻(xiàn)[38]中的統(tǒng)計(jì)結(jié)果，我們可以得到如圖22所示的設(shè)備級帶寬發(fā)展趨勢，可以看出網(wǎng)絡(luò)帶寬與PCIe，DRAM 帶寬之間的差距在逐漸縮小，F(xiàn)PGA 可以直接接入網(wǎng)絡(luò)傳輸，數(shù)據(jù)不需要在網(wǎng)絡(luò)分層和軟件棧之間復(fù)制傳輸，基于網(wǎng)絡(luò)接口的排序加速設(shè)計(jì)目前沒有相應(yīng)的研究.

圖22 設(shè)備級帶寬發(fā)展趨勢[38]Fig.22 Bandwidth development trends at device-level[38]

控制中心與數(shù)據(jù)庫用戶具體請求相關(guān)，目前尚未有對請求多樣性問題的深入研究.數(shù)據(jù)庫多用戶并發(fā)請求或者同一用戶請求中含有多個(gè)排序操作時(shí)，需要同時(shí)排序多組數(shù)據(jù)，一方面需要配備多個(gè)并行加速引擎，另一方面可以利用多組數(shù)據(jù)間的數(shù)據(jù)不相關(guān)性消除流水線間空隙.除此之外，用戶請求還包括基于多于1 個(gè)列屬性進(jìn)行排序，即首先按列A進(jìn)行排序，當(dāng)列A中出現(xiàn)數(shù)據(jù)相同時(shí)，再按照列B進(jìn)行排序，該情況下最直接的做法是將列B按照列A的排序結(jié)果進(jìn)行重排之后，再判斷列A中重復(fù)數(shù)據(jù)出現(xiàn)的位置，以此來篩選列B數(shù)據(jù)從而啟動新一輪的排序，但該方案排序比較次數(shù)過多，數(shù)據(jù)搬運(yùn)過于頻繁.

4 未來研究方向

Roofline 模型將片上處理性能和片外訪存流量相關(guān)聯(lián)，是在CPU 和其他架構(gòu)上進(jìn)行性能建模的一種有效和直觀的方式[60].Roofline 模型根據(jù)程序的計(jì)算強(qiáng)度（operation intensity，OI）給出了一個(gè)可實(shí)現(xiàn)的性能上限，即min(PeakPerf,PeakBW×OI)，其中PeakPerf，PeakBW分別為目標(biāo)平臺所能提供的峰值性能和峰值帶寬，OI定義為目標(biāo)平臺上每字節(jié)訪存流量上所進(jìn)行的操作數(shù).在本節(jié)中，我們將Roofline 模型應(yīng)用至基于FPGA 的排序加速上，以分析探索各種加速方案的瓶頸，以及基于FPGA 排序加速的潛在發(fā)展空間.

不同F(xiàn)PGA 平臺算力不同，因此我們以應(yīng)用較多的AWS F1 為例，同時(shí)由于Roofline 模型最初應(yīng)用于架構(gòu)穩(wěn)定的多核處理器建模，因此峰值性能為常數(shù)，而FPGA 作為可編程平臺，其峰值性能與具體排序架構(gòu)相關(guān)[61]，因此盡管歸并排序[23]和采樣排序[25]均基于AWS F1 實(shí)現(xiàn)，二者的峰值性能并不一致，具體可表示為PeakPerfFPGA=PerfPE×SC，其中PerfPE為每個(gè)處理單元PE（在排序架構(gòu)中可為單獨(dú)的歸并樹、桶等）所能達(dá)到的峰值性能，由PE 的延時(shí)和最大工作頻率決定，SC為可支持的最大并行擴(kuò)展數(shù).由于各工作一般不單獨(dú)公開其PE 延時(shí)，因此我們暫時(shí)以排序模塊總延時(shí)與模塊數(shù)目的比值作為PE 延時(shí)的近似值.對于峰值帶寬，一般可僅簡單考慮DRAM 帶寬[62].對于計(jì)算強(qiáng)度，由于排序一般可通過FOR 循環(huán)的方式表征，當(dāng)各迭代之間無數(shù)據(jù)復(fù)用時(shí)，OI=OP/(IN+OUT)，其中OP為每次迭代時(shí)所進(jìn)行的操作數(shù)，IN和OUT為該次迭代時(shí)的輸入、輸出數(shù)據(jù)量.

具體來說，AWS F1 共有862 128 個(gè)LUT，同時(shí)配備有峰值帶寬為32 GBps 的DDR DRAM.將每秒整型操作（integer operation per second，INTOPS）視為Roofline模型所需統(tǒng)計(jì)的操作數(shù)（即OP值），分別采用歸并樹（64 個(gè)輸入節(jié)點(diǎn)，每周期32 個(gè)數(shù)據(jù)輸出）和采樣排序架構(gòu)，二者均運(yùn)行在250 MHz 的頻率下.Bonsai 中每個(gè)歸并樹所能達(dá)到的性能上限PerfPE=0.9 TINTOPS，LUT 資源占用率為33.3%，因此可至多并行部署3 組歸并樹，其峰值性能為0.9×3 =2.7 TINTOPS，每輪次輸出數(shù)據(jù)128 B，k輸入雙調(diào)半排序模塊含有(lbk+1)×k/4 個(gè)比較交換模塊，計(jì)算強(qiáng)度為3.375 INTOPS/B；采樣排序架構(gòu)使用2 階劃分模塊將數(shù)據(jù)劃分成218個(gè)桶，每個(gè)桶內(nèi)數(shù)據(jù)量為212，峰值性能約為90 GINTOPS，其計(jì)算強(qiáng)度為0.6 INTOPS/B.整理得到的Roofline 模型如圖23 所示，由此可以看出排序是一種帶寬受限的算法，從存儲資源中獲取到的數(shù)據(jù)未能進(jìn)行足夠的運(yùn)算操作，即架構(gòu)更多地等待新數(shù)據(jù)的到來而非產(chǎn)生新的輸出.類似地，對于FPGA 上的其他排序算法加速方案也可以得到相同的結(jié)論.除此之外，由圖23可以進(jìn)一步得到4 個(gè)結(jié)論：

圖23 FPGA 排序加速的Roofline 模型Fig.23 Roofline model of sorting acceleration on FPGA

1） 提升帶寬上限和帶寬利用率是關(guān)鍵，前者需借助于存儲、互聯(lián)技術(shù)的不斷發(fā)展，后者如圖5 所示提升空間仍然很大.

2） 在現(xiàn)有帶寬利用率下，單FPGA 的排序加速性能提升空間有限且難度極大，現(xiàn)有設(shè)計(jì)已經(jīng)逼近Roofline 模型的峰值帶寬約束，一種可行的解決方案為尋求多FPGA 分布式加速.

3） 歸并類排序與非歸并類排序加速相比峰值性能更優(yōu)，主要是由于其PE 占用資源較少，并行度（SC）更高.

4） 歸并排序、采樣排序距離，其峰值性能均有一定距離，即仍有很多閑置算力，可以用來為排序提供更多的非帶寬限制型輔助支持，如數(shù)據(jù)劃分、去重等.

接下來，我們將針對上述4 個(gè)結(jié)論具體分析并提出可行的解決措施.

基于CPU 的分布式排序是目前應(yīng)用最為廣泛的解決方案，而目前尚未有針對基于FPGA 的分布式排序加速研究.基于CPU 的分布式排序多基于Hadoop或Spark 等分布式框架將一系列通用處理器計(jì)算結(jié)點(diǎn)組織在一起.在這一組織形式下，排序的延遲和吞吐量主要受限于單個(gè)結(jié)點(diǎn)的計(jì)算處理能力以及不同結(jié)點(diǎn)間的通信能力，尤其是磁盤I/O 和網(wǎng)絡(luò)通信這2大瓶頸因素.Bonsai 在100 TB 數(shù)據(jù)規(guī)模下相比單CPU能實(shí)現(xiàn)2 倍的性能加速，但性能并不能隨著FPGA 資源的增加而線性增長.因此，通過PCIe 端對端（peerto-peer）傳輸而非傳統(tǒng)CPU 干預(yù)下的PCIe 路由，解決SSD-FPGA 通信和RDMA 硬件卸載加速應(yīng)對板卡間網(wǎng)絡(luò)通信等方式來解決這2 個(gè)瓶頸將是一個(gè)值得期待的方向.

排序加速架構(gòu)與硬件是松耦合的，新型硬件的引入將進(jìn)一步使得現(xiàn)有架構(gòu)設(shè)計(jì)獲得提升.新型硬件如DPU 等將為排序加速設(shè)計(jì)開辟新的設(shè)計(jì)空間.英特爾的基礎(chǔ)設(shè)施處理器（infrastructure processing unit，IPU）基于Agilex FPGA 和Xeon-D CPU 實(shí)現(xiàn)，同時(shí)配備有高帶寬DRAM、千兆以太網(wǎng)接口等.Xeon-D CPU不僅能夠分擔(dān)一部分?jǐn)?shù)據(jù)排序工作，而且可以勝任數(shù)據(jù)分割以及存儲管理等輔助類工作，并且可以支持RDMA 從而實(shí)現(xiàn)分布式排序加速.目前，尚未有基于DPU 的排序加速研究.

新型開發(fā)工具及編程語言能夠縮短開發(fā)時(shí)間，有助于排序加速設(shè)計(jì)方案的快速迭代更新.基于FPGA進(jìn)行排序加速設(shè)計(jì)，多是基于Verilog 和VHDL 等硬件描述語言進(jìn)行RTL 設(shè)計(jì)，開發(fā)難度大；而基于HLS的高層次綜合設(shè)計(jì)，雖然所能達(dá)到的性能上限與硬件描述語言相比可能存在一定差距，但極大地降低了開發(fā)門檻，可以通過添加控制參數(shù)的方式配置流水和控制循環(huán).作為另一種開發(fā)選擇的SpinalHDL 和Chisel，在以RISC-V 為代表的開源芯片設(shè)計(jì)領(lǐng)域取得了較大的成功，縮短了開發(fā)時(shí)間的同時(shí)也降低了如模塊間連線的出錯(cuò)概率，對于其在FPGA 排序加速領(lǐng)域的應(yīng)用也值得期待.

5 結(jié) 論

為了緩解排序所帶來的性能瓶頸問題，目前的主流方向是將排序這一存儲密集型操作卸載到FPGA 上，利用FPGA 的硬件特性實(shí)現(xiàn)高吞吐率、低延時(shí)和低功耗等目標(biāo).本文討論了各種結(jié)構(gòu)在實(shí)現(xiàn)上的挑戰(zhàn)和背后的驅(qū)動因素、面臨的主要瓶頸問題及相關(guān)改進(jìn)措施.隨著新的應(yīng)用場景的不斷出現(xiàn)、新技術(shù)的迭代更新、輔助工具鏈的日趨完善，基于FPGA 的排序加速工作將繼續(xù)發(fā)展進(jìn)步.

作者貢獻(xiàn)聲明：孔浩負(fù)責(zé)完成數(shù)據(jù)整理、文獻(xiàn)搜集并撰寫論文；盧文巖負(fù)責(zé)論文架構(gòu)討論和論文修改；陳巖負(fù)責(zé)論文數(shù)據(jù)整理和指導(dǎo)；鄢貴海和李曉維提出指導(dǎo)意見并修改論文.