基于分数阶傅里叶变换的水下航行器LFM回波检测算法的GPU优化实现

詹 飞,马晓川,吴永清,王 磊,杨 力

(1.中国科学院声学研究所,北京 100190; 2.中国科学院大学,北京 100049)

0 引 言

现代主动声呐系统常采用大时间带宽积的线性调频(Linear Frequency Modulated，LFM)信号[1-2]来提高对水下目标速度和距离的估计精度。LFM信号带宽或脉宽增加会带来信号多普勒容限的变化，传统单通道匹配滤波处理方法由于未考虑多普勒效应的影响，会导致系统检测性能的损失。由于LFM信号在分数阶傅里叶变换(Fractional Fourier Transform，FRFT)域的强能量聚集特性[3]，FRFT已广泛应用于LFM信号的检测与估计[4-6]。在主动声呐系统水下目标探测方面，利用FRFT可提升低信噪比环境[7]和强混响背景[8-9]下系统的检测性能，实现对LFM回波信号的检测与参数估计，进而获得目标距离与速度的有效估计信息。但理论计算表明相同条件下FRFT算法的计算复杂度是单副本匹配滤波方法的数百倍，这限制了算法的应用环境，尤其是在具有强实时性处理要求的无人水下航行器(Unmanned Underwater Vehicle，UUV)平台上的应用。传统基于数字信号处理器(Digital Signal Processor，DSP)的UUV信号处理系统受航行器体积、重量和功耗等的约束，系统规模和运算能力无法大幅提升，导致FRFT方法的实现难以满足UUV平台的实时处理要求。

近年来，具有众核处理架构、高存储器带宽以及强大运算能力的图形处理器(Graphics Processing Unit，GPU)在雷达和声呐领域得到了广泛的应用。与传统实现方案相比，GPU实现方案通常可获得数倍至数百倍的性能加速[10-12]。在UUV平台信号处理系统设计方面，文献[13]研究表明嵌入式GPU平台比传统DSP平台更有优势，能满足UUV探测系统低功耗和高实时性的应用需求。

本文首先介绍了基于FRFT的LFM回波检测算法实现流程，分析了算法的计算复杂度。随后通过优化算法的数据处理流程和设计算法的GPU映射框架，降低了算法计算复杂度，并使算法可以在GPU上高效并行实现。最后利用UUV平台湖上实验数据对GPU优化实现方案进行了测试。

1 算法理论分析

1.1 数据处理流程

基于FRFT算法的LFM回波检测流程如图1所示。假设UUV平台发射脉宽为Δt、起始频率为fl、调频斜率为m0的LFM脉冲信号，平台与目标相对径向速度为vd。图1中GPU端主要实现对接收回波按窗(处理窗宽T≥Δt，系统采样率fs，处理窗宽N=Tfs)执行多方向波束形成、以变换阶数p为变量的FRFT，以及对归一化结果的峰值搜索等过程。执行FRFT运算前可根据搜索目标速度范围确定理论最佳变换阶数p的范围，公式如下：

(1)

式中η≈1+2vd/c为目标多普勒压缩因子，上式中p和η均表示为向量形式。FRFT的实现采用离散采样型FRFT快速算法[14]，公式为

(2)

(3)

(4)

结合处理窗编号即可计算出目标回波时延，从而得到目标距离估计。

图1 基于FRFT的LFM回波检测流程

根据变换阶数的独立性，所有变换阶数的FRFT运算可并行执行。在此基础上，本文将经过数据处理流程优化后的回波检测算法分为以下几个步骤：

(2)C_MUL1步骤：插值后的信号y与LFM信号1进行时域乘法运算得

(5)

(3)C_CONV步骤：将g与LFM信号2进行卷积运算。将时域卷积转换到频域相乘，结果为

(6)

(7)

(8)

1.2 计算复杂度分析

