文献标识码： A
DOI：10.16157/j.issn.0258-7998.2015.12.009
中文引用格式： 胡二猛，钱承山，张永宏，等. 基于FPGA的硬件排序系统设计[J].电子技术应用，2015，41(12)：39-41.
英文引用格式： Hu Ermeng，Qian Chengshan，Zhang Yonghong，et al. Hardware sorting system design based on FPGA[J].Application of Electronic Technique，2015，41(12)：39-41.
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个控制信号，控制信号送至对应的多路选择器控制信号输入端,多路选择器根据控制信号选择不同的数据通道，将对应数据存放在寄存器组中。待一组数据在寄存器组中排序完成，通过压栈方式将数据从寄存器组中顺序压出，直至所有数据全部被压出。根据硬件架构模型，给出了排序的数学模型：
上式中的Ri为寄存器，data为待排序数据。
2 排序系统的FPGA实现
2.1 排序系统的总体设计
排序系统由排序机和动态存储器两部分组成，如图2所示。动态存储器用来存放待排序和已经排好序的数据。排序机和动态存储器之间采用 Avalon接口协议，它是一种主从式传输协议，数据传输过程无需复杂的握手/应答机制[5，6]。
排序系统共有7个外部接口，功能介绍如表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)待一组数据传输完毕，开始将寄存器中排序好的数据进行压栈输出，直到数据全部被排出，一次完整排序完成。
2.2.2 比较器
系统中采用两路比较器，是将待排序的新数据与对应寄存器中的数据进行比较，产生一个比较结果（0或者1）作为解码器的输入。比较器关键部分代码如下：
always@(*)
if(next_data>current_data)
gt <= 1；
else gt <= 0；
2.2.3 解码器
解码器的作用是根据当前对应比较器的输出以及上一级比较器的输出产生一个控制信号，控制对应多路选择器进行数据通道选择。解码器一共输出四种控制信号，分别是清零、移入上级寄存器中数据、保持当前数据和插入新数据。解码器关键部分代码如下：
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 多路选择器
系统中采用的是四选一多路器，四个数据通道分别是清零通道、上一级寄存器中数据、当前寄存器中数据以及待排序数据，根据对应解码器的输出选择其中一个数据通道作为对应寄存器的输入。
多路选择器关键部分代码如下：
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调试配置
系统选用基于SRAM工艺的的FPGA芯片属于易挥发性器件，即掉电后数据丢失，因此需要在每次上电时将网表加载到SDRAM中，为此Altera设计了专门用于自动加载的配置芯片。将网表加载到配置芯片的过程称为配置，将网表加载到FPGA的过程称为编程。配置和编程在FPGA开发过程中是必不可少的，通常情况会专门预留两个接口用于配置和编程。
图4给出了FPGA配置部分电路图，与传统FPGA配置电路不同，本系统没有预留单独用于配置和编程的接口，而是仅用了一个JTAG接口来实现配置和编程。在配置模式下,FPGA内部会自动调用一个软核(Serial Flash Loader)将网表下载到EPCS64I16N芯片；在编程模式下，网表直接被下载到FPGA内部SDRAM中。采用这种配置电路，不仅可以提高资源利用率，而且还减少了印制电路板的尺寸。
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中可以看出，对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.