基于CUDA的GPS信號快速捕獲

程俊仁，劉光斌，張 博

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

0 引言

以GPS為代表的擴頻信號的快速捕獲和實現(xiàn)技術(shù)一直是研究的熱點。在中、低動態(tài)環(huán)境下，對GPSC/A碼的捕獲需要進行32顆衛(wèi)星、1023個碼元和至少20 kHz多普勒頻率帶寬的三維搜索，計算量很大。目前基于PC平臺的GPS軟件接收機中普遍采用基于FFT的碼相位并行捕獲算法［1］，然而鑒于PC平臺的構(gòu)架和FFT的執(zhí)行效率，捕獲速度不高。即便是目前國外比較高端的軟件接收機Nordnav公司的R30，其冷啟動捕獲時間也需要4秒［2］。

近年來，一種利用圖形處理器 GPU(Graphic Processing Unite，GPU)進行通用計算的技術(shù)逐步發(fā)展起來并初步應(yīng)用到視頻解碼、金融、地質(zhì)勘探和科學(xué)計算中［3］。GPU是一種高度并行化的多核處理器，它的特點是能夠利用大量的處理單元進行并行計算，而 CUDA(Compute Unified Device Architecture，CUDA)則是由NVIDIA于2006年提出的利用GPU實現(xiàn)通用計算的編程模型。為此，本文在基于FFT的碼相位并行捕獲算法基礎(chǔ)上，提出了一種利用CUDA實現(xiàn)PC平臺GPS軟件接收機L1頻段C/A碼信號捕獲的快速實現(xiàn)方法，仿真數(shù)據(jù)的測試結(jié)果表明:該方法能夠顯著提高捕獲速度，冷啟動條件下，搜索全部32顆衛(wèi)星只需1.653秒，為基于PC平臺的GPS軟件接收機的實時化提供了重要保證。

1 GPS信號捕獲

由于GPS系統(tǒng)采用碼分多址(CDMA)的擴頻通訊體制，信號捕獲的實質(zhì)是通過本地復(fù)現(xiàn)信號和接收信號進行相關(guān)運算，獲得衛(wèi)星的偽隨機碼號(PRN)、偽隨機碼的碼相位和載波多普勒頻移。衡量捕獲性能的主要指標(biāo)是信號捕獲估計出的多普勒頻移和碼相位的分辨率以及捕獲時間。

基于FFT的碼相位并行搜索算法可以在同一頻點上實現(xiàn)1023個碼相位的并行搜索［1］，其處理流程如圖1所示。接收機將接收到的信號進行預(yù)處理，利用本地復(fù)現(xiàn)的包含載波和碼的復(fù)信號與接收信號進行相關(guān)運算，求取相關(guān)峰值，根據(jù)預(yù)設(shè)的檢測門限進行檢測判決，最終給出粗略的碼相位和多普勒頻移估計值。為了提高信噪比，往往需要進行多次相干積分，并進行模值的累加(即非相干累加)。整個運算過程中，需要進行單一載波的大點數(shù)FFT運算以及多載波的循環(huán)搜索和多次相干積分，運算時間較長。

圖1 基于FFT的信號捕獲算法結(jié)構(gòu)框圖Fig.1 Block diagram of FFT based signal acquisition

2 基于CUDA的快速捕獲

目前接收機的信號處理都是一種基于通道的處理方式，各通道的信號處理流程基本相同，而在同一通道內(nèi)的信號捕獲過程中，多載波的搜索和多毫秒的相關(guān)運算都是相對獨立的過程，在數(shù)據(jù)上不存在顯著的依賴關(guān)系，如果能夠并行計算則可以顯著減少計算時間。2006年，NVIDIA提出了GPU的通用編程模型CUDA，它的出現(xiàn)使得GPU真正成為了一個通用的并行數(shù)據(jù)處理設(shè)備。CUDA是一種可伸縮的并行編程模型，它專門解決大量數(shù)據(jù)的并行計算問題，它的出現(xiàn)使得GPS信號捕獲速度的進一步提高成為可能。

2. 1 CUDA 基本構(gòu)架

CUDA基于C語言擴展而來，是一種單指令多線程(SIMT)的處理模式，其最基本的運算單元是線程(Thread)，多個線程可以組成一個線程塊(Block)，多個Block又可以組成一個網(wǎng)格(Grid)，一個網(wǎng)格對應(yīng)著一個核函數(shù)，在這個核函數(shù)里面每個線程可以并行處理不同的數(shù)據(jù)。CUDA的主要工具是NVCC［4］，它需要配合C/C++編譯器。在Windows的Visual Studio(7.0以上)環(huán)境下，通過設(shè)定組建模式，即可讓Visual Studio執(zhí)行NVCC。

在CUDA的架構(gòu)下，一個程序分為兩部分:Host程序和Device程序。Host程序是指在CPU上執(zhí)行的部分，而Device程序則是在GPU上執(zhí)行的部分，即“Kernel”函數(shù)。Host端將數(shù)據(jù)準(zhǔn)備好后，通過PCI總線將數(shù)據(jù)拷貝到GPU內(nèi)存中，由GPU執(zhí)行Device程序，計算完成后再由Host端將數(shù)據(jù)從GPU中取回［5］，其基本執(zhí)行框圖如圖2。

