火靜斌,張曉濱,田 澤

(1.西安工程大學(xué),陜西 西安 710048;2.集成電路與微系統(tǒng)設(shè)計航空科技重點實驗室,陜西 西安 710068)

0 引 言

在雷達(dá)系統(tǒng)中,恒虛警率檢測技術(shù)(CFAR)通過動態(tài)調(diào)整檢測門限來檢測背景雜波干擾下的目標(biāo)。為了估計雜波功率,需要對每個雷達(dá)回波樣本進(jìn)行大量的計算。雷達(dá)系統(tǒng)需要高吞吐量和低延遲,傳統(tǒng)的CFAR處理通常使用現(xiàn)場可編程門陣列(FPGA)或數(shù)字信號處理器(DSP)[1-2],但也存在一定的問題,如開發(fā)周期長、調(diào)試難度大、耗費資源等。隨著GPU統(tǒng)一渲染架構(gòu)的出現(xiàn),基于CPU-GPU的異構(gòu)計算體系結(jié)構(gòu)開始普及,OpenCL、CUDA等開發(fā)平臺簡化了GPU編程難度,基于異構(gòu)計算平臺的GPU開發(fā)環(huán)境已廣泛應(yīng)用于雷達(dá)信號處理領(lǐng)域[3-6]。

在雷達(dá)應(yīng)用中,有多種方法可以實現(xiàn)恒虛警檢測,比如經(jīng)典的單元平均恒虛警檢測技術(shù)(Cell Averaging CFAR,CACFAR)、平均選大(Greatest of CFAR,GOCFAR)和平均選小恒虛警檢測技術(shù)(Smallest of CFAR,SOCFAR)。但是在需要多目標(biāo)或高性能的應(yīng)用環(huán)境中,有序統(tǒng)計類恒虛警檢測技術(shù)的應(yīng)用范圍更廣[7]。與其他檢測方法不同的是,OSCFAR的內(nèi)部實現(xiàn)更為復(fù)雜,屬于計算密集型方法,需要高性能計算設(shè)備。文獻(xiàn)[8]在Tesla C1060 GPU上研究了PD雷達(dá)中CACFAR的GPU實現(xiàn),通過對算法進(jìn)行了優(yōu)化,提高了算法的并行性,達(dá)到了一定的加速效果。文獻(xiàn)[9]利用OpenCL在集成顯卡以及中等級別產(chǎn)品AMD GPU實現(xiàn)CACFAR,但由于使用零填充方法,容易造成程序虛警。文獻(xiàn)[10]利用積分圖像算法加速了并行均值濾波算法,但需要兩個內(nèi)核函數(shù)上分別實現(xiàn)計算并行前綴和以及平均值,會產(chǎn)生額外的計算以及對共享內(nèi)存的不必要訪問。文獻(xiàn)[11]在GPU端采用Blelloch掃描算法來對CA-CFAR求和過程進(jìn)行優(yōu)化,避免了重復(fù)計算,但存在的問題是數(shù)據(jù)必須是以二的指數(shù)冪格式傳輸。文獻(xiàn)[12]提出的局部最大最小快速濾波是一種充分考慮數(shù)據(jù)重用的算法,可以用來解決GOCFAR、SOCFAR的數(shù)據(jù)重用,但存在邊界溢出的問題。

以上都是對均值類恒虛警檢測算法進(jìn)行了GPU加速實現(xiàn),而對OSCFAR加速的研究還比較少。文獻(xiàn)[13]在FGPA上設(shè)計實現(xiàn)了可以規(guī)避排序算法的OSCFAR,但是如果需要排序值計算信噪比時不能滿足系統(tǒng)要求。文獻(xiàn)[14]設(shè)計了重復(fù)快速排序算法,但快速排序不適合在GPU上進(jìn)行計算。文獻(xiàn)[15]提出了具有分布式直方圖的OSCFAR的計算方法,但是需要一定的計算量。文獻(xiàn)[16]提出了基于“掃雷算法”的OSCFAR算法,適合并行計算,但是需要利用第三方工具做預(yù)處理排序。

