基于FPGA的堆排序算法实现与改进

2015-10-30 07:20龚晓峰
制造业自动化 2015年8期
关键词:上位排序状态

张 鹏,龚晓峰

(四川大学 电气信息学院,成都 610065)

0 引言

在实际应用中,为了计算数字信号的调制参数,通常需要将ADC采样后的数据通过FPGA处理后上传给上位机进行调制参数的计算。但是由于受到FPGA与上位机接口传输速率的制约,要将大量IQ数据上传至上位机将消耗大量的时间;同时,IQ数据上传至上位机后要经过大量的计算处理后才能得到调制参数的结果。这大大降低了使用效率,同时给上位机添加了大量的计算负担。为此,将调制参数的计算下放至FPGA,仅仅将调制参数的计算结果上传至上位机,如此便可克服上述的两个难题。

在FPGA上实现调制参数的计算中,对解调后数据的排序是其中的一个难点。目前在FPGA上实现排序的算法较少,且大多排序的点数较少,无法评估大量样本排序时FPGA所占用的资源与排序的时间[1]。

本文针对FPGA设计出一种流水线式的堆排序方法,通过时序优化与modelsim仿真验证,最终实现将2048点排序的时间控制在2ms以内。这一结果与原ARM上位机处理速度相当,从而达到了预期设计目的。

1 堆排序的原理

堆排序是利用堆积树这种数据结构所设计出的一种排序算法,可以利用数组的特点快速定位指定索引的元素。

堆排序包括建堆和排序两部分。堆可以定义为一棵二叉树,包括大根堆(父节点大于等于其左右子节点)与小根堆(父节点小于等于其左右子节点)两种,可以用于从小到大排序与从大到小排序两种方式。

排序部分是将堆顶的数与堆尾的数互换位置,然后将堆顶的数排除,将原来n个数的堆变为n-1个数的新堆,再将新的堆重复建堆与排序的过程直至完成排序[2]。

2 FPGA方案设计

2.1 FPGA与ARM方案对比

原始调制参数设计方案与改进后设计方案的对比图如图1所示。

图1 两种方案的对比图

如图1所示,如果采用原始的设计方案,当FPGA完成数字下变频处理后,需要上传2048组IQ数据,即4096个16位数据至上位机。由于接口速率限制,传输效率较低,占用了大量时间。原始IQ数据上传至上位机后仍需在上位机上进行调制参数的计算,这将占用大量的上位机CPU资源。

而改进后的方案,由于调制参数在FPGA内计算完成,因此只需上传调制参数的结果,即3个16位数据(调制参数,正向调制参数以及负向调制参数)至上位机,这大大节省了数据上传的时间。同时,由于在FPGA内已经完成参数调制计算,节约了上位机的CPU资源,让上位机只做控制与显示功能。

2.2 FPGA总体结构的设计

当使用2048组IQ数据进行调制参数计算时,先需要对信号进行解调,得到2048个16位有符号的解调数据后进行排序。

进入排序模块后,首先要对2048个数据进行缓存;其次从RAM中读出数据进行建堆处理后重新存入RAM中;再次对已建好的大根堆进行排序后重新存入RAM中;最后将排好序的数依次读出。FPGA总体结构图如图2所示。

图2 FPGA总体结构设计

如图2所示,总体结构包含了DATA_INPUT数据输入模块,BUILD_HEAP建堆模块,HEAP_SORT堆排序模块,DATA_OUTPUT数据输出模块以及一个RAM使用权控制模块RAM_CONTROL。

2.3 建堆模块的设计

建堆模块是堆排序的核心模块,该模块将缓存在RAM中的2048个数据建立为一个大根堆。其处理的思路如图3所示。

图3 建堆模块信号流程图

图4 建堆模块状态转移图

建堆模块的实现是由一个状态机来完成,其包括IDLE等待状态;PRE预处理状态;WAIT等待数据状态;COMPARE比较状态;LYC缓存状态;WRITE写入状态;HANDLE处理状态以及FINISH完成状态。该模块的状态转移图以及各状态完成的功能如下:

各状态完成的功能:

IDLE:等待状态。

PRE:预处理状态,设置RAM的读取地址。

WAIT:等待数据从RAM中读出,需要4个周期。

COMPARE:依次读出该数据的父根,比较该数与父根的大小关系,直到找到比该数大的父根或读取到最顶层父根。

LYC:缓存比较结果,为后续分类处理写入RAM模块做好准备。

WRITE:将建堆好的数重新写入RAM中。

HANDLE:修改记录地址,记录已有多少个数完成了建堆。

