基于CPU-GPU的有序统计类恒虚警检测优化

火静斌,张晓滨,田 泽

(1.西安工程大学,陕西 西安 710048;2.集成电路与微系统设计航空科技重点实验室,陕西 西安 710068)

0 引 言

在雷达系统中,恒虚警率检测技术(CFAR)通过动态调整检测门限来检测背景杂波干扰下的目标。为了估计杂波功率,需要对每个雷达回波样本进行大量的计算。雷达系统需要高吞吐量和低延迟,传统的CFAR处理通常使用现场可编程门阵列(FPGA)或数字信号处理器(DSP)[1-2],但也存在一定的问题,如开发周期长、调试难度大、耗费资源等。随着GPU统一渲染架构的出现,基于CPU-GPU的异构计算体系结构开始普及,OpenCL、CUDA等开发平台简化了GPU编程难度,基于异构计算平台的GPU开发环境已广泛应用于雷达信号处理领域[3-6]。

在雷达应用中,有多种方法可以实现恒虚警检测,比如经典的单元平均恒虚警检测技术(Cell Averaging CFAR,CACFAR)、平均选大(Greatest of CFAR,GOCFAR)和平均选小恒虚警检测技术(Smallest of CFAR,SOCFAR)。但是在需要多目标或高性能的应用环境中,有序统计类恒虚警检测技术的应用范围更广[7]。与其他检测方法不同的是,OSCFAR的内部实现更为复杂,属于计算密集型方法,需要高性能计算设备。文献[8]在Tesla C1060 GPU上研究了PD雷达中CACFAR的GPU实现,通过对算法进行了优化,提高了算法的并行性,达到了一定的加速效果。文献[9]利用OpenCL在集成显卡以及中等级别产品AMD GPU实现CACFAR,但由于使用零填充方法,容易造成程序虚警。文献[10]利用积分图像算法加速了并行均值滤波算法,但需要两个内核函数上分别实现计算并行前缀和以及平均值,会产生额外的计算以及对共享内存的不必要访问。文献[11]在GPU端采用Blelloch扫描算法来对CA-CFAR求和过程进行优化,避免了重复计算,但存在的问题是数据必须是以二的指数幂格式传输。文献[12]提出的局部最大最小快速滤波是一种充分考虑数据重用的算法,可以用来解决GOCFAR、SOCFAR的数据重用,但存在边界溢出的问题。

以上都是对均值类恒虚警检测算法进行了GPU加速实现,而对OSCFAR加速的研究还比较少。文献[13]在FGPA上设计实现了可以规避排序算法的OSCFAR,但是如果需要排序值计算信噪比时不能满足系统要求。文献[14]设计了重复快速排序算法,但快速排序不适合在GPU上进行计算。文献[15]提出了具有分布式直方图的OSCFAR的计算方法,但是需要一定的计算量。文献[16]提出了基于“扫雷算法”的OSCFAR算法,适合并行计算,但是需要利用第三方工具做预处理排序。

该文的研究重点是在OSCFAR中使用GPU进行加速,提出了一种改进的OSCFAR方法,使其适用于GPU并行实现。首先,设计了一个预处理程序,对每个多普勒通道进行数据扩充。在预处理程序中,为了减少GPU处理中的分支操作,对每个多普勒通道数据进行扩充,大小为左右保护单元以及参考单元数量之和,从而优化设备计算效率。其次,设计并实现了CPU-GPU异构架构下OSCFAR的并行加速方法。根据GPU的显存大小,将原始数据按时间顺序划分为若干个子数据并传输到GPU。为了优化计算效率,预处理程序分配给CPU执行,之后OSCFAR由GPU执行。为了证明所提出方法的可行性,在雷达模拟噪声信号为瑞利噪声背景条件下,对有序统计类恒虚警检测方法进行了仿真实验。在实验中,所提出的方法消耗时间是仅在CPU上运行的OSCFAR所消耗时间的1/60,且目标信号质量并没有降低。