該文的研究重點是在OSCFAR中使用GPU進(jìn)行加速,提出了一種改進(jìn)的OSCFAR方法,使其適用于GPU并行實現(xiàn)。首先,設(shè)計了一個預(yù)處理程序,對每個多普勒通道進(jìn)行數(shù)據(jù)擴充。在預(yù)處理程序中,為了減少GPU處理中的分支操作,對每個多普勒通道數(shù)據(jù)進(jìn)行擴充,大小為左右保護(hù)單元以及參考單元數(shù)量之和,從而優(yōu)化設(shè)備計算效率。其次,設(shè)計并實現(xiàn)了CPU-GPU異構(gòu)架構(gòu)下OSCFAR的并行加速方法。根據(jù)GPU的顯存大小,將原始數(shù)據(jù)按時間順序劃分為若干個子數(shù)據(jù)并傳輸?shù)紾PU。為了優(yōu)化計算效率,預(yù)處理程序分配給CPU執(zhí)行,之后OSCFAR由GPU執(zhí)行。為了證明所提出方法的可行性,在雷達(dá)模擬噪聲信號為瑞利噪聲背景條件下,對有序統(tǒng)計類恒虛警檢測方法進(jìn)行了仿真實驗。在實驗中,所提出的方法消耗時間是僅在CPU上運行的OSCFAR所消耗時間的1/60,且目標(biāo)信號質(zhì)量并沒有降低。

1 有序統(tǒng)計類恒虛警處理方法分析

在瑞利背景條件下,假設(shè)v(t)是單脈沖檢測中某個分辨單元的一個觀測值,當(dāng)使用平方律檢波器進(jìn)行檢波時,可寫成如下形式:

D(v)=I2(v)+Q2(v)

(1)

其中,I(v)表示信號的同相分量,Q(v)表示信號的正交分量。在一般的雜波環(huán)境中,可以認(rèn)為接收到的雜波的包絡(luò)服從瑞利分布。在均勻的瑞利雜波背景條件下,單元平均方法就是利用檢測單元周圍的前沿滑窗和后沿滑窗中的一組獨立同分布的參考單元采樣的平均值來估計雜波功率水平的。有序統(tǒng)計類(Order Statistics)OSCFAR是采用統(tǒng)計手段來估計雜波水平功率。該方法和常規(guī)均值類CFAR的區(qū)別是其在多目標(biāo)環(huán)境下檢測性能較好,但是在雜波邊緣環(huán)境和均勻環(huán)境下會存在一定的損失,如圖1所示。

圖1 有序統(tǒng)計類CFAR檢測方法

數(shù)據(jù)經(jīng)過平方率檢波得到距離多普勒功率譜,對每個待檢測單元D選取參考單元(xi(i=1,2,…,n),yj(j=1,2,…,n)),為了防止目標(biāo)的能量泄露到參考單元造成雜波功率估計值較高,一般在檢測單元兩側(cè)選取一定的保護(hù)單元(np)。OSCFAR算法是將待檢測單元兩側(cè)參考單元(ns)拼接后進(jìn)行排序,得到一個遞增序列。然后取第K個有序值作為雜波水平的估計值,一般條件下K的取值和rate相關(guān),具體計算方式為K=rate*2n。OSCFAR的虛警概率PFA與門限因子α的關(guān)系如下:

(2)

一般條件下,虛警概率PFA為固定概率值,由此計算得到門限監(jiān)測因子α,檢測門限T為門限監(jiān)測因子與有序值K的乘積。將待檢測目標(biāo)單元與檢測門限進(jìn)行比較,如果待檢測單元的功率值大,則判決為目標(biāo),否則判為雜波。

從有序統(tǒng)計類恒虛警檢測圖中可看出,均值類恒虛警檢測方法CACFAR是每一個采樣點需要完成一次求和運算,這樣可以通過并行掃描的方式避免大量的重復(fù)運算。例如Blelloch算法是在GPU端計算掃描的方法,避免了CPU完成掃描處理時主機段與設(shè)備端之間的傳輸時間。而OSCFAR與CACFAR的區(qū)別在于中間的排序過程,會耗費系統(tǒng)大量的資源。為此,如何選擇適合GPU并行的排序算法以及對完整流程的并行化設(shè)計是OSCFAR加速研究的重點。

2 基于GPU的有序統(tǒng)計類恒虛警檢測并行化技術(shù)

