王可東，李鴻田，侯紹東，高 悅

（1.北京航空航天大學(xué)宇航學(xué)院，北京100191；2.工業(yè)和信息化部電信規(guī)劃研究院，北京100191）

0 引 言

GPS接收機(jī)的信號(hào)捕獲是一種并行處理過(guò)程，其中各通道和每個(gè)通道的各頻點(diǎn)均可并行獨(dú)立進(jìn)行，以提高捕獲速度，因此，并行捕獲算法基于FPGA實(shí)現(xiàn)的居多［1－2]。圖形處理單元（GPU）近年來(lái)在神經(jīng)網(wǎng)絡(luò)、模糊系統(tǒng)、元胞自動(dòng)機(jī)、粒子群優(yōu)化算法和蟻群優(yōu)化等通用計(jì)算方面得到了深入研究和一定程度的應(yīng)用，證明了GPU在并行計(jì)算方面的優(yōu)異性能［4]。文獻(xiàn)［5]探討了基于GPU實(shí)現(xiàn)并行快速捕獲的一種方法，其中一個(gè)通道內(nèi)各頻點(diǎn)的捕獲是并行的，而各通道是串行處理的，捕獲32個(gè)PRN的時(shí)間縮短為使用CPU時(shí)的1／16。

在文獻(xiàn)［5]的基礎(chǔ)上實(shí)現(xiàn)各通道的并行處理可以進(jìn)一步提高捕獲速度。因此，提出了一種各通道和各頻點(diǎn)均使用GPU并行運(yùn)算的快速捕獲方案，并初步分析了GPU與FPGA進(jìn)行并行計(jì)算的應(yīng)用對(duì)比。試驗(yàn)結(jié)果表明：在保證捕獲精度的條件下，與基于CPU的運(yùn)算方案相比，本文捕獲方案的捕獲時(shí)間是基于CPU的1／60，捕獲速度提升顯著。

1 FFT并行捕獲算法

GPS系統(tǒng)采用碼分多址（CDMA）的擴(kuò)頻通訊技術(shù)，所有衛(wèi)星信號(hào)使用相同的中心頻率，被不同擴(kuò)頻碼調(diào)制。信號(hào)捕獲的實(shí)質(zhì)是通過(guò)本地復(fù)現(xiàn)碼信號(hào)和載波信號(hào)，與輸入信號(hào)進(jìn)行相關(guān)運(yùn)算，獲得衛(wèi)星的偽隨機(jī)碼的碼相位和載波多普勒頻移，因此，GPS信號(hào)捕獲是一種二維搜索過(guò)程。衡量捕獲性能的主要指標(biāo)是多普勒頻移捕獲精度、碼相位的分辨率和捕獲時(shí)間等。

FFT并行捕獲算法可以在同一頻點(diǎn)上實(shí)現(xiàn)1023個(gè)碼相位的并行搜索，在運(yùn)算能力足夠的情況下，具有快速運(yùn)算的特點(diǎn)。如圖1所示為FFT并行處理算法的一般流程［6－7]：

圖1 FFT捕獲算法的原理

1）將中頻數(shù)字信號(hào)分別與本地載波發(fā)生器輸出的同相和正交信號(hào)相乘，剝離載波信號(hào)，獲得了一個(gè)復(fù)信號(hào)；

2）對(duì)復(fù)信號(hào)進(jìn)行FFT運(yùn)算。同時(shí)，對(duì)本地偽碼發(fā)生器輸出的偽碼采樣信號(hào)做FFT運(yùn)算，取其共軛值；

3）將復(fù)信號(hào)的FFT結(jié)果與偽碼采樣信號(hào)FFT的共軛結(jié)果相乘，對(duì)乘積結(jié)果做IFFT，對(duì)IFFT的結(jié)果取模。

4）如果IFFT模的峰值超過(guò)了門(mén)限值，則認(rèn)為捕獲成功，尖峰值對(duì)應(yīng)的位置即為偽碼相位，此時(shí)的載波頻率值就認(rèn)為是信號(hào)的載波頻率。如果峰值沒(méi)有超過(guò)門(mén)限值，則重設(shè)本地載波發(fā)生器的頻率值，重復(fù)以上步驟。

