李大琳 陳濤

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

關(guān)鍵詞：浮點數(shù);并行排序;可重構(gòu);插入排序

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

0 引言

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

1 排序器設計

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

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

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

2 排序器實現(xiàn)

2.1 浮點數(shù)排序節(jié)點設計

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

2.2 浮點數(shù)排序器的設計

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

2.3 可重構(gòu)排序器設計

本文所設計排序器使用SystemVerilog語言實現(xiàn)，所有排序器位寬、排序器節(jié)點數(shù)定義部分均使用參數(shù)化設計，使用者可以根據(jù)實際問題的規(guī)模重新定義參數(shù)后實現(xiàn)排序器。

3 測試結(jié)果

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

4 結(jié)論

本文設計了一種基于FPGA的可重構(gòu)浮點數(shù)線性排序器，在浮點數(shù)比較環(huán)節(jié)使用了Xilinx公司系統(tǒng)的浮點數(shù)比較核，在系統(tǒng)在面積和頻率性能上都比現(xiàn)有使用浮點數(shù)減法運算的實現(xiàn)有明顯提升。

參考文獻

[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.