脈沖多普勒雷達(dá)信號處理系統(tǒng)常用的算法模塊包括脈沖壓縮、動目標(biāo)信號顯示、動目標(biāo)檢測、恒虛警檢測。雷達(dá)信號在經(jīng)過前三個步驟之后可以得到大小為Np*Ns的二維矩陣,針對該矩陣進(jìn)行距離維CFAR檢測時,各個脈沖之間不存在聯(lián)系,可以同時進(jìn)行Np個脈沖的CFAR檢測,因此存在數(shù)據(jù)集的并行。針對有序統(tǒng)計類的檢測算法而言,處理主要有平方率檢波、每個單元的雜波功率估計(包括窗口排序)、檢測門限計算以及待檢測單元的比較,都可以由GPU的多個線程完成。因此,OSCFAR具有較好的數(shù)據(jù)以及線程級別的可并行性。

2.1 有序統(tǒng)計類恒虛警檢測的GPU實現(xiàn)

基于OpenCL的OSCFAR處理流程如圖2所示,采用以單個脈沖為單位進(jìn)行OSCFAR,單個脈沖內(nèi)的平方率檢波,兩側(cè)參考單元的排序,以及待檢測單元的分支可以由多個線程并行實現(xiàn)。

圖2 基于OpenCL的OSCFAR處理流程

大小為Np*Ns的數(shù)據(jù)從主機端傳到設(shè)備端后,按照流程可以將算法分解為兩個模塊依次對應(yīng)兩個內(nèi)核函數(shù),第一個內(nèi)核函數(shù)平方率檢波主要將復(fù)數(shù)信號轉(zhuǎn)化為實數(shù)信號,數(shù)據(jù)格式為實部虛部交替存儲,即連續(xù)兩個數(shù)據(jù)分別是信號的實部和虛部,一般采用OpenCL內(nèi)建矢量數(shù)據(jù)類型表示。若采用一維尋址的方式,設(shè)置合適的workgroup大小p,則需要的workgroup數(shù)量為Np*Ns/p記為q,每個線程完成一個平方律檢波計算,總的計算組織架構(gòu)如圖3所示。

圖3 平方率檢波處理流程

第二個內(nèi)核函數(shù)主要用于計算雜波功率水平估計以及與實際值進(jìn)行判斷,若采用一維尋址的方式,設(shè)置workgroup大小,每個線程進(jìn)行一個信號的雜波水平估計與判斷。假設(shè)單側(cè)參考單元大小為nr,單側(cè)保護(hù)單元大小為np,由此可以將距離維度的數(shù)據(jù)劃分為三個部分:對于前nr+np個元素來說,如果要填充左右數(shù)據(jù)的話可以從右側(cè)取2*(nr+np)個元素對其排序后將第K個有序值作為待檢測單元的估計值,對于最后nr+np個元素取其左側(cè)2*(nr+np)個元素,中間部分的話直接從左右兩側(cè)各取nr+np個元素。將兩側(cè)數(shù)據(jù)排序取K值作為雜波功率的估計值,最后將估計值與實際值作對比確定是否為目標(biāo)對象。

2.2 算法優(yōu)化

優(yōu)化1:數(shù)據(jù)填充。

在估計雜波功率水平時,需要將距離維度的數(shù)據(jù)劃分為三個部分,即需要三個分支操作來進(jìn)行各自的計算。由于GPU的設(shè)計不善于處理分支判斷,因此需要將每個線程進(jìn)行統(tǒng)一操作。采取的辦法是數(shù)據(jù)擴充,擴充的方法如圖4所示。如果填充數(shù)據(jù)零的話,對于均值類CFAR和有序統(tǒng)計類OSCFAR來說,將導(dǎo)致雜波功率估計值變小,從而導(dǎo)致檢測門限變小容易造成虛警[9]。因此,可以采取的方法是將原數(shù)據(jù)做復(fù)制,不論是鏡像復(fù)制還是按序復(fù)制都會對這兩類數(shù)據(jù)結(jié)果產(chǎn)生影響較小,在實驗中采用按序復(fù)制一側(cè)的方法。

圖4 數(shù)據(jù)填充方式

優(yōu)化2:排序分析。