经过数据处理流程优化后各步骤的计算复杂度公式如表1所示。式中M为基阵阵元数，N为一帧数据长度(处理窗宽)，为利用FFT快速实现，N通常取2的整数次幂，卷积步骤中FFT运算的信号最小长度为16N。NB为执行波束形成的波束数量，NBW为工作频带内频域子带数量，NP为变换阶数p的数量，Om和Oa分别表示复数乘法和复数加法所需的浮点运算次数，并且有Om=6，Oa=2。当M=32，N=8192，NBW=768，NB=21，NP=81时各步骤计算复杂度见表1。

UUV平台信号处理系统对回波数据进行采集和处理时，为保证在单个处理窗内获得完整目标回波，一般要求采样数据按照50%重叠，并且处理窗宽为两倍发射信号脉宽。为满足实时性要求，系统对单窗数据的处理时间应小于半窗数据的更新时间N/(2fs)。处理窗宽为8192点时，数据更新时间约120 ms。实际测试结果显示，在UUV平台嵌入式GPU处理系统中执行16 N点批处理FFT运算的计算吞吐量约80 GFlops。C_CONV步骤中FFT的计算复杂度为18.95 GFloats，运算时间约237 ms，无法满足UUV平台主动声呐系统的采集数据更新时间要求，因此实际应用时需要适当减少波束数量NB或变换阶数数量NP。

表1 FRFT算法各步骤计算复杂度

2 算法的GPU优化实现

2.1 数据处理流程优化

算法部分步骤涉及前后补零操作，但补零方式不适合采用大数据块拷贝方式高效实现。此外，数据的重复利用率也较低，导致访存时间开销极大限制了并行程序性能。为降低算法计算复杂度，使算法易于高效并行实现，本文对处理流程进行了优化，包括以下几个方面：

(1)图2(a)和2(b)分别给出了基于频域DFT的宽带波束形成和基于FFT的两倍插值步骤的实现过程。波束形成输出时域数据需要经过Hilbert变换后，才能进行FRFT运算。将波束形成和两倍插值步骤合并为BF_IN步骤，省略将频域波束加权数据通过IFFT运算转换为时域数据的过程，直接将频域数据及其变换形式写入对应的频点位置，再执行IFFT运算，即可得到两倍插值后的采样数据解析形式，如图2(c)所示。

图2 BF_IN步骤实现流程

图3给出该步骤优化前后计算复杂度的变化趋势。该步骤的计算复杂度随波束数量NB的增加而线性增加。当NB=3时，优化前计算复杂度约0.036 GFloats，优化后计算复杂度约0.024 GFloats，计算复杂度降低约33%。当NB=21时，优化前计算复杂度约0.152 GFloats，优化后计算复杂度约0.069 GFloats，计算复杂度降低约54.6%。随着波束数量的增加，计算复杂度显著降低。

图3 优化前后BF_IN步骤计算复杂度变化

(2)由于CPU和GPU端的数据传输速率较慢，为精简数据传输过程中的冗余操作，提升程序执行效率，可预先将部分数据写入硬盘文件。在系统主程序初始化时将文件导入系统内存，保证GPU程序执行时可直接访问所需数据。分析回波检测算法的实现流程，首先根据波束方向和工作频带范围，生成宽带常规波束形成的波束加权向量，存储到硬盘文件。另外，根据FRFT变换阶数范围，生成LFM信号1时域数据以及LFM信号2频域数据，存储到硬盘文件。在程序初始化时完成加权向量文件和LFM信号的读取操作。

图4给出了优化前后算法总计算复杂度的变化趋势，算法的总计算复杂度随波束数量NB和变换阶数数量NP的增加而线性增加。当NB=3,NP=81时，优化前算法的计算复杂度约为8.47 GFloats，优化后算法的计算复杂度约为5.68 GFloats，计算复杂度降低约33%。

图4 优化前后算法总的计算复杂度变化

2.2 算法的GPU映射框架

本文采用NVIDIA公司统一计算设备架构(CUDA)支持的Unified Memory编程模型，用于简化内存管理。表2给出了LFM回波检测算法的CUDA实现流程。不同变换阶数的FRFT运算的独立性使算法具备了数据级并行的特点，适合于在GPU上并行实现。在此基础上，本文设计了变换阶数p在0.5≤|p|≤1.5范围内时算法的GPU映射框架，如图5所示。

