基于FPGA的硬件排序系統設計

胡二猛，錢承山，張永宏，許 強

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

0 引言

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

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

1 硬件排序機的工作原理

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

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

圖1 排序機的硬件架構模型

上式中的Ri為寄存器，data為待排序數據。

2 排序系統的FPGA實現

2.1 排序系統的總體設計

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

圖2 排序系統頂層框圖

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

表1 排序系統接口功能表

2.2 排序機各個子模塊的FPGA實現

2.2.1 有限狀態機

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

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

圖3 排序系統狀態轉移圖

2.2.2 比較器

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

2.2.3 解碼器

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

2.2.4 多路選擇器

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

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

2.3 FPGA調試配置

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

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

圖4 FPGA配置部分電路圖

3 仿真實驗與分析

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

圖5 排序機仿真時序圖

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

4 結束語

本文提出一種基于FPGA的硬件排序系統，并完成排序機的硬件架構設計，通過仿真證實硬件排序系統具有排序效率高、占據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與通用處理器同步數據傳輸接口的設計[J].電子技術應用，2014，40（8）：14-16.

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

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