基于FPGA的浮點數線性排序器設計

李大琳 陳濤

摘要：本文實現了一種基于FPGA的可重構浮點數線性排序器。該排序器基于經典的插入排序算法，將插入排序算法并行化，在比較操作的實現上，采用浮點數比較核，使排序器總體性能較現有實現有明顯提升。

關鍵詞：浮點數;并行排序;可重構;插入排序

中圖分類號：TP312 文獻標識碼：A 文章編號：1007-9416（2019）11-0143-02

0 引言

排序是計算機應用領域中非常重要、研究和應用都非常廣泛的一類問題。例如，在數據處理、數據庫、數據壓縮、分布式計算、圖像處理和計算機圖形學中排序算法都有著非常廣泛的應用[1]。為了充分提升排序問題的解決效率，提升算法運行速度，研究人員除了設計出針對不同問題的各種排序算法之外，還結合排序問題的可并行性特點，結合具體處理器（CPUs，GPUs以及FPGAs）的結構特點設計出了很多并行排序算法。其中，基于FPGAs的并行排序算法在性能、功耗比上表現得最優，但是現有排序器多數為定點數排序器，且在問題規模發生變化時，排序器適應性很差[2]。本文在插入排序算法的基礎上，針對數據庫研究中存在的大量浮點數排序問題，設計出一套基于Xilinx公司的FPGAs的可重構浮點數線性排序器。

1 排序器設計

排序算法的基礎是待排序數據之間的比較。插入排序算法的基本原理是將新進數據與已有有序序列進行逐次比較，以獲得新數據在隊列中的位置，從而形成新的有序序列。本文將插入排序算法并行化，新的排序機制如圖1所示。圖中每一個節點代表一個比較/插入單元。單元的數量等于待排序數據的數量。新的待插入輸入數據被廣播到所有節點，用以和所有現有數據進行比較，并且找到新數據的正確位置。根據算法是要做升序排序或者降序排序，最右側的節點獲取最小或者最大值。待排數據從左側進入，從序列右側讀出。在這個排序操作過程中，排序操作和數據輸入操作同時進行。

以升序排序模式為例，在這種情況下，序列的最小值位于節點隊列的最右側節點。在其中任一個節點，得到一個從前序節點輸入的數據a，以及當前節點數據b。為實現升序排序，節點執行條件判斷：b≤a。新的待插入數據與所有節點中的數據進行比較。通常情況下，數據a 一般不是最大值，因此序列中的每一個節點內的數據關系可能是下面三個中的一個：

（1）c≥a： c被插入當前節點，a和其右側所有節點被向右移動。（2）c≥b：c被插入到a的右側，并且b以及其右側所有節點右移。（3）c

2 排序器實現

2.1 浮點數排序節點設計

浮點數排序節點設計如圖2所示。排序節點由浮點數比較器、多路選擇器、數據存儲寄存器和控制邏輯實現。在浮點數比較器的設計上，為了保證性能，本設計采用了Xilinx公司的浮點數比較IP核，該核可按照IEEE-754的數據標準實現32位標準浮點數和16位短浮點數比較，比較過程按浮點數格式分段進行，而不采用浮點數減法方式進行，因此在比較器構成資源使用和最終實現的最高主頻上都比現有浮點數減法方案優化很多。

2.2 浮點數排序器的設計

N個排序節點串聯構成一個排序器，N為待排序數據數量，如圖3所示。有兩個系統狀態標簽以流水線工作方式互聯所有節點。排序器通過這兩個標簽來驅動節點內的控制邏輯，以確定新數據的準確插入位置。一個標簽代表激活的節點，以進位標志（CY）的方式在節點中間傳遞。另外一個標簽（LE）反映新的待插入數據和節點當前已有數據之間的比較結果。如果新數據比當前數據大，則LE標簽復位，否者LE標簽置位。

2.3 可重構排序器設計

本文所設計排序器使用SystemVerilog語言實現，所有排序器位寬、排序器節點數定義部分均使用參數化設計，使用者可以根據實際問題的規模重新定義參數后實現排序器。

3 測試結果

本文測試環境使用xilinx公司的Zynq7020芯片，芯片內包含兩個Arm A9內核和Artex系列FPGA。試驗把運行在A9內核上的標準插入排序算法和運行在Artex系列FPGA上的并行排序算法進行比較，時間結果顯示，并行算法相對于經典算法的加速比達25倍。

4 結論

本文設計了一種基于FPGA的可重構浮點數線性排序器，在浮點數比較環節使用了Xilinx公司系統的浮點數比較核，在系統在面積和頻率性能上都比現有使用浮點數減法運算的實現有明顯提升。

參考文獻

[1] Matai J，Richmond D，Lee D，et al.Resolve：Generation of High-Performance Sorting Architectures from High-Level Synthesis[C].the 2016 ACM/SIGDA International Symposium.ACM，2016.

[2] Marcelino R，Neto，Horácio，Cardoso，Joo M P.Sorting units for FPGA-Based embedded systems[J].Ifip International Federation for Information Processing，2008（271）：11-22.