整個(gè)運(yùn)算過(guò)程中，需要進(jìn)行單一載波的大點(diǎn)數(shù)FFT運(yùn)算以及多載波的循環(huán)搜索，要求處理器的并行計(jì)算能力強(qiáng)，否則會(huì)由于計(jì)算資源消耗過(guò)大而導(dǎo)致計(jì)算時(shí)長(zhǎng)增加。

1 FFT并行捕獲算法的GPU實(shí)現(xiàn)方案設(shè)計(jì)

2006年NVIDIA公司推出了GPU的通用編程模型CUDA，CUDA的出現(xiàn)簡(jiǎn)化了GPU的開(kāi)發(fā)流程，由于CUDA是基于C語(yǔ)言進(jìn)行程序開(kāi)發(fā)的，不需要了解復(fù)雜圖形編程語(yǔ)言即可進(jìn)行GPU的通用計(jì)算編程。因此，本文將基于CUDA進(jìn)行FFT并行捕獲算法的實(shí)現(xiàn)。在進(jìn)行方案設(shè)計(jì)之前，先與同樣具有很強(qiáng)并行計(jì)算能力的FPGA對(duì)比，分析基于GPU進(jìn)行并行捕獲的可行性和優(yōu)勢(shì)。

1.1 使用GPU完成快速并行捕獲的可行性

GPU與FPGA都適合于實(shí)現(xiàn)并行運(yùn)算，但二者的應(yīng)用方式還是有一定的差異，簡(jiǎn)單對(duì)比如下：

1）開(kāi)發(fā)語(yǔ)言：GPU使用C語(yǔ)言進(jìn)行開(kāi)發(fā)，F(xiàn)PGA使用VHDL和Verilog等描述性語(yǔ)言開(kāi)發(fā)。對(duì)熟悉軟件開(kāi)發(fā)的人員來(lái)說(shuō)，不需要學(xué)習(xí)新的編程語(yǔ)言，有利于降低GPU的開(kāi)發(fā)難度；

2）功耗：GPU的功耗與具體型號(hào)有關(guān)，在本設(shè)計(jì)中使用的顯卡型號(hào)是GeForce9500GT，其總功耗約為30W，其使用的GPU芯片功耗與之相當(dāng)。FPGA的功耗與所使用的片內(nèi)資源有關(guān)，使用的資源越多功耗也越大，不過(guò)，一般要低于GPU的功耗，例如文獻(xiàn)［8]使用Altera公司的EP3S70F484C2芯片的功耗約為15W；

3）體積：GPU 的體積略小于FPGA，Ge－Force9500GT顯卡芯片的尺寸是12mm2，而EP3S70F484C2芯片的尺寸是23mm2；

4）成本：本設(shè)計(jì)中使用的GeForce9500GT顯卡的價(jià)格約為500元。由于FFT并行捕獲運(yùn)算需要消耗較多的計(jì)算資源，需要使用高端的FPGA芯片，價(jià)格較高，如單片EP3S70F484C2芯片的價(jià)格超過(guò)1000元。

綜上所述，在開(kāi)發(fā)難度、體積和成本等方面GPU有一定的優(yōu)勢(shì)，F(xiàn)PGA在功耗方面有一定的節(jié)省，不過(guò)，要是應(yīng)用多片F(xiàn)PGA芯片進(jìn)行捕獲時(shí)，還要考慮綜合功耗。

1.2 基于GPU的并行捕獲方法

在基于FFT的快速捕獲算法中，大量數(shù)據(jù)的FFT耗費(fèi)了大量時(shí)間，一些減少FFT計(jì)算數(shù)據(jù)的捕獲算法，可以加快捕獲的速度，但要以犧牲碼的分辨率為代價(jià)［10]。由于各通道各頻點(diǎn)捕獲的相對(duì)獨(dú)立性，可以使用GPU進(jìn)行并行運(yùn)算，加速FFT運(yùn)算過(guò)程［11]，在不降低碼相位分辨率的情況下減少捕獲時(shí)間。