圖2 CUDA程序執(zhí)行框圖Fig.2 Architecture of CUDA

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

由CUDA的處理模式可知，可以利用多個線程實現(xiàn)多頻點的并行搜索和多毫秒的并行相關(guān)運算，在運算單元容許的情況下，甚至還可以實現(xiàn)多顆衛(wèi)星的并行搜索。信號捕獲中需要進行大量的FFT運算，這可以利用 CUDA自帶的 CUFFT庫來實現(xiàn)［6］。CUFFT庫是基于麻省理工學(xué)院(MIT)提供的FFTW軟件包開發(fā)而來，F(xiàn)FTW是由MIT計算機科學(xué)實驗室超級計算技術(shù)組開發(fā)的基于PC平臺的FFT算法軟件包，是目前最優(yōu)秀的FFT算法軟件包。CUFFT庫函數(shù)可以進行靈活設(shè)置，它會自動調(diào)用GPU的執(zhí)行單元完成任意點數(shù)和最多可達(dá)三維的FFT運算，對于一維的FFT，最多可實現(xiàn)8000000個元素的變換。在計算能力為1.0的顯卡上，一個線程塊可以處理多達(dá)512個線程，網(wǎng)格各維度的最大規(guī)格為 65535［5，7］。

因此，基本公共服務(wù)不管分類如何，應(yīng)強調(diào)其基本性。它是公共服務(wù)應(yīng)該覆蓋的最小范圍?；?，即是公共程度較高、公共品的特征較強、與民生密切相關(guān)的公共服務(wù)。公共服務(wù)的基本性，一是看其正面外部性的大??；二是看其是否具有非競爭性和非排他性；三是看其是否與民生密切相關(guān)。更高層次的需求，屬于一般公共服務(wù)的范疇，可以由市場機制補充提供。例如，義務(wù)教育既具有較大的正外部性、非競爭性和非排他性，又與民生密切相關(guān)，可以看作基本公共服務(wù)，而高等教育具有準(zhǔn)公共品特征，正外部性較小，就屬于一般公共服務(wù)。

利用CUDA的特點，本文對基于FFT的碼相位并行捕獲算法進行了改進。改進方法的參數(shù)設(shè)置如下:對單顆衛(wèi)星采用1 ms的相干積分，10 ms的非相干積分，采樣率是5 MHz，數(shù)字載波中心頻率為1.17 MHz，考慮中低動態(tài)的載體，多普勒頻移搜索空間為20 kHz，步進666.67 Hz，需要搜索31個頻點。

設(shè)定FFT點數(shù)為5000，輸入數(shù)據(jù)FFT的運算組數(shù)(Batch)為10，本地信號FFT的Batch為31，采用310個線程實現(xiàn)頻域相乘的操作，IFFT運算的Batch為310個。FFT的最大操作元素個數(shù)為5000×31×10=1550000，能夠滿足要求。由于CUFFT庫函數(shù)會自動分配線程資源，因此這些操作將最大限度地并行進行。捕獲N號衛(wèi)星的操作步驟如下:

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

Step 1 產(chǎn)生中心頻率為1.17 MHz、頻率間隔為666.67 Hz的31個中頻復(fù)數(shù)載波信號;

Step 2 產(chǎn)生N號衛(wèi)星的C/A碼，與中頻載波相乘并采樣得到本地復(fù)信號yi(k);

Step 3 將數(shù)據(jù)拷貝到GPU，調(diào)用CUFFT庫函數(shù)實現(xiàn)yi(k)的FFT運算得到Y(jié)i(k);

Step 4 按照采樣率讀取10 ms的實數(shù)輸入數(shù)據(jù)，對虛部補零得到復(fù)數(shù)數(shù)據(jù)xj(k);

Step 5 將數(shù)據(jù)拷貝到GPU，調(diào)用CUFFT庫函數(shù)實現(xiàn)xj(k)的FFT運算得到Xj(k);

Step 6 求Xj(k)的復(fù)共軛得到(k)，在GPU上實現(xiàn)Yi(k)和(k)的逐點相乘得到

Step 7 調(diào)用CUFFT庫函數(shù)實現(xiàn)Mi，j(k)的IFFT 運算得到 Ri，j(k)，求模得到 ri，j(k);

Step 8 將ri，j(k)中每毫秒對應(yīng)的點累加，即進行非相干累加，得到ri(k);

Step 9 將數(shù)據(jù)拷貝到CPU，計算ri(k)的極大片內(nèi)，并按下式計算兩者的比值

Step 10 若Ratio大于預(yù)先設(shè)定的門限值，則檢測成功，rmax對應(yīng)的i和k分別為多普勒頻移對應(yīng)的頻率索引和碼相位對應(yīng)的采樣點，否則判定為檢測失敗。

