基于FPGA的串并集合排序在雷达系统中的应用
摘要:基于FPGA硬件技术,以资源和时间相结合的思路,提出了一种串并结合的比较排序算法。该算法通过对数据的分时并行比较,计算出每个数据在排序中的位置实现数据排序。该算法可在较短的时间内实现数字序列的排序,通过实验证明,资源消耗少,实时性号,通用性强。
关键词:排序;FPGA;并行;串行
在雷达抗干扰处理以及空时二维处理过程中数据排序将必不可免,在传统的DSP、CPU等常规软件排序已经不能够满足雷达系统实时性要求,使用 FPGA排序的趋势将势不可当。FPGA由于具有较高的并行处理能力,目前已成为雷达阵列信号处理中的主流处理器件。计算耗费的时间和消耗的硬件资源成为 处理的主要矛盾,如何解决这个矛盾,本人将提出解决方案。
1 算法描述与分析
排序就是将数据元素的一个任意序列,重新排列成一个按关键字有序的序列。各种传统串行排序算法如冒泡,大多都是以两两之间顺序比较为基础,不能满足 实时性要求。如果将传统的串行排序在FPGA中进行分段串行排序再排序,可以减少排序时间,但却大大增加设计难度。本文提出基于并行比较思路,通过将逻辑 比较结果求和,用此和值确定排序结果的位置,从而达到实现排序结果的目的。
假设待排序数据元素个数为N,全并行比较就是在同一时刻将N个数两两比较,再在下一时刻进行累加求和以确定排序结果。这样需要耗费N*N个比较器,如果元素个数较多,将耗费大量逻辑资源。本算法采用N个比较器,用N倍时间实现比较。算法如上图所示。
不同的比较器将有不同的比较结果输出,下表列出了4种比较器输出结果形式。
2 工程实现
排序算法在FPGA内进行,整个实现过程如下图。使用verilog语言设计,做到模块化、参数化,以适应不同数量的排序以及各自逻辑资源的控制,主要有以下几步:
1)将流水线上的待排序的Ⅳ个数据存储到RAM中,同时对相等值数量的RAM写零;
2)读取N个赋给N个变量准备比较;
3)读取数据和N个变量同时比较;
4)将比较结果累加求和;
5)将和值作为地址读取此数据的个数,将此个数和累加和相加写到排序结果RAM中,同时将个数加1写入相等值数量的RAM中。
相等值数量RAM主要处理待排序数据流有过个相同数值大小的数据排序的情况。
读取N个赋给N个变量准备比较需要N个时钟周期,比较需要N个时钟周期,多级累加需要3*N个时钟周期(N≤512),相同数值排序需要3*N个时钟周期,合计需要8*N个时钟周期。
3 仿真与验证
本算法Verilog代码以及IP核模块的新建基于Xilinxvp690,功能级仿真在Modsim中完成。图3是待排序数据流截图,待排序数据 是从20到319的300个递增数据,图4是图3输入数据的从小到大的排序结果,其中m_data_h是是排序后原先数据的序号,m_data_l是排序 后从小到大的结果;为了验证相同数值的排序情况,将上述待排序数据的第2、39个数改成和第1个数相同,即20,再排序,其结果如图5所示,圆圈标出了相 同数据及相同数据的排序结果。
4 算法在工程应用中的性能分析
通过实际建立工程,综合、仿真分析分别得出128点、256点以及512点排序,分别使用全并行算法、串行(冒泡)算法和本文串并结合的算法得到的 逻辑资源使用情况以及运算时钟周期。从表中可以看出,全并行算法速度最快,但数据点数翻倍时消耗的资源消耗平方级翻倍,256点排序已经超出了芯片的范 围;串行冒泡算法消耗的资源较少,但数据点数翻倍时消耗的时间却是平方级翻倍;只有本文提出的算法消耗的资源和时钟周期都能接收,具有可行性意义。
采用240 MHz时钟,512点排序,只需要8μs。
5 结束语
排序在雷达信号处理过程中只是其中的一个功能,这要求我们逻辑资源不能消耗太多,而雷达的实时性要求又要求我们必须快速的完成排序。从上述论述可 知,单纯的串行和并行排序都不能满足要求,只有本文这种基于FPGA技术的串并行结合处理排序算法才能够满足实际工程要求,达到了实时排序的效果。该算法 具有通用性,可以应用到各种数据快速排序运算领域。
- 重温经典排序思想--C语言常用排序全解 (12-08)
- 用VC++类实现快速排序(并输出过程)(12-01)
- 快速排序与二分查找程序(12-01)
- 比较型排序算法总结(12-01)
- 快速排序+二分查找与哈希表(11-28)
- 实验二:排序、加法(80C51单片机汇编语言编程)(11-23)