1 有序统计类恒虚警处理方法分析

在瑞利背景条件下,假设v(t)是单脉冲检测中某个分辨单元的一个观测值,当使用平方律检波器进行检波时,可写成如下形式:

D(v)=I2(v)+Q2(v)

(1)

其中,I(v)表示信号的同相分量,Q(v)表示信号的正交分量。在一般的杂波环境中,可以认为接收到的杂波的包络服从瑞利分布。在均匀的瑞利杂波背景条件下,单元平均方法就是利用检测单元周围的前沿滑窗和后沿滑窗中的一组独立同分布的参考单元采样的平均值来估计杂波功率水平的。有序统计类(Order Statistics)OSCFAR是采用统计手段来估计杂波水平功率。该方法和常规均值类CFAR的区别是其在多目标环境下检测性能较好,但是在杂波边缘环境和均匀环境下会存在一定的损失,如图1所示。

图1 有序统计类CFAR检测方法

数据经过平方率检波得到距离多普勒功率谱,对每个待检测单元D选取参考单元(xi(i=1,2,…,n),yj(j=1,2,…,n)),为了防止目标的能量泄露到参考单元造成杂波功率估计值较高,一般在检测单元两侧选取一定的保护单元(np)。OSCFAR算法是将待检测单元两侧参考单元(ns)拼接后进行排序,得到一个递增序列。然后取第K个有序值作为杂波水平的估计值,一般条件下K的取值和rate相关,具体计算方式为K=rate*2n。OSCFAR的虚警概率PFA与门限因子α的关系如下:

(2)

一般条件下,虚警概率PFA为固定概率值,由此计算得到门限监测因子α,检测门限T为门限监测因子与有序值K的乘积。将待检测目标单元与检测门限进行比较,如果待检测单元的功率值大,则判决为目标,否则判为杂波。

从有序统计类恒虚警检测图中可看出,均值类恒虚警检测方法CACFAR是每一个采样点需要完成一次求和运算,这样可以通过并行扫描的方式避免大量的重复运算。例如Blelloch算法是在GPU端计算扫描的方法,避免了CPU完成扫描处理时主机段与设备端之间的传输时间。而OSCFAR与CACFAR的区别在于中间的排序过程,会耗费系统大量的资源。为此,如何选择适合GPU并行的排序算法以及对完整流程的并行化设计是OSCFAR加速研究的重点。

2 基于GPU的有序统计类恒虚警检测并行化技术

脉冲多普勒雷达信号处理系统常用的算法模块包括脉冲压缩、动目标信号显示、动目标检测、恒虚警检测。雷达信号在经过前三个步骤之后可以得到大小为Np*Ns的二维矩阵,针对该矩阵进行距离维CFAR检测时,各个脉冲之间不存在联系,可以同时进行Np个脉冲的CFAR检测,因此存在数据集的并行。针对有序统计类的检测算法而言,处理主要有平方率检波、每个单元的杂波功率估计(包括窗口排序)、检测门限计算以及待检测单元的比较,都可以由GPU的多个线程完成。因此,OSCFAR具有较好的数据以及线程级别的可并行性。

2.1 有序统计类恒虚警检测的GPU实现

基于OpenCL的OSCFAR处理流程如图2所示,采用以单个脉冲为单位进行OSCFAR,单个脉冲内的平方率检波,两侧参考单元的排序,以及待检测单元的分支可以由多个线程并行实现。

图2 基于OpenCL的OSCFAR处理流程

大小为Np*Ns的数据从主机端传到设备端后,按照流程可以将算法分解为两个模块依次对应两个内核函数,第一个内核函数平方率检波主要将复数信号转化为实数信号,数据格式为实部虚部交替存储,即连续两个数据分别是信号的实部和虚部,一般采用OpenCL内建矢量数据类型表示。若采用一维寻址的方式,设置合适的workgroup大小p,则需要的workgroup数量为Np*Ns/p记为q,每个线程完成一个平方律检波计算,总的计算组织架构如图3所示。