得到數(shù)據(jù)后將兩側(cè)數(shù)據(jù)合并,利用合適的排序算法得到雜波功率的估計值。采取的排序算法可以是傳統(tǒng)的冒泡排序算法以及快速排序,由于只需要遞增排序前K個元素,對于冒泡排序來說,時間復(fù)雜度可以降為O(K×N)。當(dāng)數(shù)據(jù)量過大時,排序過程可能成為程序瓶頸,快速排序具有良好的執(zhí)行效率可以提高性能,但由于OpenCL平臺限制,GPU執(zhí)行的機器代碼僅包含分支和循環(huán),一般情況下,對于函數(shù)調(diào)用來說編譯器會將函數(shù)轉(zhuǎn)換為內(nèi)聯(lián)函數(shù),但是對于遞歸調(diào)用來說無法做到。因此,對于高效的快速排序無法應(yīng)用到本項目場景中。

為此,解決的辦法是采用雙調(diào)排序。雙調(diào)排序是基于Batcher定理的一種適用于數(shù)據(jù)并行的排序算法,首先需要生成一個雙調(diào)序列(有一個非嚴(yán)格遞增序列和一個非嚴(yán)格遞減數(shù)列),然后將該序列劃分為兩個子序列(左邊的雙調(diào)序列小于右邊的序列),繼續(xù)對每個子序列進(jìn)行劃分直到序列長度為1,就可以得到單調(diào)遞增的序列。

優(yōu)化3:內(nèi)存優(yōu)化。

對于平方率檢波內(nèi)核函數(shù)來說,AMD系列GPU支持的最大workgroup大小為256,為此可以將交替存儲的實虛數(shù)拷貝到本地內(nèi)存中,減少函數(shù)對全局內(nèi)存的訪問,提高設(shè)備計算能力。除此之外,可以在程序中使用頁鎖定(Page-Locked)內(nèi)存分配方式,操作系統(tǒng)不需要對其分頁也不需要將其交換到磁盤上,可以將其一直置于物理內(nèi)存中,GPU根據(jù)其物理地址直接與主機進(jìn)行數(shù)據(jù)的復(fù)制與傳遞,可以獲得更好的加速性能。

對齊訪問全局內(nèi)存對于AMD系列以及Nvida系列GPU來說都會提高GPU性能。本實驗中,在主機端對數(shù)組數(shù)據(jù)進(jìn)行手工填充比較復(fù)雜,該文采用了OpenCL引入的clEnqueueWriteBufferRect命令將主機端數(shù)據(jù)拷貝到設(shè)備端。在創(chuàng)建緩存時,用來確定的列數(shù)是滿足對齊后所需的數(shù)據(jù)。對于一維的大小為256的workgroup來說,列數(shù)應(yīng)該四舍五入到最近的256的倍數(shù)。

3 實驗評估

實驗中用到的GPU硬件平臺分別為Intel(R) HD Graphics520和AMD Radeon R7 M370。CPU為Core(TM)i5-6200U CPU@2.30 GHz。所使用的數(shù)據(jù)是由Matlab仿真的線性調(diào)頻信號,其主要參數(shù)如表1所示。

表1 模擬信號參數(shù)

3.1 優(yōu)化實驗結(jié)果對比

由之前的模擬數(shù)據(jù)可知,采樣頻率(fs)為2.0×106,雷達(dá)發(fā)射脈沖重復(fù)周期(PRT)為4.096×10-3,則單個脈沖周期的采樣點數(shù)fs*PRT為8 192。脈沖數(shù)量為16,則總的采樣點數(shù)為16*8 192。雷達(dá)信號在經(jīng)過脈沖壓縮、MTI、MTD之后可以得到大小為16*8 192的二維復(fù)數(shù)矩陣。由于存儲的數(shù)據(jù)格式為實虛部交替存儲,交由主機端存儲時數(shù)據(jù)16*8 192*2。首先,數(shù)據(jù)在經(jīng)過平方率檢波內(nèi)核函數(shù)時,相鄰兩個數(shù)據(jù)之間分別是采樣點的實部與虛部,將二者的平方和存入該線程的寄存器中。其次,針對該矩陣進(jìn)行距離維CFAR檢測時,采用一維尋址方式,設(shè)置全局工作組大小16*8 192,由于workgroup中的work-item不存在數(shù)據(jù)共享,并未設(shè)置本地workgroup大小。處理雜波功率水平估計采用有序統(tǒng)計類方式,測試穩(wěn)定后取三次實驗結(jié)果,表2給出了CFAR在CPU和GPU上運行時間對比。

表2 CPU與GPU運行時間以及加速比

