李梓博，單福悅，高　寧

(中國人民解放軍63778部隊，黑龍江 佳木斯 154002)

?

基于GPU的并行MSD算法研究

李梓博，單福悅，高寧

(中國人民解放軍63778部隊，黑龍江 佳木斯 154002)

摘要通用計算機(jī)的遙測信號處理系統(tǒng)通用性、靈活性強(qiáng)，不受硬件平臺限制，便于開發(fā)、升級和維護(hù)，能夠有效克服傳統(tǒng)硬件平臺的不足。多符號檢測(MSD)算法性能優(yōu)良，具有計算量大、并行度高的特點，適合在通用計算機(jī)上進(jìn)行處理。針對如何提高處理速度，在通用計算機(jī)平臺上研究基于圖形處理器(GPU)的并行MSD算法，通過使用GPU對MSD算法并行加速，提高算法運(yùn)算效率。實驗結(jié)果表明，在同樣條件下，基于GPU的并行MSD算法較串行算法最大可提速約134倍，能夠有效提高處理速度。

關(guān)鍵詞PCM/FM解調(diào)；多符號檢測；GPU；并行計算

Research on Parallel MSD Algorithm Based on GPU

LI Zi-bo,SHAN Fu-yue,GAO Ning

(Unit63778,PLA,JiamusiHeilongjiang101416,China)

AbstractThe telemetry signal processing system based on general-purpose computer has multiple advantages which can effectively overcome the shortcomings of current hardware devices,such as high versatility and flexibility,low cost,no limits of hardware platform,and easy upgrade and maintenance.The multi-symbol detection(MSD)algorithm has such characteristics as large computing and high parallelism and better performance,and it is suitable for processing on a general-purpose computer.For the method to improve processing efficiency,this paper studies parallel MSD algorithm based on GPU on general-purpose computer platform.The results show that the processing speed of parallel MSD algorithm is about 134 times higher than sequential algorithm.

Key wordsPCM/FM demodulation;MSD;GPU;parallel computing

0引言

脈沖編碼調(diào)制/調(diào)頻(PCM/FM)體制相較于其他遙測體制，具有能量效率高、靈活性強(qiáng)、精度高和抗噪聲性能好等優(yōu)勢，這些優(yōu)勢使得PCM/FM體制廣泛應(yīng)用于航天遙測領(lǐng)域中[1]。PCM/FM信號具有相位記憶性，即信號當(dāng)前相位不僅僅與當(dāng)前符號有關(guān)，而且受已發(fā)送的所有符號的影響[2]。MSD算法將接收信號碼組與所有可能的參考信號碼組做相關(guān)運(yùn)算，使得相關(guān)運(yùn)算結(jié)果最大的參考信號序列即為最優(yōu)判決序列。該算法充分利用前后碼元之間的相位信息，可以實現(xiàn)更高精度的PCM/FM信號解調(diào)，提高解調(diào)處理增益，從而降低解調(diào)門限。其內(nèi)部包含有大量并行乘加運(yùn)算，非常適合使用并行計算技術(shù)對其并行優(yōu)化。

本文將MSD算法與通用計算機(jī)平臺相結(jié)合，在通用計算機(jī)平臺上通過GPU對其并行優(yōu)化，加快算法的運(yùn)算速度，提高運(yùn)算效率。

1MSD算法原理及計算量分析

設(shè)s為接收信號包含信息，r為接收信號解得信息，r(t)為接收信號，則錯誤概率可表示為：

pε=p(r≠s|r(t))。

(1)

(2)

(3)

(4)

(5)

(6)

圖1　MSD算法原理

MSD算法的計算過程即是一連串的求相關(guān)運(yùn)算，若每個碼元內(nèi)包含Ns個采樣點，每次判決結(jié)束向后滑動一個碼元長度，則對于包含L個碼元的信號來說，共有L-N+1次MSD運(yùn)算，每次有N×Ns個采樣點參與。那么在求相關(guān)過程中，共有4×N×Ns×2N次乘法，(4×N×Ns-2)×2N次加法；求模平方過程中，共有2×2N次乘法，2N次加法。則單次MSD算法共有(4×N×Ns+2)×2N次乘法，(4×N×Ns-1)×2N次加法。