图5 LFM回波检测算法的GPU映射框架

根据图1给出的回波检测流程，在GPU端实现宽带波束形成、FRFT运算，以及对归一化结果的峰值搜索等步骤，在CPU端实现门限判别和目标参数计算步骤。GPU端的实现主要包括FFT、IFFT以及向量元素对应相乘运算。其中FFT和IFFT步骤利用CUDA cuFFT库实现，SEARCH步骤利用CUDA cuBLAS库实现。向量元素对应相乘运算过程通过设计CUDA核函数实现。核函数线程块维度的设计遵循硬件资源利用率最大化的原则，计算所需数据也按照SoA方式在内存中排列以实现线程的合并访存[13]。

3 实例测试

3.1 测试参数

测试平台软硬件参数如表3所示，为方便验证算法优化效果，可先在桌面级GPU平台上对算法的实现方案进行不断优化，再将并行程序直接移植到嵌入式GPU平台进行测试即可。GPU映射框架中四个核函数都是向量元素点乘运算，将线程块设置为一维，程块维度分别为128、256、256、256。

表2 LFM回波检测算法实现流程

测试数据选用2015年冬季UUV平台在千岛湖某水域实验记录的LFM脉冲回波数据。实验过程中UUV运动速度恒定，模拟点目标与UUV平台深度相同，初始目标方位为θb=(-7°,0°)，目标距离r0=1750 m，目标速度为vt=-2 m/s。

表3 测试平台参数

UUV信号处理系统设计工作频带内频点数NBW=768，数据处理帧长度N=8192，并按照50%数据重叠方式处理数据。通过性能预估波束数量超过3时，嵌入式GPU平台处理无法满足实时性要求。因此，设置最大波束数量为NB=3，检测速度范围为-4～4 m/s，速度间隔为0.1 m/s，则执行FRFT的变换阶数p的数量NP=81。

3.2 实时性测试

表4给出了NB=3,NP=81条件下处理一窗数据时几种方案执行时间。在桌面级平台上，与CPU实现方案相比，GPU方案能获得超过9倍的性能加速。对于计算复杂度较低的步骤如BF_IN步骤，GPU方案仅获得约2.33倍性能加速。加速效果不明显，原因为核函数的启动具有较大而相对固定的时间开销，当计算任务的计算复杂度较低时，核函数启动时间开销占比较大且不可忽略。另外，C_CONV步骤的计算复杂度约5.6 GFloats，GPU方案实现该步骤的计算吞吐量约243 GFlops，获得约10倍性能加速，这充分体现了GPU在处理大规模并行计算任务时的优势。将GPU并行程序移植到嵌入式平台上，执行时间约89 ms，小于UUV平台半窗采集数据的更新时间，满足实时性需求。

表4 两种平台三种实现方案对比

3.3 湖试数据测试

利用GPU连续处理单次实验航行任务中28 ping共546窗数据，每窗数据处理时间如图7所示。图中显示在嵌入式GPU平台上，处理所有窗数据的时间始终小于半窗数据的更新时间，能够满足UUV数据处理的实时性要求，表明FRFT算法可以应用于以嵌入式GPU平台为处理核心的UUV声呐信号处理系统。

图7 所有窗数据处理时间

4 结 语

针对FRFT方法因计算复杂度高而无法满足UUV平台实时处理要求的问题，本文提出采用GPU，通过优化LFM回波检测算法处理流程和设计算法的GPU映射框架，使算法的计算复杂度降低约33%，并使算法可在GPU上高效并行实现。湖上实验数据测试结果表明，嵌入式GPU方案处理一窗LFM回波数据的时间始终小于半窗数据更新时间，满足了UUV数据处理的实时性要求。因此，FRFT方法可以应用于以嵌入式GPU平台为处理核心的UUV声呐信号处理系统。

下一步将深入研究如何进一步减小离散FRFT算法的计算复杂度，从而可在更多波束方向上实现对更大速度范围水下目标的有效探测。