0 引言

    排序是計(jì)算機(jī)程序設(shè)計(jì)中的一個(gè)重要操作，它的作用是將一個(gè)無(wú)序的數(shù)列按照其中的某些關(guān)鍵字，遞增或者遞減地排成一個(gè)有序數(shù)列。排序在計(jì)算機(jī)圖形學(xué)、計(jì)算機(jī)輔助設(shè)計(jì)、機(jī)器人、數(shù)字信號(hào)處理、模式識(shí)別等領(lǐng)域應(yīng)用十分廣泛,在以上領(lǐng)域的數(shù)據(jù)處理時(shí)，程序排序算法占據(jù)了很大的比重^[1]。排序算法曾被評(píng)為對(duì)科學(xué)和工程計(jì)算的研究與實(shí)踐影響最大的十大問題之一，因此，排序算法既有廣泛的應(yīng)用價(jià)值，又有深刻的理論意義^[2]。排序是一個(gè)高度復(fù)雜、耗時(shí)和頻繁的運(yùn)算，其頻繁程度不亞于基本的算術(shù)運(yùn)算和邏輯運(yùn)算，后兩者運(yùn)算在計(jì)算機(jī)中分別由算術(shù)運(yùn)算部件和邏輯運(yùn)算部件完成，但是沒有專門的部件完成排序算法^[3]。

    目前，在數(shù)字信號(hào)和圖像處理等實(shí)時(shí)性要求比較高的場(chǎng)合，利用軟件實(shí)現(xiàn)排序算法很難滿足需求，相比之下，硬件排序機(jī)不僅排序效率高，而且占用CPU資源少^[4]。例如：在2014巴西世界杯上第一次采用了門線技術(shù)和3D回放技術(shù)，這些技術(shù)是利用FPGA構(gòu)造硬件加速器實(shí)現(xiàn)的。在硬件加速器中，必然要利用邏輯電路構(gòu)造高效率的硬件排序機(jī)，以滿足實(shí)時(shí)性要求。 

1 硬件排序機(jī)的工作原理

    硬件排序機(jī)采用直接插入排序法，其基本思想是：每次將待排序序列的第N個(gè)數(shù)據(jù)元素的關(guān)鍵碼與前面已排好序的N-1、N-2、N-3、…、2、1數(shù)據(jù)元素的關(guān)鍵碼進(jìn)行并行比較，只需一個(gè)時(shí)鐘周期即可找到對(duì)應(yīng)插入位置，排在后面的數(shù)據(jù)元素順序后移，直到全部數(shù)據(jù)排好順序。由于升序和降序排序原理相同，本文選擇降序來(lái)進(jìn)行設(shè)計(jì)。假設(shè)一次對(duì)N個(gè)數(shù)據(jù)進(jìn)行排序，得到如圖1所示的硬件架構(gòu)模型。硬件排序機(jī)由一個(gè)狀態(tài)機(jī)、N個(gè)多路選擇、一個(gè)長(zhǎng)度為N的寄存器組、N個(gè)比較器以及一個(gè)N位解碼器組成。

    排序機(jī)的排序過程如下：待排序數(shù)據(jù)以串行方式進(jìn)入數(shù)據(jù)總線，N個(gè)比較器同時(shí)與總線上數(shù)據(jù)進(jìn)行比較，產(chǎn)生N個(gè)比較碼，解碼器對(duì)N個(gè)比較碼進(jìn)行解碼產(chǎn)生N個(gè)控制信號(hào)，控制信號(hào)送至對(duì)應(yīng)的多路選擇器控制信號(hào)輸入端,多路選擇器根據(jù)控制信號(hào)選擇不同的數(shù)據(jù)通道，將對(duì)應(yīng)數(shù)據(jù)存放在寄存器組中。待一組數(shù)據(jù)在寄存器組中排序完成，通過壓棧方式將數(shù)據(jù)從寄存器組中順序壓出，直至所有數(shù)據(jù)全部被壓出。根據(jù)硬件架構(gòu)模型，給出了排序的數(shù)學(xué)模型：

    上式中的R_i為寄存器，data為待排序數(shù)據(jù)。

2 排序系統(tǒng)的FPGA實(shí)現(xiàn)