2串行MSD算法

進(jìn)行一次MSD判決，最終需要得到的即是與接收信號序列具有最大相關(guān)結(jié)果的本地參考序列。對于每一個接收信號序列，共有2N個實部相關(guān)結(jié)果和2N個虛部相關(guān)結(jié)果，對它們求模得到2N個模值，從中可判決出最大模值及其對應(yīng)本地參考序列的通道號。具體實現(xiàn)步驟如下：

① 計算接收信號序列與每一個本地參考序列對應(yīng)的實部與虛部相關(guān)值；

② 由步驟①中相關(guān)值求得對應(yīng)模值，選出其中的最大值及其對應(yīng)本地參考序列通道號；

③ 重復(fù)調(diào)用步驟①和步驟②，直到全部計算完成。

串行MSD算法流程如圖2所示。

圖2　串行MSD算法流程

隨著觀測長度的增加，MSD算法計算量呈指數(shù)增長，采樣率56 MHz的信號每秒也將產(chǎn)生大量待處理數(shù)據(jù)。串行MSD算法需要消耗大量的時間，不利于處理效率的提高。同時需要注意到，MSD算法將接收信號與2N組本地參考信號相乘，積分累加并求模平方，得到2N個對應(yīng)似然值，但這2N組計算之間是獨立不相關(guān)的。

由于計算資源及能力的限制，串行MSD算法逐次計算的方式效率較低?？紤]到每次MSD算法計算過程中，接收信號與本地參考信號的相關(guān)計算過程是相互獨立的，每次滑動所得到的接收信號序列也是相互獨立的，故可將接收信號分為若干段，并行地進(jìn)行MSD判決。

3基于GPU的并行MSD算法

GPU擁有海量計算核心，在處理大規(guī)模并行數(shù)據(jù)計算中存在與生俱來的優(yōu)勢，極其適合承擔(dān)并行計算任務(wù)、提高M(jìn)SD算法計算效率[5]。CUDA是由NVIDIA公司推出的一種通用并行計算架構(gòu)，采用單指令多線程體系結(jié)構(gòu)，為訪問GPU提供了直接的硬件接口，使用標(biāo)準(zhǔn)C語言及其擴(kuò)展即可進(jìn)行軟件開發(fā)與研究[6]。下面對CUDA編程模型及GPU體系結(jié)構(gòu)做一個簡單概述。

CUDA編程模型如圖3所示[7]。

圖3　CUDA編程模型

CPU作為Host，負(fù)責(zé)邏輯性強(qiáng)的事務(wù)處理和串行運(yùn)算，與負(fù)責(zé)處理高密度并行運(yùn)算、作為Device的GPU協(xié)同工作。有CUDA程序被執(zhí)行時，首先由Host執(zhí)行CPU代碼，當(dāng)有任務(wù)需要GPU處理時，Host將向Device發(fā)起Kernel函數(shù)。在此之后，Host繼續(xù)完成自己的工作，直到Device計算完成，Host將從中獲取計算結(jié)果并進(jìn)行下一步處理。

Kernel是運(yùn)行在GPU上的CUDA并行計算函數(shù)，它是CUDA中一個可被并行執(zhí)行的步驟。Kernel函數(shù)以及Kernel之間進(jìn)行的串行計算由CPU負(fù)責(zé)調(diào)用。每個Kernel由GPU里的海量Thread并行執(zhí)行。Thread的規(guī)模和結(jié)構(gòu)由block和Grid決定，其中，block為Thread的集合，Grid為block的集合。每個Kernel中存在2個層次的并行，即block中Thread之間的并行與Grid中block之間的并行。

在基于GPU的并行MSD算法中，由CUDA中block的每一個thread負(fù)責(zé)一次MSD計算。對于一個長為L的信號，共有L-N+1個thread被發(fā)起。以2N個本地參考序列的組合為單位，可將需要計算的所有本地參考序列放入GPU緩存中，提高計算效率，如此可最大化地利用GPU中的thread資源來進(jìn)行并行計算?；贕PU的并行MSD算法流程如圖4所示。

