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

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

1 （處理器芯片全國重點實驗室（中國科學院計算技術研究所） 北京 100190）

2 （中國科學院大學 北京 100049）

3 （中科馭數（北京）科技有限公司 北京 100094）

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

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

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

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

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

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

圖1 FPGA 排序加速設計流程Fig.1 Design process of FPGA sort acceleration

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

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

本文所做的主要貢獻有4 個方面：

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

2) 分析了FPGA 排序加速在設計、實現、測評等各不同階段所面臨的問題與挑戰，在排序算法選擇、最優化模型建立以及評測基準的配置等方面，為如何基于FPGA 進行排序加速設計提供指導和幫助；

3) 以數據庫為分析案例，闡明了排序加速在實際應用場景中所面臨的資源競爭、數據組織方式、特有操作與用戶請求多樣性等挑戰與相應架構調整，為其他領域的應用提供了借鑒；

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

1 FPGA 排序加速設計原則

1.1 排序加速算法選擇

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

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

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

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

3)數據寬度.數據寬度一方面與數據類型相關，另一方面排序數據一般分為“鍵”和“值”2 部分，當“值”部分寬度過大無法與“鍵”一起搬運時，會引發衛星數據（satellite data）的處理問題，但一般不影響排序算法的選擇.

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

綜合考慮上述4 個因素之后，圖2 展示了在各類因素限制下的1 種或多種表現較好的可行算法選擇，其中歸并排序對大多因素均具有良好的適應性.

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

1.2 排序加速優化設計

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

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

Table 2 Parameter List表2 參數列表

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

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

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

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

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

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

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

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

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

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

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

該模型有助于研究人員統一不同工作間的研究動機和發展路徑，并且該模型也能起到實際設計空間探索指導作用，當然在實際應用中需要進一步細化.下面，我們將以歸并樹加速設計為例，詳細介紹該模型的應用.

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

約束條件為

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

1.3 排序加速性能測試

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

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

2 FPGA 排序加速分析

FPGA 排序加速目前主要集中在歸并排序領域，非歸并類排序盡管在特定應用場景下會有其獨特優勢，但是對于應用場景較為挑剔，相比于歸并排序而言，目前暫未系統性地深入研究.因此本節將主要關注于歸并排序，其代表性排序架構設計包括排序網絡、基于FIFO 的排序和歸并樹3 類.通過對3 類不同排序架構的分析，可以揭示出排序設計原則在各研究工作中的應用.同時在2.4 節介紹了代表性的非歸并類加速工作，強調了其設計特點和應用場景.

2.1 排序網絡設計分析

排序網絡的優勢在于其結構規整，具備高并行且控制邏輯簡單的優勢，常用的高效排序網絡包括雙調排序和奇偶排序，如圖7 所示.排序網絡內部的比較交換模塊按固定的階段順序連接，同階段內的比較單元可以并行運行，不同階段間可以添加寄存器進行流水化，適合硬件實現.對于輸入端口為N的排序網絡，數據長度小于N時可以通過特殊數據補齊，或者進行相應架構調整，如圖7（c）所示.

圖7 排序網絡Fig.7 Sorting network

在實際應用中大多選用雙調排序網絡，雙調半排序規整的結構路徑使得其具備進一步演進優化的潛力.雖然奇偶排序網絡占用比較器數目比雙調排序網絡少,但奇偶排序不同數據通路之間的路徑延遲不均衡，需要額外添加寄存器來保證所有數據到達輸出端時的時序一致.

針對排序網絡的優化主要在于如何降低硬件資源占用率.由圖6 可以看出，排序網絡的硬件資源占用率主要集中在LUT 上，且與輸入端口數目正相關，因此排序網絡更多地被用于小數據規模的排序.為降低硬件資源占用率可以采用可重配置的方法復用單一階段以完整模擬整個雙調排序過程.

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

圖8 排序網絡優化方案Fig.8 Optimizations of sorting network

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

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

