李大琳 陳濤
摘要:本文實(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.