FINISH:操作build_ready信号并清零寄存器。

2.4 堆排序模块的设计

堆排序模块是建立在建堆模块基础之上的。根据堆排序的原理,将堆顶与堆尾数据交换;将该数两子节点取较大的数与该数比较,如果大于子节点中较大的数则表示重新建堆完成,否则继续向下查找直至大于其子节点或没有子节点为止[3]。

堆排序模块的实现同样是由一个状态机来完成,其包括IDLE等待状态;PRE预处理状态;WAIT等待数据状态;HANDLE处理状态;JUDGE跳转状态;OVER结束状态以及FINISH完成状态。该模块的状态转移图以及各状态完成的功能如下:

各状态完成的功能:

IDLE:等待状态。

PRE:预处理状态,设置RAM的读取地址,并将最高地址值与记录地址值交换。

WAIT:读取记录地址的两个子根。

HANDLE:比较两个子根的大小,并记录大根的值与地址值。

图5 堆排序模块状态转移图

JUDGE:比较大根值与待建堆数的大小,根据结果跳转状态。

OVER:将排好序的数依次重新写入RAM中。

FINISH:操作heap_ready信号并清零寄存器。

3 仿真结果

根据上文所述,在modelsim中仿真建堆过程与排序过程如图6所示。

图6 两核心模块的仿真结果

如图6(a)所示,BUILD_HEAP模块取其中一个点进行建堆验证,如第87个点的建堆,依次查找其父节点43,21,10,4,1,0;发现地址为10的父节点已经大于地址为87的点,将新的顺序重新写入RAM中。

如图6(b)所示,HEAP_SORT模块中首先交换堆顶与堆尾的数据(如交换0地址与1481地址的数据),然后依次找出较大子节点先缓存在寄存器中,当找到一个小于堆顶的数则重新将建堆的数据写入RAM中。

通过图6可以看出,建堆与排序两个模块运行情况与预期完全相同,完成了堆排序。

4 验证平台

Altera公司的Cyclone III系列芯片为主流低成本FPGA,因此我们选取EP3C40F484C8作为测试芯片[3]。而ARM处理器模块选用Cortex-A8处理器,与FPGA进行堆排序比较,以验证方案的可行性。

5 验证结果与对比

5.1 FPGA堆排序

首先在MATLAB中产生一组随机数,通过modelsim将数据读入,验证FPGA排序,在100MHz晶振频率下所需时间如图7所示。

图7 FPGA堆排序所需时间

如图7所示,当完成数据缓存DATA_INPUT模块后开始计时,开始进入建堆模块与堆排序模块,当数据输出模块DATA_OUTPUT开始读出数据停止计时;这段时间即为堆排序所需时间。从图中可以看出,对于一组2048点的随机数堆排序时间控制在2ms以内。

5.2 FPGA与ARM堆排序时间结果对比

堆排序为一种不定时排序,排序时间与输入数据原始的顺序有关。对此,验证3种不同输入数据顺序,分别为2048点随机数组,由大到小的2048点数组以及由小到大的2048点数组,测试结果如表1所示。

表1 FPGA与ARM时间对比

从表1可以看出,FPGA堆排序与ARM堆排序时间相当,这是由于为了节约FPGA逻辑资源而采用流水线的工作模式;但如前文所述,此方案大大降低了数据上传所需时间以及ARM上位机的计算负担,达到了预期结果。

6 结束语

本文针对FPGA与上位机接口传输速率受限问题以及上位机沉重的计算负担,将调制参数的计算下放至FPGA中进行处理,极大的解决了上述问题。而针对FPGA调制参数计算中的排序处理,采用了2048点的流水线式堆排序,排序时间与主流ARM处理器相当,排序结果正常;证明了该方案的可行性,达到了克服FPGA与上位机接口传输速率受限问题,以及减小上位机计算负担的目的。

[1] 吴彦宏,陈相宁.QoS保障机制中的FPGA堆排序实现[J].计算机工程, 2009,35(12):223-225

[2] 黎佩南.一种快速排序算法的实现及其应用[J].电讯技术,2012,52(2):225-229.

[3] 吴彦宏,陈相宁.QoS中堆排序的脉动阵列结构在FPGA上的实现[J].科学技术与工程, 2008,8(19):5435-5438.

猜你喜欢
上位排序状态
作者简介
恐怖排序
状态联想
节日排序
要攻城略地关键要有好筹码,这匹水产动保“黑马”如何能迅速上位?
特斯拉 风云之老阿姨上位
生命的另一种状态
基于ZigBee和VC上位机的教室智能监测管理系统
坚持是成功前的状态