基于CUDA的GPS信号快速捕获

程俊仁，刘光斌，张 博

(第二炮兵工程学院303教研室，西安710025)

0 引言

以GPS为代表的扩频信号的快速捕获和实现技术一直是研究的热点。在中、低动态环境下，对GPSC/A码的捕获需要进行32颗卫星、1023个码元和至少20 kHz多普勒频率带宽的三维搜索，计算量很大。目前基于PC平台的GPS软件接收机中普遍采用基于FFT的码相位并行捕获算法［1］，然而鉴于PC平台的构架和FFT的执行效率，捕获速度不高。即便是目前国外比较高端的软件接收机Nordnav公司的R30，其冷启动捕获时间也需要4秒［2］。

近年来，一种利用图形处理器 GPU(Graphic Processing Unite，GPU)进行通用计算的技术逐步发展起来并初步应用到视频解码、金融、地质勘探和科学计算中［3］。GPU是一种高度并行化的多核处理器，它的特点是能够利用大量的处理单元进行并行计算，而 CUDA(Compute Unified Device Architecture，CUDA)则是由NVIDIA于2006年提出的利用GPU实现通用计算的编程模型。为此，本文在基于FFT的码相位并行捕获算法基础上，提出了一种利用CUDA实现PC平台GPS软件接收机L1频段C/A码信号捕获的快速实现方法，仿真数据的测试结果表明:该方法能够显著提高捕获速度，冷启动条件下，搜索全部32颗卫星只需1.653秒，为基于PC平台的GPS软件接收机的实时化提供了重要保证。

1 GPS信号捕获

由于GPS系统采用码分多址(CDMA)的扩频通讯体制，信号捕获的实质是通过本地复现信号和接收信号进行相关运算，获得卫星的伪随机码号(PRN)、伪随机码的码相位和载波多普勒频移。衡量捕获性能的主要指标是信号捕获估计出的多普勒频移和码相位的分辨率以及捕获时间。

基于FFT的码相位并行搜索算法可以在同一频点上实现1023个码相位的并行搜索［1］，其处理流程如图1所示。接收机将接收到的信号进行预处理，利用本地复现的包含载波和码的复信号与接收信号进行相关运算，求取相关峰值，根据预设的检测门限进行检测判决，最终给出粗略的码相位和多普勒频移估计值。为了提高信噪比，往往需要进行多次相干积分，并进行模值的累加(即非相干累加)。整个运算过程中，需要进行单一载波的大点数FFT运算以及多载波的循环搜索和多次相干积分，运算时间较长。

图1 基于FFT的信号捕获算法结构框图Fig.1 Block diagram of FFT based signal acquisition

2 基于CUDA的快速捕获

目前接收机的信号处理都是一种基于通道的处理方式，各通道的信号处理流程基本相同，而在同一通道内的信号捕获过程中，多载波的搜索和多毫秒的相关运算都是相对独立的过程，在数据上不存在显著的依赖关系，如果能够并行计算则可以显著减少计算时间。2006年，NVIDIA提出了GPU的通用编程模型CUDA，它的出现使得GPU真正成为了一个通用的并行数据处理设备。CUDA是一种可伸缩的并行编程模型，它专门解决大量数据的并行计算问题，它的出现使得GPS信号捕获速度的进一步提高成为可能。

2. 1 CUDA 基本构架

CUDA基于C语言扩展而来，是一种单指令多线程(SIMT)的处理模式，其最基本的运算单元是线程(Thread)，多个线程可以组成一个线程块(Block)，多个Block又可以组成一个网格(Grid)，一个网格对应着一个核函数，在这个核函数里面每个线程可以并行处理不同的数据。CUDA的主要工具是NVCC［4］，它需要配合C/C++编译器。在Windows的Visual Studio(7.0以上)环境下，通过设定组建模式，即可让Visual Studio执行NVCC。

在CUDA的架构下，一个程序分为两部分:Host程序和Device程序。Host程序是指在CPU上执行的部分，而Device程序则是在GPU上执行的部分，即“Kernel”函数。Host端将数据准备好后，通过PCI总线将数据拷贝到GPU内存中，由GPU执行Device程序，计算完成后再由Host端将数据从GPU中取回［5］，其基本执行框图如图2。

图2 CUDA程序执行框图Fig.2 Architecture of CUDA

2. 2 基于CUDA的快速捕获方法