圖9 雙調排序衍生架構Fig.9 Derivative architecture of bitonic sorting

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

圖10 帶有反饋路徑的排序架構及其優化Fig.10 Sorting architecture with feedback datapath and its optimization

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

2.2 基于FIFO 的歸并排序設計分析

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

圖11 FMS 結構Fig.11 FMS structure

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

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

2.3 歸并樹設計分析

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

圖12 歸并樹及其優化Fig.12 Merge tree and its optimizations

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

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

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

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

圖13 Bonsai 架構Fig.13 The architecture of Bonsai

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

2.4 非歸并類排序設計分析

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

基數/桶排序最原始的算法原理依據單一數據位進行排序，排序時間與數據位寬相關，對于一個k位的數據，時間復雜度為O(N×k).因此，理論上當排序數據滿足k＜lbN時，使用基數排序會比歸并排序更有優勢，但由于數據分布、范圍無法預知，基數/桶排序中對于桶的劃分和每個桶內所會分配的數據量均無法確定.對于數據偏斜非常嚴重的情況，基數/桶排序將退化為按位比較的快速排序算法.基數/桶排序對于片上存儲需求較大，依賴于大規模存儲以緩解讀寫存儲開銷[29,40].

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

圖14 采樣排序Fig.14 Sample sort

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

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

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

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

3 數據庫排序加速設計

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

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

Table 3 Sort Acceleration Design of Database表3 數據庫排序加速設計

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

圖16 范圍劃分Fig.16 Range partition

除共通性問題之外，數據庫排序加速更加需要注意的是其獨特的要求，需要排序加速架構進行適應性調整優化.具體來說，存在5 個問題與挑戰：

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

2）排序衍生特有操作優化問題.如最大值/最小值（max/min）、選取前K項最值（Top-K）[54]操作和排序合并連接（sort-merge join）等，該類型操作需要對原始排序加速架構進行調整或者設計數據流式新型架構.

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

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

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

上述5 個問題與數據庫卸載引擎的設計方式是密不可分的，接下來我們將結合數據庫卸載引擎架構模型，進一步分析其機遇和挑戰.對于數據庫卸載引擎，可以劃分成查詢加速引擎、存儲架構、互聯結構、控制中心以及外設5 個部分，如圖17 所示[53].下面將從上述部分對數據庫排序加速設計的影響出發介紹排序加速架構的適應性調整優化.

圖17 數據庫卸載引擎模型Fig.17 Model of database offloading engine

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

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

圖18 Top-K 操作架構Fig.18 Architecture of Top-K operation

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

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

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

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

圖20 數據庫數據組織形式Fig.20 Data arrangement of database

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

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

圖21 DOE 數據組織形式Fig.21 Data arrangement of DOE

專用互聯結構和外設等影響排序加速的數據通路，使排序最優化模型緩解了帶寬限制因素.專用互聯結構方面，由于各操作間數據傳遞方向復雜多變，保守起見需要全連通圖拓撲設計，因此Q100 中設計了2D-網格型片上網絡，帶寬可達6.3 GBps.外設方面，基于文獻[38]中的統計結果，我們可以得到如圖22所示的設備級帶寬發展趨勢，可以看出網絡帶寬與PCIe，DRAM 帶寬之間的差距在逐漸縮小，FPGA 可以直接接入網絡傳輸，數據不需要在網絡分層和軟件棧之間復制傳輸，基于網絡接口的排序加速設計目前沒有相應的研究.

圖22 設備級帶寬發展趨勢[38]Fig.22 Bandwidth development trends at device-level[38]

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

4 未來研究方向

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

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

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

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

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

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

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

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

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

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

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

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

5 結 論

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

作者貢獻聲明：孔浩負責完成數據整理、文獻搜集并撰寫論文；盧文巖負責論文架構討論和論文修改；陳巖負責論文數據整理和指導；鄢貴海和李曉維提出指導意見并修改論文.