0 引言

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

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

1 硬件排序機的工作原理

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

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

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

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

2.1 排序系統(tǒng)的總體設計

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

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

2.2 排序機各個子模塊的FPGA實現(xiàn)

2.2.1 有限狀態(tài)機

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

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

2.2.2 比較器

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

    always@(*)

    if(next_data>current_data)

        gt <= 1；

        else gt <= 0； 

2.2.3 解碼器

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

    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)中采用的是四選一多路器，四個數(shù)據(jù)通道分別是清零通道、上一級寄存器中數(shù)據(jù)、當前寄存器中數(shù)據(jù)以及待排序數(shù)據(jù)，根據(jù)對應解碼器的輸出選擇其中一個數(shù)據(jù)通道作為對應寄存器的輸入。

    多路選擇器關鍵部分代碼如下：

    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調試配置

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

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

3 仿真實驗與分析

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

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

4 結束語

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

參考文獻

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

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

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

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

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

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

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