图3 平方率检波处理流程

第二个内核函数主要用于计算杂波功率水平估计以及与实际值进行判断,若采用一维寻址的方式,设置workgroup大小,每个线程进行一个信号的杂波水平估计与判断。假设单侧参考单元大小为nr,单侧保护单元大小为np,由此可以将距离维度的数据划分为三个部分:对于前nr+np个元素来说,如果要填充左右数据的话可以从右侧取2*(nr+np)个元素对其排序后将第K个有序值作为待检测单元的估计值,对于最后nr+np个元素取其左侧2*(nr+np)个元素,中间部分的话直接从左右两侧各取nr+np个元素。将两侧数据排序取K值作为杂波功率的估计值,最后将估计值与实际值作对比确定是否为目标对象。

2.2 算法优化

优化1:数据填充。

在估计杂波功率水平时,需要将距离维度的数据划分为三个部分,即需要三个分支操作来进行各自的计算。由于GPU的设计不善于处理分支判断,因此需要将每个线程进行统一操作。采取的办法是数据扩充,扩充的方法如图4所示。如果填充数据零的话,对于均值类CFAR和有序统计类OSCFAR来说,将导致杂波功率估计值变小,从而导致检测门限变小容易造成虚警[9]。因此,可以采取的方法是将原数据做复制,不论是镜像复制还是按序复制都会对这两类数据结果产生影响较小,在实验中采用按序复制一侧的方法。

图4 数据填充方式

优化2:排序分析。

得到数据后将两侧数据合并,利用合适的排序算法得到杂波功率的估计值。采取的排序算法可以是传统的冒泡排序算法以及快速排序,由于只需要递增排序前K个元素,对于冒泡排序来说,时间复杂度可以降为O(K×N)。当数据量过大时,排序过程可能成为程序瓶颈,快速排序具有良好的执行效率可以提高性能,但由于OpenCL平台限制,GPU执行的机器代码仅包含分支和循环,一般情况下,对于函数调用来说编译器会将函数转换为内联函数,但是对于递归调用来说无法做到。因此,对于高效的快速排序无法应用到本项目场景中。

为此,解决的办法是采用双调排序。双调排序是基于Batcher定理的一种适用于数据并行的排序算法,首先需要生成一个双调序列(有一个非严格递增序列和一个非严格递减数列),然后将该序列划分为两个子序列(左边的双调序列小于右边的序列),继续对每个子序列进行划分直到序列长度为1,就可以得到单调递增的序列。

优化3:内存优化。

对于平方率检波内核函数来说,AMD系列GPU支持的最大workgroup大小为256,为此可以将交替存储的实虚数拷贝到本地内存中,减少函数对全局内存的访问,提高设备计算能力。除此之外,可以在程序中使用页锁定(Page-Locked)内存分配方式,操作系统不需要对其分页也不需要将其交换到磁盘上,可以将其一直置于物理内存中,GPU根据其物理地址直接与主机进行数据的复制与传递,可以获得更好的加速性能。

对齐访问全局内存对于AMD系列以及Nvida系列GPU来说都会提高GPU性能。本实验中,在主机端对数组数据进行手工填充比较复杂,该文采用了OpenCL引入的clEnqueueWriteBufferRect命令将主机端数据拷贝到设备端。在创建缓存时,用来确定的列数是满足对齐后所需的数据。对于一维的大小为256的workgroup来说,列数应该四舍五入到最近的256的倍数。

3 实验评估

实验中用到的GPU硬件平台分别为Intel(R) HD Graphics520和AMD Radeon R7 M370。CPU为Core(TM)i5-6200U CPU@2.30 GHz。所使用的数据是由Matlab仿真的线性调频信号,其主要参数如表1所示。

表1 模拟信号参数

3.1 优化实验结果对比