2.1 排序系統(tǒng)的總體設(shè)計(jì)

    排序系統(tǒng)由排序機(jī)和動(dòng)態(tài)存儲(chǔ)器兩部分組成，如圖2所示。動(dòng)態(tài)存儲(chǔ)器用來(lái)存放待排序和已經(jīng)排好序的數(shù)據(jù)。排序機(jī)和動(dòng)態(tài)存儲(chǔ)器之間采用 Avalon接口協(xié)議，它是一種主從式傳輸協(xié)議，數(shù)據(jù)傳輸過程無(wú)需復(fù)雜的握手/應(yīng)答機(jī)制^[5，6]。

    排序系統(tǒng)共有7個(gè)外部接口，功能介紹如表1所示。

2.2 排序機(jī)各個(gè)子模塊的FPGA實(shí)現(xiàn)

2.2.1 有限狀態(tài)機(jī)

    有限狀態(tài)機(jī)(Finite State Machine，F(xiàn)SM)是為了研究有限狀態(tài)的計(jì)算過程和某些語(yǔ)言類而抽象出的一種計(jì)算模型，反映從系統(tǒng)開始到當(dāng)前時(shí)刻的輸入變化的狀態(tài)^[7]。

    圖3所示是系統(tǒng)的排序狀態(tài)轉(zhuǎn)移圖，描述了系統(tǒng)在接收到CPU指令后進(jìn)行排序的過程。具體過程如下：(1)系統(tǒng)上電復(fù)位后，當(dāng)狀態(tài)機(jī)處于空閑狀態(tài)，一旦接收到CPU的排序命令后，進(jìn)行自身初始化；(2)初始化完畢，狀態(tài)機(jī)接管SDRAM的控制權(quán)，在從機(jī)SDRAM處于空閑狀態(tài)時(shí)，從SDRAM中地址為source_addr處開始連續(xù)讀取長(zhǎng)度為data_length的一組數(shù)據(jù)送入排序邏輯單元中進(jìn)行排序；(3)待一組數(shù)據(jù)傳輸完畢，開始將寄存器中排序好的數(shù)據(jù)進(jìn)行壓棧輸出，直到數(shù)據(jù)全部被排出，一次完整排序完成。

2.2.2 比較器

    系統(tǒng)中采用兩路比較器，是將待排序的新數(shù)據(jù)與對(duì)應(yīng)寄存器中的數(shù)據(jù)進(jìn)行比較，產(chǎn)生一個(gè)比較結(jié)果（0或者1）作為解碼器的輸入。比較器關(guān)鍵部分代碼如下：

    always@(*)

    if(next_data>current_data)

        gt <= 1；

        else gt <= 0； 

2.2.3 解碼器

    解碼器的作用是根據(jù)當(dāng)前對(duì)應(yīng)比較器的輸出以及上一級(jí)比較器的輸出產(chǎn)生一個(gè)控制信號(hào)，控制對(duì)應(yīng)多路選擇器進(jìn)行數(shù)據(jù)通道選擇。解碼器一共輸出四種控制信號(hào)，分別是清零、移入上級(jí)寄存器中數(shù)據(jù)、保持當(dāng)前數(shù)據(jù)和插入新數(shù)據(jù)。解碼器關(guān)鍵部分代碼如下：

    always@(*) begin    

    if(clr) 

        mux_sel <= 2′b11；

    else if (previous_gt==1)

        mux_sel <= 2′b01；

    else if(previous_gt==0 && current_gt==0)

        mux_sel <= 2′b00；

    else if(previous_gt==0 && current_gt==1)

        mux_sel <= 2′b10；

    else

        mux_sel <= 2′b00；

    end

2.2.4 多路選擇器

    系統(tǒng)中采用的是四選一多路器，四個(gè)數(shù)據(jù)通道分別是清零通道、上一級(jí)寄存器中數(shù)據(jù)、當(dāng)前寄存器中數(shù)據(jù)以及待排序數(shù)據(jù)，根據(jù)對(duì)應(yīng)解碼器的輸出選擇其中一個(gè)數(shù)據(jù)通道作為對(duì)應(yīng)寄存器的輸入。

    多路選擇器關(guān)鍵部分代碼如下：

    always@(posedge clk)

    if(rst)buffer <= 8′d0；

    else if(en)

        case (mux_sel)

        2′b00 : buffer <= current_data；

        2′b01 : buffer <= previous_data；

        2′b10 : buffer <= next_data；

        2′b11 : buffer <= 8'd0；

        endcase