CUDA提供了一個(gè)CUFFT運(yùn)算庫(kù)，可以高效地并行完成多個(gè)一維FFT運(yùn)算，最多可以實(shí)現(xiàn)800萬(wàn)個(gè)點(diǎn)的FFT運(yùn)算。文中GPS中頻信號(hào)的采樣頻率為5.714 285MHz，中心頻率為1.405 396 8MHz，捕獲搜索帶寬為14kHz，使用FFT快速捕獲的方法分別處理兩個(gè)連續(xù)的1ms數(shù)據(jù)，選取其中信噪比較好的數(shù)據(jù)完成峰值的確定，以消除導(dǎo)航電文跳變的影響。其中，1ms數(shù)據(jù)有5714個(gè)采樣點(diǎn)，通過(guò)補(bǔ)零，使用8 192點(diǎn)的FFT運(yùn)算；采用500Hz的頻率步進(jìn)，每顆衛(wèi)星有29個(gè)頻點(diǎn)；在冷啟動(dòng)時(shí)要搜索32個(gè)PRN衛(wèi)星。因此，一次并行運(yùn)算的FFT點(diǎn)數(shù)是7 602 176，小于800萬(wàn)，滿足CUFFT庫(kù)的使用要求。

具體捕獲流程如下：

1）使用不同頻點(diǎn)的載波信號(hào)，分別對(duì)32個(gè)PRN衛(wèi)星的中頻信號(hào)進(jìn)行解調(diào)。將32個(gè)不同衛(wèi)星的CA碼采樣序列，按頻點(diǎn)數(shù)量擴(kuò)充，按順序存儲(chǔ)在一塊內(nèi)存里，如圖2和3所示；

圖2 解調(diào)后中頻數(shù)據(jù)的存儲(chǔ)順序

2）申請(qǐng)3個(gè)顯存塊，顯存1用于接收內(nèi)存塊1中的調(diào)制中頻信號(hào)，顯存2用于接收內(nèi)存塊2中的本地CA碼采樣序列，顯存3用于存儲(chǔ)運(yùn)算結(jié)果；

圖3 本地碼的存儲(chǔ)方式

3）啟動(dòng)GPU完成中頻調(diào)制序列的FFT運(yùn)算，運(yùn)算結(jié)果仍保留在顯存1，將FFT運(yùn)算結(jié)果保留在原位的方法可以節(jié)約GPU的運(yùn)算資源；

4）啟動(dòng)GPU完成本地碼采樣序列的FFT運(yùn)算，運(yùn)算結(jié)果保留在原位；

5）利用GPU完成兩個(gè)長(zhǎng)序列相乘，將本地碼的FFT運(yùn)算結(jié)果取共軛后與輸入中頻序列的FFT運(yùn)算結(jié)果相乘，進(jìn)行IFFT后將乘積序列存入顯存3；

6）顯存3的運(yùn)算結(jié)果拷貝到主機(jī)內(nèi)存，釋放GPU的運(yùn)算資源；

7）使用同樣的方法處理第二個(gè)1ms的數(shù)據(jù)，將顯存中的數(shù)據(jù)拷貝到內(nèi)存；

8）經(jīng)過(guò)以上的步驟已經(jīng)將32個(gè)PRN和29個(gè)頻點(diǎn)的兩個(gè)連續(xù)1ms的峰值信息數(shù)據(jù)存入了內(nèi)存。比較找出兩個(gè)連續(xù)1ms中信噪比較高的數(shù)據(jù)，完成碼相位的確定，流程如圖4所示。

2 捕獲方案的試驗(yàn)驗(yàn)證

2.1 試驗(yàn)條件

1）硬件環(huán)境：CPU是Intel?CoreTM2Quad芯片，主頻為2GHz；顯卡型號(hào)是 GeForce 9500GT，顯存為512MB；內(nèi)存為2GB；

2）軟件環(huán)境：32位的 Windows?7操作系統(tǒng)，軟件開(kāi)發(fā)環(huán)境為微軟公司的VS2008，還利用了NVIDIA公司提供的CUDA Driver、CUDA Toolkit和CUDA SDK；

3）實(shí)驗(yàn)數(shù)據(jù)：使用GP2010采集的真實(shí)中頻數(shù)據(jù)，采樣頻率為5.714 285MHz，中心頻率為1.405 396 8MHz.

2.2 試驗(yàn)結(jié)果與分析

分別基于CPU和GPU完成32個(gè)PRN衛(wèi)星和29個(gè)頻點(diǎn)的搜索，捕獲結(jié)果和運(yùn)行時(shí)間如表1所示，其中GPU代碼運(yùn)行時(shí)間是使用NAVIDA提供的專用計(jì)時(shí)API測(cè)定的，CPU的運(yùn)行時(shí)間是使用MFC提供的計(jì)時(shí)器函數(shù)測(cè)定的。

圖4 碼相位的查找方法