其中,Graphics520執(zhí)行期間,兩個內(nèi)核函數(shù)(平方率檢波,雜波估計與判別)分別耗費的時間為0.251 ms、99.111 ms。由表2可以看出,并行化后的恒虛警檢測在GPU上有著良好的性能。經(jīng)過算法優(yōu)化后的OSCFAR方法實驗結(jié)果如表3所示。優(yōu)化后系統(tǒng)的執(zhí)行時間較優(yōu)化前縮小到原來的1/7,實驗證明,該方法加速效果明顯。

表3 優(yōu)化前后的執(zhí)行事件對比

3.2 算法優(yōu)化實驗結(jié)果分析

對于OSCFAR來說,優(yōu)化的方面分別是將條件分支通過數(shù)據(jù)擴充解決、排序算法的合理使用和內(nèi)存優(yōu)化。本實驗采用不同的策略在16個雷達(dá)脈沖,在每個脈沖的采樣點數(shù)為8 192的條件下進(jìn)行了分支與數(shù)據(jù)填充實驗分析,得到的實驗結(jié)果如表4所示。

表4 分支與數(shù)據(jù)填充實驗分析

對于數(shù)據(jù)擴充來說會影響到兩個方面,首先是在主機端(CPU)擴充了數(shù)據(jù),對于每個雷達(dá)脈沖的8 192個采樣點來說,只會在其兩側(cè)分別添加保護(hù)單元和參考單元的總數(shù),導(dǎo)致數(shù)據(jù)傳輸時間會受到一定的影響。其次就是減少數(shù)據(jù)流分支,對于工作組中的線程執(zhí)行同樣的操作會對GPU執(zhí)行效率產(chǎn)生了近5倍的性能提升,對整體的優(yōu)化有著顯著的提升。

除此之外,有序統(tǒng)計類恒虛警檢測中的排序算法也會對GPU執(zhí)行效率有一定影響,實驗中采用了改進(jìn)過的冒泡排序和雙調(diào)排序來對參考單元數(shù)量進(jìn)行排序,數(shù)據(jù)采用填充過的雷達(dá)信號數(shù)據(jù),實驗結(jié)果如表5所示。分析算法中存在的瓶頸,通過設(shè)計更加合理、更加具有并行性的排序算法,對估計每個待檢測單元的功率值的GPU執(zhí)行效率有了近1.5倍的性能提升。

表5 排序算法實驗分析

對于OSCFAR中的兩個內(nèi)核函數(shù)都可以在內(nèi)存優(yōu)化方面有一定的空間,采用的方法就是減少對全局內(nèi)存的訪問,利用本地內(nèi)存提升效率。利用頁鎖定機制,系統(tǒng)不需要進(jìn)行分頁也不需要置換內(nèi)存,可以獲得較好的加速性能。缺點就是如果數(shù)據(jù)量過大的話,一旦沒有足夠的物理內(nèi)存供程序使用,系統(tǒng)性能有所下降。通過循環(huán)展開將平方率檢波后的二維數(shù)據(jù)映射到OpenCL二維空間,提升計算部件的利用率。實驗結(jié)果如表6所示:算法經(jīng)過頁鎖定機制以及內(nèi)存訪問對齊后的性能有所提升。

表6 主存與循環(huán)展開實驗分析

3.3 誤差分析

圖5展示了OSCFAR在CPU端和GPU端的目標(biāo)檢測對比結(jié)果,二者處理結(jié)果近乎一致。在處理待檢測功率估計值時將CPU與GPU的數(shù)據(jù)做誤差分析,得到的結(jié)果如圖6所示,其絕對誤差小于3×10-3,且GPU具有更好的數(shù)據(jù)精度。

圖5 OSCFAR CPU與GPU處理結(jié)果

圖6 CPU和GPU誤差分析結(jié)果

4 結(jié)束語

提出了一種基于GPU的恒虛警檢測并行處理方法,通過對原數(shù)據(jù)進(jìn)行填充、采用雙調(diào)排序并行化等優(yōu)化策略來實現(xiàn)GPU加速?；贠penCL通用異構(gòu)平臺的GPU加速滿足了雷達(dá)信號處理高性能要求,在集成顯卡以及中等級別的AMD顯卡上可以達(dá)到60倍左右的加速比,本研究為后續(xù)基于國產(chǎn)GPU的加速積累了經(jīng)驗。