基于GPU的并行MSD算法研究

李梓博，單福悅，高　寧

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

?

基于GPU的并行MSD算法研究

李梓博，單福悅，高寧

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

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

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

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

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

1MSD算法原理及計(jì)算量分析

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

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

(1)

(2)

(3)

(4)

(5)

(6)

圖1　MSD算法原理

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

2串行MSD算法

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

① 計(jì)算接收信號(hào)序列與每一個(gè)本地參考序列對(duì)應(yīng)的實(shí)部與虛部相關(guān)值；

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

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

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

圖2　串行MSD算法流程

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

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

3基于GPU的并行MSD算法

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

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

圖3　CUDA編程模型

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

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

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

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

4性能測(cè)試

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

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

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

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

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

5結(jié)束語(yǔ)

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

參考文獻(xiàn)

[1]嚴(yán)匡武.PCM/FM再入遙測(cè)信道波形設(shè)計(jì)方法研究[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)計(jì)(第4版)[M].北京:高等教育出版社,2010.

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

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

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

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

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

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

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

作者簡(jiǎn)介

收稿日期：2015-11-17

中圖分類(lèi)號(hào)V556.1

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

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

doi:10.3969/j.issn.1003-3106.2016.03.08

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