上述算法將以200 ns的時間分辨率給出C/A碼的起始位置，以666.67 Hz的頻率分辨率給出中頻載波頻率。由于進行了31個頻點各10次相干累加的并行計算，理論上這種方法的計算速度將提高300倍以上。

3 性能測試與結(jié)果分析

為了測試上述方法的捕獲性能，在VS2008下利用C語言和CUDA分別實現(xiàn)了兩種捕獲算法，并進行了對比測試。一種是傳統(tǒng)的基于FFT的碼相位并行搜索算法(傳統(tǒng)方法)，這種方法的FFT運算采用的是MIT提供的FFTW軟件包，根據(jù)需要進行了適當(dāng)?shù)男薷暮腿∩?另一種方法是本文提出的基于CUDA的快速實現(xiàn)方法(改進方法)。

3. 1 實驗環(huán)境設(shè)置

本文開發(fā)的兩個程序運行的硬件平臺為:CPU Pentium(R)D 2.6 GHz，內(nèi)存2GB，顯卡 NVIDIA Ge-Force GTS 250，顯存512 MB，GPU的核心頻率是735 MHz，流處理器的核心頻率 1.836 GHz，計算能力為1.0。時間測試函數(shù)為VS2008自帶的clock()函數(shù)。不同的硬件配置測試結(jié)果可能不同。

利用自行研制的GPS中頻信號仿真器產(chǎn)生了一組靜態(tài)測試數(shù)據(jù)。測試數(shù)據(jù)的基本參數(shù)為:數(shù)字載波中心頻率為1.17 MHz，量化位數(shù)為1比特，采樣率5 MHz，載噪比為45 dB，只仿真了4顆衛(wèi)星，相應(yīng)的仿真參數(shù)如表1。

表1 仿真衛(wèi)星參數(shù)表Table 1 Parameters of satellites

時間測試沒有把產(chǎn)生本地信號的時間考慮在內(nèi)，因為這部分可以預(yù)先計算好存入相應(yīng)的存儲器。為了避免測試過程中的不確定因素的影響，兩種方法分別對10 ms的輸入數(shù)據(jù)進行了20次獨立的捕獲試驗，處理時間取平均值。

3. 2 實驗結(jié)果與分析

經(jīng)過一段時間的運行，兩種方法均正常捕獲到了四顆衛(wèi)星的信號，兩種方法捕獲的信號參數(shù)和程序運行的時間如表2。

表2 捕獲結(jié)果Table 2 Results of acquisition

由表2可知，20次獨立的捕獲過程中，兩種方法檢測到的碼相位和多普勒頻移參數(shù)幾乎相同，因此改進方法的檢測性能并沒有受到影響，而相比傳統(tǒng)方法，改進方法的計算速度提高了10倍。對全部32顆衛(wèi)星完成搜索的時間是1.653 s，比R30提供的冷啟動捕獲時間4秒還要小。

為了進一步提高計算速度，可以將32顆衛(wèi)星進行并行搜索，但是按照本文的方法，F(xiàn)FT的操作元素個數(shù)為1550000×32=49600000，超過了CUFFT庫函數(shù)中規(guī)定的一維FFT操作元素的最大范圍80000000，同時還要占用大量的GPU內(nèi)存，因此不可取。然而，即使是串行搜索，捕獲速度已經(jīng)足夠快了，這正是利用CUDA進行大量數(shù)據(jù)并行計算的結(jié)果。

當(dāng)然，從上述結(jié)果我們也可以看出，計算速度并非理論計算中的那樣提高300倍以上，這主要是由于GPU處理特性造成的。GPU計算速度雖然比較快，但是由于顯卡內(nèi)存中沒有緩存，因此存取時間(Latency)很長。GPU就是靠大量的線程來隱藏這種存取時間從而達(dá)到快速計算的目的。而實際上，本文程序中的線程的數(shù)量還比較小;同時，GPU與CPU之間的數(shù)據(jù)拷貝也要消耗時間。因此，在利用CUDA編程的時候，應(yīng)當(dāng)盡量減少數(shù)據(jù)拷貝的次數(shù)，同時還要盡可能多地利用線程資源，以提高內(nèi)存存取的效率。

4 結(jié)論

本文針對基于PC平臺的GPS軟件接收機C/A碼信號快速捕獲的難題，以基于FFT的碼相位并行搜索捕獲算法為基礎(chǔ)，提出了一種基于CUDA的C/A碼信號快速捕獲的實現(xiàn)方法。本方法立足于提高算法的計算效率，而非減少總共的計算量。在通用PC平臺下將本方法和基于FFTW軟件包實現(xiàn)的捕獲方法進行了比較，結(jié)果表明，在保證捕獲性能的前提下，捕獲速度提高了10倍以上，為基于PC平臺的GPS軟件接收機的實時化提供了重要保證。同時，此方法不局限于偽碼的結(jié)構(gòu)，是一種通用的計算方法，因此對其它擴頻信號的快速捕獲具有較高的參考價值。

［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］ 吳恩華.圖形處理器用于通用計算的技術(shù)，現(xiàn)狀及其挑戰(zhàn)［J］.軟件學(xué)報，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.