由CUDA的处理模式可知，可以利用多个线程实现多频点的并行搜索和多毫秒的并行相关运算，在运算单元容许的情况下，甚至还可以实现多颗卫星的并行搜索。信号捕获中需要进行大量的FFT运算，这可以利用 CUDA自带的 CUFFT库来实现［6］。CUFFT库是基于麻省理工学院(MIT)提供的FFTW软件包开发而来，FFTW是由MIT计算机科学实验室超级计算技术组开发的基于PC平台的FFT算法软件包，是目前最优秀的FFT算法软件包。CUFFT库函数可以进行灵活设置，它会自动调用GPU的执行单元完成任意点数和最多可达三维的FFT运算，对于一维的FFT，最多可实现8000000个元素的变换。在计算能力为1.0的显卡上，一个线程块可以处理多达512个线程，网格各维度的最大规格为 65535［5，7］。

因此，基本公共服务不管分类如何，应强调其基本性。它是公共服务应该覆盖的最小范围。基本，即是公共程度较高、公共品的特征较强、与民生密切相关的公共服务。公共服务的基本性，一是看其正面外部性的大小；二是看其是否具有非竞争性和非排他性；三是看其是否与民生密切相关。更高层次的需求，属于一般公共服务的范畴，可以由市场机制补充提供。例如，义务教育既具有较大的正外部性、非竞争性和非排他性，又与民生密切相关，可以看作基本公共服务，而高等教育具有准公共品特征，正外部性较小，就属于一般公共服务。

利用CUDA的特点，本文对基于FFT的码相位并行捕获算法进行了改进。改进方法的参数设置如下:对单颗卫星采用1 ms的相干积分，10 ms的非相干积分，采样率是5 MHz，数字载波中心频率为1.17 MHz，考虑中低动态的载体，多普勒频移搜索空间为20 kHz，步进666.67 Hz，需要搜索31个频点。

设定FFT点数为5000，输入数据FFT的运算组数(Batch)为10，本地信号FFT的Batch为31，采用310个线程实现频域相乘的操作，IFFT运算的Batch为310个。FFT的最大操作元素个数为5000×31×10=1550000，能够满足要求。由于CUFFT库函数会自动分配线程资源，因此这些操作将最大限度地并行进行。捕获N号卫星的操作步骤如下:

对i=0 ～ 30，j=0 ～ 10，k=0 ～ 4999

Step 1 产生中心频率为1.17 MHz、频率间隔为666.67 Hz的31个中频复数载波信号;

Step 2 产生N号卫星的C/A码，与中频载波相乘并采样得到本地复信号yi(k);

Step 3 将数据拷贝到GPU，调用CUFFT库函数实现yi(k)的FFT运算得到Yi(k);

Step 4 按照采样率读取10 ms的实数输入数据，对虚部补零得到复数数据xj(k);

Step 5 将数据拷贝到GPU，调用CUFFT库函数实现xj(k)的FFT运算得到Xj(k);

Step 6 求Xj(k)的复共轭得到(k)，在GPU上实现Yi(k)和(k)的逐点相乘得到

Step 7 调用CUFFT库函数实现Mi，j(k)的IFFT 运算得到 Ri，j(k)，求模得到 ri，j(k);

Step 8 将ri，j(k)中每毫秒对应的点累加，即进行非相干累加，得到ri(k);

Step 9 将数据拷贝到CPU，计算ri(k)的极大片内，并按下式计算两者的比值

Step 10 若Ratio大于预先设定的门限值，则检测成功，rmax对应的i和k分别为多普勒频移对应的频率索引和码相位对应的采样点，否则判定为检测失败。

上述算法将以200 ns的时间分辨率给出C/A码的起始位置，以666.67 Hz的频率分辨率给出中频载波频率。由于进行了31个频点各10次相干累加的并行计算，理论上这种方法的计算速度将提高300倍以上。

3 性能测试与结果分析

为了测试上述方法的捕获性能，在VS2008下利用C语言和CUDA分别实现了两种捕获算法，并进行了对比测试。一种是传统的基于FFT的码相位并行搜索算法(传统方法)，这种方法的FFT运算采用的是MIT提供的FFTW软件包，根据需要进行了适当的修改和取舍;另一种方法是本文提出的基于CUDA的快速实现方法(改进方法)。

3. 1 实验环境设置

