程俊仁，劉光斌，張 博

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

0 引言

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

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

1 GPS信號(hào)捕獲

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

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

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

2 基于CUDA的快速捕獲

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

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

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

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

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

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

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

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

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

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

對(duì)i=0 ～ 30，j=0 ～ 10，k=0 ～ 4999

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

利用自行研制的GPS中頻信號(hào)仿真器產(chǎn)生了一組靜態(tài)測(cè)試數(shù)據(jù)。測(cè)試數(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

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

3. 2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

4 結(jié)論

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

［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ì)算的技術(shù)，現(xiàn)狀及其挑戰(zhàn)［J］.軟件學(xué)報(bào)，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.