李大琳 陳濤

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

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

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）11-0143-02

0 引言

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

1 排序器設(shè)計

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

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

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

2 排序器實(shí)現(xiàn)

2.1 浮點(diǎn)數(shù)排序節(jié)點(diǎn)設(shè)計

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

2.2 浮點(diǎn)數(shù)排序器的設(shè)計

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

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

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

3 測試結(jié)果

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

4 結(jié)論

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

參考文獻(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.