本文开发的两个程序运行的硬件平台为:CPU Pentium(R)D 2.6 GHz，内存2GB，显卡 NVIDIA Ge-Force GTS 250，显存512 MB，GPU的核心频率是735 MHz，流处理器的核心频率 1.836 GHz，计算能力为1.0。时间测试函数为VS2008自带的clock()函数。不同的硬件配置测试结果可能不同。

利用自行研制的GPS中频信号仿真器产生了一组静态测试数据。测试数据的基本参数为:数字载波中心频率为1.17 MHz，量化位数为1比特，采样率5 MHz，载噪比为45 dB，只仿真了4颗卫星，相应的仿真参数如表1。

表1 仿真卫星参数表Table 1 Parameters of satellites

时间测试没有把产生本地信号的时间考虑在内，因为这部分可以预先计算好存入相应的存储器。为了避免测试过程中的不确定因素的影响，两种方法分别对10 ms的输入数据进行了20次独立的捕获试验，处理时间取平均值。

3. 2 实验结果与分析

经过一段时间的运行，两种方法均正常捕获到了四颗卫星的信号，两种方法捕获的信号参数和程序运行的时间如表2。

表2 捕获结果Table 2 Results of acquisition

由表2可知，20次独立的捕获过程中，两种方法检测到的码相位和多普勒频移参数几乎相同，因此改进方法的检测性能并没有受到影响，而相比传统方法，改进方法的计算速度提高了10倍。对全部32颗卫星完成搜索的时间是1.653 s，比R30提供的冷启动捕获时间4秒还要小。

为了进一步提高计算速度，可以将32颗卫星进行并行搜索，但是按照本文的方法，FFT的操作元素个数为1550000×32=49600000，超过了CUFFT库函数中规定的一维FFT操作元素的最大范围80000000，同时还要占用大量的GPU内存，因此不可取。然而，即使是串行搜索，捕获速度已经足够快了，这正是利用CUDA进行大量数据并行计算的结果。

当然，从上述结果我们也可以看出，计算速度并非理论计算中的那样提高300倍以上，这主要是由于GPU处理特性造成的。GPU计算速度虽然比较快，但是由于显卡内存中没有缓存，因此存取时间(Latency)很长。GPU就是靠大量的线程来隐藏这种存取时间从而达到快速计算的目的。而实际上，本文程序中的线程的数量还比较小;同时，GPU与CPU之间的数据拷贝也要消耗时间。因此，在利用CUDA编程的时候，应当尽量减少数据拷贝的次数，同时还要尽可能多地利用线程资源，以提高内存存取的效率。

4 结论

本文针对基于PC平台的GPS软件接收机C/A码信号快速捕获的难题，以基于FFT的码相位并行搜索捕获算法为基础，提出了一种基于CUDA的C/A码信号快速捕获的实现方法。本方法立足于提高算法的计算效率，而非减少总共的计算量。在通用PC平台下将本方法和基于FFTW软件包实现的捕获方法进行了比较，结果表明，在保证捕获性能的前提下，捕获速度提高了10倍以上，为基于PC平台的GPS软件接收机的实时化提供了重要保证。同时，此方法不局限于伪码的结构，是一种通用的计算方法，因此对其它扩频信号的快速捕获具有较高的参考价值。

［1］ James B T.Fundamentals of global positioning systems，a software approach［M］.New York:John Wiley＆ Sons，Inc，2005:113－116.

［2］ NordNav Technologies the Galileo and GPS Software Receiver Company.The complete GNSS software receiver package［EB/OL］，2005.http://www.nordnav.com.

［3］ 吴恩华.图形处理器用于通用计算的技术，现状及其挑战［J］.软件学报，2004，15(10):1493－1504.［Wu En-hua.State of art and future challengeon general purpose computation by graphic processing unit［J］.Journal of Software，2004，15(10):1493 －1504.］

［4］ Cuda Z.NVIDIA compute unified device architecture NVCC［EB/OL］.Version2.1，2008.12.http://www.nvidia.com/cuda.csdn.cn.

［5］ Cuda Z.NVIDIA compute unified device architecture programming guide［EB/OL］.Version 2.1，2008.8.http://www.nvidia.com/cuda.csdn.cn.

［6］ Cuda Z.NVIDIA compute unified device architecture CUFFT library［EB/OL］.Version 2.1，2008.10.http://www.nvidia.com/cuda.csdn.cn.

［7］ Cuda Z.NVIDIA compute unified device architecture reference manual［EB/OL］.Version 2.0，2008.6.http://www.nvidia.com/cuda.