基于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.