2.3 FPGA調(diào)試配置

    系統(tǒng)選用基于SRAM工藝的的FPGA芯片屬于易揮發(fā)性器件，即掉電后數(shù)據(jù)丟失，因此需要在每次上電時(shí)將網(wǎng)表加載到SDRAM中，為此Altera設(shè)計(jì)了專門用于自動(dòng)加載的配置芯片。將網(wǎng)表加載到配置芯片的過程稱為配置，將網(wǎng)表加載到FPGA的過程稱為編程。配置和編程在FPGA開發(fā)過程中是必不可少的，通常情況會(huì)專門預(yù)留兩個(gè)接口用于配置和編程。

    圖4給出了FPGA配置部分電路圖，與傳統(tǒng)FPGA配置電路不同，本系統(tǒng)沒有預(yù)留單獨(dú)用于配置和編程的接口，而是僅用了一個(gè)JTAG接口來(lái)實(shí)現(xiàn)配置和編程。在配置模式下,FPGA內(nèi)部會(huì)自動(dòng)調(diào)用一個(gè)軟核(Serial Flash Loader)將網(wǎng)表下載到EPCS64I16N芯片；在編程模式下，網(wǎng)表直接被下載到FPGA內(nèi)部SDRAM中。采用這種配置電路，不僅可以提高資源利用率，而且還減少了印制電路板的尺寸。

3 仿真實(shí)驗(yàn)與分析

    為了驗(yàn)證硬件排序系統(tǒng)的可行性，基于Modelsim軟件進(jìn)行仿真驗(yàn)證。本次實(shí)驗(yàn)選用Cyclone IV EP4CE10-F17C8系列FPGA芯片，主頻為50 MHz。實(shí)驗(yàn)參數(shù)設(shè)定如下：data_length=1，source_addr=10，target_addr=300。圖5給出了排序機(jī)仿真波形圖，在5 330 ns時(shí)刻排序機(jī)被啟動(dòng)，一組亂序數(shù)據(jù)進(jìn)入排序邏輯單元開始排序，在5 530 ns時(shí)刻數(shù)據(jù)輸入完成，此時(shí)數(shù)據(jù)已經(jīng)在寄存器組中完成降序排序。為了排出寄存器組中的數(shù)據(jù)，在5 550 ns時(shí)刻開始?jí)撼鲆粋€(gè)最大數(shù)255將寄存器組中數(shù)據(jù)壓出，在5 730 ns時(shí)刻排序完成。

    從圖5中可以看出，對(duì)10個(gè)數(shù)據(jù)排序共耗400 ns，排序效率高。數(shù)據(jù)傳輸過程采用SISO方式，數(shù)據(jù)傳輸與排序同時(shí)進(jìn)行。在排序過程中，排序機(jī)僅僅和SDRAM之間通過狀態(tài)機(jī)進(jìn)行數(shù)據(jù)傳遞,與CPU之間沒有數(shù)據(jù)傳遞，降低了CPU的使用率。

4 結(jié)束語(yǔ)

    本文提出一種基于FPGA的硬件排序系統(tǒng)，并完成排序機(jī)的硬件架構(gòu)設(shè)計(jì)，通過仿真證實(shí)硬件排序系統(tǒng)具有排序效率高、占據(jù)CPU資源少等特點(diǎn)，彌補(bǔ)了軟件排序的不足，解決了實(shí)時(shí)性要求較高場(chǎng)合的排序問題。

參考文獻(xiàn)

[1] CORMEN T H，LEISERSON C E，RIVEST R L.Introduce to Algori_thms[M].2nd ed.The MIT Press，2001.

[2] 吳偉娜，孫世鵬，楊風(fēng)，等.常用排序算法的比較與分析[J].電腦知識(shí)與分析，2013(9)：2146-2149.

[3] 楊繡丞，李彤，趙娜，等.計(jì)算排序算法設(shè)計(jì)與分析[J].計(jì)算機(jī)應(yīng)用研究，2014，31(3)：658-695.

[4] 呂偉新，李清清，婁俊嶺.FPGA比較矩陣排序法及其在中值濾波器中的應(yīng)用[J].電子器件，2012，35(1)：34-38.

[5] 胡強(qiáng).FPGA與通用處理器同步數(shù)據(jù)傳輸接口的設(shè)計(jì)[J].電子技術(shù)應(yīng)用，2014，40（8）：14-16.

[6] 楊鑫，徐偉俊，陳先勇，等.Avalone總線最新接口標(biāo)準(zhǔn)綜述[J].中國(guó)集成電路，2007,16(11)：24-29．

[7] 孫宏旭，邢薇，陶林.基于有限狀態(tài)機(jī)的模型轉(zhuǎn)換方法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2012，22(2)：10-17.