基于GPU的并行MSD算法研究

李梓博，單福悅，高　寧

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

?

基于GPU的并行MSD算法研究

李梓博，單福悅，高寧

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

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

關鍵詞PCM/FM解調；多符號檢測；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引言

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

本文將MSD算法與通用計算機平臺相結合，在通用計算機平臺上通過GPU對其并行優化，加快算法的運算速度，提高運算效率。

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

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

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

(1)

(2)

(3)

(4)

(5)

(6)

圖1　MSD算法原理

MSD算法的計算過程即是一連串的求相關運算，若每個碼元內包含Ns個采樣點，每次判決結束向后滑動一個碼元長度，則對于包含L個碼元的信號來說，共有L-N+1次MSD運算，每次有N×Ns個采樣點參與。那么在求相關過程中，共有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算法

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

① 計算接收信號序列與每一個本地參考序列對應的實部與虛部相關值；

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

③ 重復調用步驟①和步驟②，直到全部計算完成。

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

圖2　串行MSD算法流程

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

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

3基于GPU的并行MSD算法

GPU擁有海量計算核心，在處理大規模并行數據計算中存在與生俱來的優勢，極其適合承擔并行計算任務、提高MSD算法計算效率[5]。CUDA是由NVIDIA公司推出的一種通用并行計算架構，采用單指令多線程體系結構，為訪問GPU提供了直接的硬件接口，使用標準C語言及其擴展即可進行軟件開發與研究[6]。下面對CUDA編程模型及GPU體系結構做一個簡單概述。

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

圖3　CUDA編程模型

CPU作為Host，負責邏輯性強的事務處理和串行運算，與負責處理高密度并行運算、作為Device的GPU協同工作。有CUDA程序被執行時，首先由Host執行CPU代碼，當有任務需要GPU處理時，Host將向Device發起Kernel函數。在此之后，Host繼續完成自己的工作，直到Device計算完成，Host將從中獲取計算結果并進行下一步處理。

Kernel是運行在GPU上的CUDA并行計算函數，它是CUDA中一個可被并行執行的步驟。Kernel函數以及Kernel之間進行的串行計算由CPU負責調用。每個Kernel由GPU里的海量Thread并行執行。Thread的規模和結構由block和Grid決定，其中，block為Thread的集合，Grid為block的集合。每個Kernel中存在2個層次的并行，即block中Thread之間的并行與Grid中block之間的并行。

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

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

4性能測試

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

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

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

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

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

5結束語

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

參考文獻

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

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

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

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

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

[6]趙炳財.基于GPU技術的并行運算應用研究[D].長沙:國防科學技術大學,2012.

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

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

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

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

作者簡介

收稿日期：2015-11-17

中圖分類號V556.1

文獻標識碼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.