如表1所示，在GPU和CPU中完成的算法是相同的，對(duì)PRN和碼相位的確定結(jié)果完全一致。但是，完成以上的捕獲過(guò)程，基于CPU的代碼需要約3min的時(shí)間，而基于GPU加速后的代碼只需要約3s的時(shí)間，即基于GPU的運(yùn)算速度大大提升了。

表1 捕獲結(jié)果

使用GPU運(yùn)算過(guò)程中保存的峰值繪制PRN和頻點(diǎn)二維搜索的結(jié)果如圖5所示，圖中坐標(biāo)X表示捕獲到衛(wèi)星的PRN；Y表示捕獲到衛(wèi)星的頻點(diǎn)編號(hào)；Z表示捕獲峰值的大小。由圖5可知，與表1相對(duì)應(yīng)的衛(wèi)星都存在明顯的峰值，證明了PRN捕獲結(jié)果的正確性。

圖5 二維搜索的結(jié)果

由于使用的是5.714 285MHz的采樣頻率，1 ms有5 714個(gè)采樣點(diǎn)，在使用FFT運(yùn)算時(shí)，將采樣點(diǎn)補(bǔ)零到8 192點(diǎn)，而表1中的捕獲到的碼相位都不大于5 714，可初步斷定捕獲結(jié)果的正確性。為進(jìn)一步分析捕獲結(jié)果的正確性，繪制了PRN 31的第15個(gè)頻點(diǎn)的峰值序列，如圖6所示。其中，在4 768點(diǎn)處出現(xiàn)的峰值遠(yuǎn)大于其他位置的，符合CA碼的自相關(guān)特性，進(jìn)一步證明了CA碼相位捕獲結(jié)果的正確性。

圖6 PRN 31衛(wèi)星的碼相位

搜索32個(gè)PRN衛(wèi)星的29個(gè)頻點(diǎn)的過(guò)程中，GPU使用928個(gè)線程完成了CPU用單一線程完成的大規(guī)模FFT運(yùn)算，忽略尋找峰值等次要時(shí)間因素的影響，理論上捕獲使用的時(shí)間約是CPU的1／900，但實(shí)際上GPU的捕獲使用的時(shí)間約是CPU代碼的1／60.導(dǎo)致這種差距的兩個(gè)主要因素包括：

1）GPU是多運(yùn)算核心的處理器，在核心數(shù)量上比CPU有很大優(yōu)勢(shì)，但是就單獨(dú)一個(gè)運(yùn)算核心而言，運(yùn)算能力不如CPU［11]；

2）基于CUDA開(kāi)發(fā)的GPU程序，必須由內(nèi)存拷貝到GPU的顯存，才能使用GPU加速，這個(gè)過(guò)程耗費(fèi)了一定的時(shí)間［11]。因此，基于GPU開(kāi)發(fā)代碼時(shí)，如果要最大程度地發(fā)揮GPU并行運(yùn)算的優(yōu)勢(shì)，則應(yīng)盡可能讓GPU一次處理更多的數(shù)據(jù)和運(yùn)行更多的線程。

與文獻(xiàn)［5]相比，該算法的運(yùn)行時(shí)間是CPU的1／60，捕獲時(shí)間更少，這主要是因?yàn)樵撍惴ǖ膶?shí)現(xiàn)不僅對(duì)各頻點(diǎn)進(jìn)行了并行計(jì)算，而且對(duì)各PRN衛(wèi)星也進(jìn)行了并行計(jì)算，充分發(fā)揮了GPU適合于進(jìn)行大規(guī)模并行運(yùn)算的特點(diǎn)，運(yùn)行速度更快。

3 結(jié) 論

為了減少GPS接收機(jī)冷啟動(dòng)的時(shí)間，結(jié)合GPS信號(hào)捕獲的并行運(yùn)算特點(diǎn)和GPU快速并行運(yùn)算能力的優(yōu)勢(shì)，提出了一種基于GPU的并行捕獲C／A碼的方案，對(duì)各通道和各頻點(diǎn)均進(jìn)行并行計(jì)算，以最大程度地提高捕獲速度。通過(guò)真實(shí)的中頻數(shù)據(jù)試驗(yàn)驗(yàn)證表明：