由之前的模拟数据可知,采样频率(fs)为2.0×106,雷达发射脉冲重复周期(PRT)为4.096×10-3,则单个脉冲周期的采样点数fs*PRT为8 192。脉冲数量为16,则总的采样点数为16*8 192。雷达信号在经过脉冲压缩、MTI、MTD之后可以得到大小为16*8 192的二维复数矩阵。由于存储的数据格式为实虚部交替存储,交由主机端存储时数据16*8 192*2。首先,数据在经过平方率检波内核函数时,相邻两个数据之间分别是采样点的实部与虚部,将二者的平方和存入该线程的寄存器中。其次,针对该矩阵进行距离维CFAR检测时,采用一维寻址方式,设置全局工作组大小16*8 192,由于workgroup中的work-item不存在数据共享,并未设置本地workgroup大小。处理杂波功率水平估计采用有序统计类方式,测试稳定后取三次实验结果,表2给出了CFAR在CPU和GPU上运行时间对比。

表2 CPU与GPU运行时间以及加速比

其中,Graphics520执行期间,两个内核函数(平方率检波,杂波估计与判别)分别耗费的时间为0.251 ms、99.111 ms。由表2可以看出,并行化后的恒虚警检测在GPU上有着良好的性能。经过算法优化后的OSCFAR方法实验结果如表3所示。优化后系统的执行时间较优化前缩小到原来的1/7,实验证明,该方法加速效果明显。

表3 优化前后的执行事件对比

3.2 算法优化实验结果分析

对于OSCFAR来说,优化的方面分别是将条件分支通过数据扩充解决、排序算法的合理使用和内存优化。本实验采用不同的策略在16个雷达脉冲,在每个脉冲的采样点数为8 192的条件下进行了分支与数据填充实验分析,得到的实验结果如表4所示。

表4 分支与数据填充实验分析

对于数据扩充来说会影响到两个方面,首先是在主机端(CPU)扩充了数据,对于每个雷达脉冲的8 192个采样点来说,只会在其两侧分别添加保护单元和参考单元的总数,导致数据传输时间会受到一定的影响。其次就是减少数据流分支,对于工作组中的线程执行同样的操作会对GPU执行效率产生了近5倍的性能提升,对整体的优化有着显著的提升。

除此之外,有序统计类恒虚警检测中的排序算法也会对GPU执行效率有一定影响,实验中采用了改进过的冒泡排序和双调排序来对参考单元数量进行排序,数据采用填充过的雷达信号数据,实验结果如表5所示。分析算法中存在的瓶颈,通过设计更加合理、更加具有并行性的排序算法,对估计每个待检测单元的功率值的GPU执行效率有了近1.5倍的性能提升。

表5 排序算法实验分析

对于OSCFAR中的两个内核函数都可以在内存优化方面有一定的空间,采用的方法就是减少对全局内存的访问,利用本地内存提升效率。利用页锁定机制,系统不需要进行分页也不需要置换内存,可以获得较好的加速性能。缺点就是如果数据量过大的话,一旦没有足够的物理内存供程序使用,系统性能有所下降。通过循环展开将平方率检波后的二维数据映射到OpenCL二维空间,提升计算部件的利用率。实验结果如表6所示:算法经过页锁定机制以及内存访问对齐后的性能有所提升。

表6 主存与循环展开实验分析

3.3 误差分析

图5展示了OSCFAR在CPU端和GPU端的目标检测对比结果,二者处理结果近乎一致。在处理待检测功率估计值时将CPU与GPU的数据做误差分析,得到的结果如图6所示,其绝对误差小于3×10-3,且GPU具有更好的数据精度。

图5 OSCFAR CPU与GPU处理结果

图6 CPU和GPU误差分析结果

4 结束语

提出了一种基于GPU的恒虚警检测并行处理方法,通过对原数据进行填充、采用双调排序并行化等优化策略来实现GPU加速。基于OpenCL通用异构平台的GPU加速满足了雷达信号处理高性能要求,在集成显卡以及中等级别的AMD显卡上可以达到60倍左右的加速比,本研究为后续基于国产GPU的加速积累了经验。