胡二猛，錢承山，張永宏，許 強(qiáng)

（南京信息工程大學(xué) 信息與控制學(xué)院，江蘇 南京 210044）

0 引言

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

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

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

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

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

圖1 排序機(jī)的硬件架構(gòu)模型

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

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

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

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

圖2 排序系統(tǒng)頂層框圖

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

表1 排序系統(tǒng)接口功能表

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

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

有限狀態(tài)機(jī)(Finite State Machine，F(xiàn)SM)是為了研究有限狀態(tài)的計算過程和某些語言類而抽象出的一種計算模型，反映從系統(tǒng)開始到當(dāng)前時刻的輸入變化的狀態(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)時，從SDRAM中地址為source_addr處開始連續(xù)讀取長度為data_length的一組數(shù)據(jù)送入排序邏輯單元中進(jìn)行排序；(3)待一組數(shù)據(jù)傳輸完畢，開始將寄存器中排序好的數(shù)據(jù)進(jìn)行壓棧輸出，直到數(shù)據(jù)全部被排出，一次完整排序完成。

圖3 排序系統(tǒng)狀態(tài)轉(zhuǎn)移圖

2.2.2 比較器

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

2.2.3 解碼器

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

2.2.4 多路選擇器

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

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

2.3 FPGA調(diào)試配置

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

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

圖4 FPGA配置部分電路圖

3 仿真實驗與分析

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

圖5 排序機(jī)仿真時序圖

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

4 結(jié)束語

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

[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].電腦知識與分析，2013(9)：2146-2149.

[3]楊繡丞，李彤，趙娜，等.計算排序算法設(shè)計與分析[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].電子技術(shù)應(yīng)用，2014，40（8）：14-16.

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

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