1）由于GPS各通道和各頻點(diǎn)的捕獲都是相互獨(dú)立的過(guò)程，使用GPU實(shí)現(xiàn)各通道和各頻點(diǎn)的并行捕獲與基于CPU實(shí)現(xiàn)的串行捕獲方案的捕獲結(jié)果是相同的；

2）基于GPU的并行捕獲方案完成一次冷啟動(dòng)的時(shí)間遠(yuǎn)遠(yuǎn)小于基于CPU的捕獲方案。在相同的條件下驗(yàn)證，基于GPU的方案耗時(shí)0.3029s，而基于CPU的方案耗時(shí)18.6723s，捕獲時(shí)間縮短為原來(lái)的1／60；

3）由于采用了各通道和各頻點(diǎn)均進(jìn)行并行計(jì)算的GPU實(shí)施方案，與文獻(xiàn)［4]的只對(duì)各通道進(jìn)行并行捕獲的GPU實(shí)施方案相比，運(yùn)行時(shí)間進(jìn)一步縮短，更充分地發(fā)揮了GPU的并行運(yùn)算優(yōu)勢(shì)；

4）使用GPU的捕獲方案減少的冷啟動(dòng)時(shí)間沒(méi)有達(dá)到理論值。為了充分的發(fā)揮GPU的并行運(yùn)算優(yōu)勢(shì)，使用GPU設(shè)計(jì)捕獲方案應(yīng)盡可能讓GPU一次處理更多的數(shù)據(jù)。

［1]陳熙源，湯新華，祝雪芬.GPS軟件接收機(jī)捕獲算法的FPGA 仿真［J].東南大學(xué)報(bào)，2009，39（2）：26－30.

［2]趙慷慨，汪 峰，李金海.基于FPGA高動(dòng)態(tài)GPS快速捕獲協(xié)處理器設(shè)計(jì)實(shí)現(xiàn)［J].微電子學(xué)與計(jì)算機(jī)，2010，27（2）：39－44.

［3]鄭海東，王明江，王進(jìn)祥，等 .一種AMR語(yǔ)言編碼器的VLSI設(shè)計(jì)及FPGA的實(shí)現(xiàn)［J].微電子學(xué)與計(jì)算機(jī)，2010，27（2）：39－44.

［4]LANGDON W B.Graphics processing units and genetic programming：An overview［J].Soft Comput，2011，15（8）：1657－1669.

［5]XU Shi－ming，LIN Hai－xiang，XUE wei.Sparse matrix－vector multiplication optimizations based on matrix bandwidth reduction using NVIDIA CUDA［C]∥9th International Symposium on Distributed Computing and Applications to Business，Engineering and Science，Hong Kong，China，August 10－12，2010：609－614.

［6]程俊仁，劉光武，張 博.基于CUDA的GPS信號(hào)快速捕獲 ［J].宇航學(xué)報(bào)，2010，31（10）：2408－2410.

［7]VAN NEE D J R，GOENEN A J R M.New fast GPS code－acquisition technique using FFT［J].Electronics Letters，1991，27（17）：158－160.

［8]JIANG Yi，ZHANG Shu－fang，HU Qing，et al.A new FFT－based acquisition algorithm for GPS signals［C]∥International Workshop on Education Technology and Training and International Workshop on Geoscience and Remote Sensing，Shanghai，China，December 21－22，2008：416－419.

［9]XU Bao－wen，CAI Ti－jing.C／A code of GPS software receiver fast acquisition based on FPGA［C]∥International Conference on Electric Information and Control Engineering，China，April 15－17，2011：4030－4033.

［10]O’Driscoll C，Murphy C C.Performance analysis of an FFT based fast acquisition GPS receiver［C]∥Institute of Navigation，2005National Technical Meeting.San Diego，CA，United states，January 24－25，2005：1014－1024.

［11]BEER D，VEN ORMODT R，DI CESARE D，et al.Accelerating batched 1D－FFT with a CUDA－capable computer：Calling CUDA library functions from a Java environment［C]∥IEEE International Conference on Imaging Systems and Techniques，Thessaloniki，Greece，July 1－2，2010：446－451.

［12]SONG Li，YIN Zhang－ke，WANG Jian－ying，et al.FFT－based matching pursuit implementation on CUDA platform［C]∥2nd International Conference on Information Science and Engineering，Hangzhou，China，December 4－6，2010：1181－1184.

［13]張 舒，褚艷利.GPU高性能運(yùn)算之CUDA［M].北京：中國(guó)水利水電出版社，2009.