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

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

0 引 言

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

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

1 FFT并行捕獲算法

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

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

圖1 FFT捕獲算法的原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 基于GPU的并行捕獲方法

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

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

具體捕獲流程如下：

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

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

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

圖3 本地碼的存儲方式

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

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

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

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

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

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

2 捕獲方案的試驗驗證

2.1 試驗條件

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

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

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

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

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

圖4 碼相位的查找方法

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

表1 捕獲結(jié)果

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

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

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

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

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

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

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

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

3 結(jié) 論

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

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

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

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

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

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

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

［3]鄭海東，王明江，王進(jìn)祥，等 .一種AMR語言編碼器的VLSI設(shè)計及FPGA的實現(xiàn)［J].微電子學(xué)與計算機(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信號快速捕獲 ［J].宇航學(xué)報，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].北京：中國水利水電出版社，2009.