圖4　基于GPU的并行MSD算法流程

4性能測試

單次MSD算法計算量表明，若本地參考信號長度增加，計算量將會呈指數(shù)增長。由Nyquist采樣定理，可通過對接收信號適當(dāng)重采樣，減少單個碼元內(nèi)采樣點數(shù)Ns，有效降低計算量。根據(jù)文獻(xiàn)[8]的結(jié)論，本文將重采樣后的Ns取值定為7。

使用配置有Intel Xeon E5-2640 CPU，NVIDIA Tesla K20c GPU的通用計算機(jī)對并行加速性能進(jìn)行測試。通過在重采樣前后選取不同MSD觀測長度，測試系統(tǒng)計算效率。實驗數(shù)據(jù)如下：采樣率fs=56 MHz，碼速率Rb=2 Mbps，重采樣前后每個碼元分別包含28個和7個采樣點。實驗結(jié)果如表1和表2所示。

表1　重采樣前并行加速效果

表2　重采樣后并行加速效果

表1和表2表明，信號重采樣后，隨著采樣點數(shù)的減少，單次MSD計算時間明顯減少，但加速比卻有所降低。這是由于在觀測長度較小時，GPU上的計算資源尚未被充分利用；而當(dāng)觀測長度較大時，由于計算量的增加，GPU的計算能力逐漸飽和，達(dá)到了更高的計算資源利用率。以N=9為例，重采樣后并行MSD算法較重采樣前串行MSD算法，加速約408倍，取得了極為可觀的加速比。

5結(jié)束語

本文圍繞PCM/FM遙測信號解調(diào)，針對MSD算法計算量大、并行度高的特點，在通用計算機(jī)平臺上使用GPU對其并行加速。并行優(yōu)化后，并行MSD算法的計算效率較串行最高可提速約134倍。重采樣后并行MSD算法運(yùn)行效率是重采樣前串行MSD算法的408倍。測試結(jié)果表明并行加速效果顯著，能夠極大地縮短MSD算法的處理時間，提高系統(tǒng)處理速度。下一步將結(jié)合多GPU并行技術(shù)等，進(jìn)一步提高系統(tǒng)計算效率。

參考文獻(xiàn)

[1]嚴(yán)匡武.PCM/FM再入遙測信道波形設(shè)計方法研究[D].成都：電子科技大學(xué),2005.

[2]RICE M,SATORIUS E.Equalization Techniques for Multipath Mitigation in Aeronautical Telemetry[C]∥Military Communications Conference.MILCOM.IEEE,2004:65-70.

[3]盛驟,謝式千,潘承毅.概率論與數(shù)理統(tǒng)計(第4版)[M].北京:高等教育出版社,2010.

[4]劉毅.CPM 信號載波同步研究[D].西安:西安電子科技大學(xué),2008.

[5]劉培志,宿紅毅,羅壯,等.面向海量數(shù)據(jù)高性能計算的cpu/gpu協(xié)同處理方法[P].中國:CN102708088 A,2012.

[6]趙炳財.基于GPU技術(shù)的并行運(yùn)算應(yīng)用研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2012.

[7]張舒,褚艷利.GPU 高性能運(yùn)算之CUDA[M].北京:中國水利水電出版社,2009.

[8]李梓博,侯孝民,鄭海昕,等.基于MSD的PCM/FM信號解調(diào)參數(shù)性能研究[J].無線電工程,2014,(8):38-40.

李梓博男，(1991—)，碩士，助理工程師。主要研究方向：航天測控。

單福悅男，(1983—)，工程師。主要研究方向：航天測控。

作者簡介

收稿日期：2015-11-17

中圖分類號V556.1

文獻(xiàn)標(biāo)識碼A

文章編號1003-3106(2016)03-0026-04

doi:10.3969/j.issn.1003-3106.2016.03.08

引用格式：李梓博,單福悅,高寧.基于GPU的并行MSD算法研究[J].無線電工程,2016,46(3):26-29.