基于多核處理器的并行雷達數(shù)據(jù)處理研究

朱海濤，倪世道，杜南山

(中國電子科技集團公司第三十八研究所，合肥 230088)

0 引言

未來戰(zhàn)爭中的電磁環(huán)境將異常復雜，雷達會受到各種形式的欺騙和干擾，產(chǎn)生大量的雜波，并且需要檢測的目標日益增多，目標的運動速度越來越快，機動性也越來越靈活［1］。上述情況的出現(xiàn)將會大大增加雷達數(shù)據(jù)處理的運算量，而雷達數(shù)據(jù)處理系統(tǒng)作為一個實時系統(tǒng)，必須在規(guī)定的時間內計算出結果。這對數(shù)據(jù)處理的計算能力提出了很高的要求。

一直以來，處理器芯片廠商通過不斷地提高主頻來提高處理器性能。但是，隨著芯片工藝的不斷進步，傳統(tǒng)的處理器體系結構技術已經(jīng)面臨瓶頸，晶體管的集成度已經(jīng)超過上億個，很難單純地通過提高主頻來提升性能，而且主頻的提高同時也帶來功耗的增 加。從應用需求來看，日益復雜的科學計算、多媒體、虛擬化等多個應用領域都迫切需要強大的計算能力。在這樣的背景下，各處理器廠商將芯片從提高主頻轉向多核、多線程［2］。

目前，雷達數(shù)據(jù)處理系統(tǒng)普遍采用單核處理器時代的串行架構，不能充分利用多核處理器的計算資源，早已不適應計算機技術的發(fā)展。本文基于多核處理器研究并行雷達數(shù)據(jù)處理架構的可行性，以提高雷達數(shù)據(jù)處理計算性能。

1 并行處理介紹

圖1 多核處理器結構

典型的多核處理器結構如圖1所示［3-4］，包含多個相同的處理器核，每個處理器核有自己的高速緩存，所有處理器核共享內存資源。這種結構屬于對稱多處理器(Symmetric Multi-Processor，SMP）。

在SMP處理器結構中，一般采用共享存儲并行編程模型，對需要并行的代碼段創(chuàng)建多線程進行計算，線程之間通過共享內存進行通信。

由于線程共享同一進程的內存空間，多個線程可能會同時訪問同一個數(shù)據(jù)。如果沒有正確的保護措施，對共享數(shù)據(jù)的訪問會造成數(shù)據(jù)的不一致和錯誤。

假設有一個共享變量counter 初始值為1，線程A執(zhí)行counter++，線程B 執(zhí)行counter--。這兩條語句實際是分別通過多條語句完成的:

線程A線程B

temp1=countertemp2=counter

temp1=temp1+1temp2=temp2－1

counter=temp1counter=temp2

兩個線程一種可能的執(zhí)行序列如下:

(1）線程A:temp1=counter(temp1=1）

(2）線程A:temp1=temp1+1(temp1=2）

(3）線程B:temp2=counter(temp2=1）

(4）線程B:temp2=temp2－1(temp2=0）

(5）線程A:counter=temp1(temp1=2）

(6）線程B:counter=temp2(temp2=0）

counter 正確的結果應該為1，但在兩個線程交叉執(zhí)行時就可能出現(xiàn)0 或2的錯誤結果。為了避免這種錯誤的發(fā)生，在多個線程訪問共享數(shù)據(jù)時需要進行同步。常用的同步機制包括臨界區(qū)、信號量和互斥量，比較常用的同步方法是互斥量和信號量［2］。

作為一種互斥設備，互斥量有兩個狀態(tài):上鎖和空閑。在同一時刻只能有一個線程能夠對互斥量加鎖。對于一個已經(jīng)加鎖的互斥量，當另一個線程試圖對它加鎖時，該線程會被阻塞，直到互斥量被釋放。

Linux 操作系統(tǒng)的IEEE POSIX 標準Pthreads 庫提供了互斥同步函數(shù)pthread_mutex_lock、pthread_mutex_unlock 等。

上述舉例通過互斥量同步機制可以得到正確的結果，如表1所示。假設線程A 首先獲得鎖。

表1 線程A和B的同步方法

并行算法(程序）執(zhí)行速度相對于串行算法(程序）執(zhí)行速度加快的倍數(shù)稱為并行加速比［2］。假設Sp是加速比，T1是單處理器下的運行時間，Tp是在有P個處理器并行系統(tǒng)中的運行時間，則

并行程序的效率Ep為

當Sp=P時，加速比被稱為線性加速比。在實際應用中，由于線程間同步、通信等額外的開銷導致Sp往往小于P。

2 數(shù)據(jù)處理流程分析

雷達數(shù)據(jù)處理系統(tǒng)接收到信號處理送來的點跡，一般按照圖2所示流程進行處理［5］。

圖2 數(shù)據(jù)處理流程

圖2所示的各個步驟是一個順序的過程，不能并行執(zhí)行。接下來對每個步驟進行分析，判斷是否適合并行處理。

(1）點跡預處理

把點跡從目標量測坐標系轉換到數(shù)據(jù)處理所在坐標系。該步驟是一個循環(huán)操作，每個循環(huán)對單個點跡進行坐標變換，循環(huán)之間沒有數(shù)據(jù)依賴關系，適合并行處理。

(2）數(shù)據(jù)互聯(lián)

建立當前時刻新點跡與歷史數(shù)據(jù)之間的關系，以確定這些點跡是否來自同一個目標，分為新點跡與航跡的互聯(lián)、新點跡與舊點跡的互聯(lián)。數(shù)據(jù)互聯(lián)方法主要有極大似然類算法和貝葉斯類算法。常用的最近鄰域算法及其改進算法屬于貝葉斯算法［5-6］。在最近鄰域算法中，根據(jù)每一個目標的預測位置設置該目標的跟蹤門(相關波門）。每一個新點跡與所有航跡一一進行相關，判斷其是否落入目標的跟蹤門內，如果落入該目標的跟蹤門內則形成點航配對，并根據(jù)新點跡與預測位置的距離差設置該配對的相關度，每個新點跡可能與多個航跡配對成功，按照相關度從高到低選擇最優(yōu)點航配對［6］。點點配對方法與點航配對相同。每一個點跡與所有航跡一一進行相關。該操作是循環(huán)操作，循環(huán)體之間沒有數(shù)據(jù)依賴，能夠采用并行處理方法。

(3）航跡起始

航跡起始是目標跟蹤的第一步，主要包括暫時航跡形成和軌跡確定。航跡起始可以劃分成多個獨立的子任務并行處理。

(4）跟蹤

根據(jù)數(shù)據(jù)互聯(lián)步驟中選擇的點航配對，對來自每個目標的新點跡進行跟蹤處理。目前，經(jīng)常采用的目標跟蹤方法有交互式多模型算法、Jerk 模型算法等。濾波算法多使用卡爾曼濾波［5-6］。交互多模型算法通過多個目標模型的有效組合來實現(xiàn)對目標機動狀態(tài)的自適應估計［5-7］。跟蹤是根據(jù)數(shù)據(jù)互聯(lián)步驟選擇的點航配對，對每個航跡的更新操作，各個航跡更新操作之間沒有數(shù)據(jù)依賴，可以并行處理。

(5）點跡與航跡維護

對每個點跡和航跡進行維護，刪除滿足條件的點跡和航跡。該步驟以單個點跡和航跡為單位進行操作，各個點跡、航跡之間沒有數(shù)據(jù)依賴，可以并行處理。

根據(jù)上述分析可知，5個步驟內部均可以采用多個線程并行處理的方法，如圖3所示。由于各步驟之間必須順序執(zhí)行，因此需要在每個步驟執(zhí)行結束時設置柵障(barrier），對并行處理的多個子任務進行同步。

3 實驗結果分析

根據(jù)上述分析，對雷達數(shù)據(jù)處理系統(tǒng)進行了并行架構設計以及實驗測試。實驗環(huán)境為Linux 2.6.32 操作系統(tǒng)，Intel Xeon W3565 4 核處理器，6 GB 內存。在實驗中，仿真了2000 幀數(shù)據(jù)，每幀模擬2000個目標，隨機產(chǎn)生20000個雜波點。

圖4 是并行數(shù)據(jù)處理系統(tǒng)執(zhí)行時間以及加速比統(tǒng)計。從圖中可以看出，隨著線程個數(shù)增加，執(zhí)行時間逐漸降低。單線程串行程序執(zhí)行時間為510 s，4 線程并行程序執(zhí)行時間降低到174 s，加速比接近3，數(shù)據(jù)處理系統(tǒng)性能得到了明顯提升。

圖3 并行處理示意圖

圖4 并行運算時間及加速比

根據(jù)第2節(jié)的分析可知，數(shù)據(jù)處理各個步驟均可以并行處理，因此4 線程并行程序加速比理論上應達到4，效率應達到1，而實驗中4 線程并行程序的效率只有Ep=2.92/4=73%。接下來對并行加速比的損失進行分析，圖5 是各個步驟執(zhí)行時間隨線程個數(shù)的變化情況。

點跡預處理、數(shù)據(jù)互聯(lián)、航跡起始和跟蹤中的數(shù)學操作易于劃分成多個子任務并行執(zhí)行，并且各個子任務之間數(shù)據(jù)依賴較少，增加線程數(shù)可以顯著的降低執(zhí)行時間。但是，由圖3 可知，每個步驟結束時都設置了barrier，只有等最慢的線程執(zhí)行結束時才會進行下一個步驟，CPU 利用率達不到100%，因此加速比不能線性提升。

圖5 各步驟并行執(zhí)行時間統(tǒng)計

點跡與航跡維護主要是對共享數(shù)據(jù)結構(如鏈表、堆等）的操作以及內存的讀寫。根據(jù)第2節(jié)的介紹可知，同時訪問共享數(shù)據(jù)結構會導致線程的阻塞，多個線程競爭有限的內存帶寬，每個線程實際利用帶寬都不高，因此點跡與航跡維護并行處理的效果不明顯。

4 結束語

未來日益復雜的電磁環(huán)境對雷達數(shù)據(jù)處理系統(tǒng)的計算能力要求將會非常高。為了提高數(shù)據(jù)處理的計算性能，本文基于多核處理器結構，對并行雷達數(shù)據(jù)處理架構進行了研究。從實驗結果可知，并行處理架構性能比傳統(tǒng)的串行系統(tǒng)有了明顯提升，在4 核處理器上，性能提高了將近3 倍。這表明雷達數(shù)據(jù)處理系統(tǒng)是適合并行處理的。但是，由于線程間同步、共享變量過多以及訪問內存競爭激烈等原因，并行系統(tǒng)的效率沒有達到最優(yōu)。在未來的工作中，將針對上述問題進行深入研究，進一步提高并行雷達數(shù)據(jù)處理系統(tǒng)的性能。

［1］俞志富，呂久明.基于航跡跟蹤的EKF 應用研究［J］.現(xiàn)代防御技術，2007，35(2）:113-117.

［2］多核系列教材編寫組.多核程序設計［M］.北京:清華大學出版社，2007.

［3］Franchetti F，Puschel M，Voronenko Y，Chellappa S，Moura J M F.Discrete fourier transform on multicore［J］.IEEE Trans.on Signal Processing Magazine，2009，26(6）:90-102.

［4］Hu Weiwu，Wang Jian，Gao Xiang.Godson-3:A Scalable Multi-core RISC Processor with X86 Emulation Support［J］.IEEE Trans.on Micro，2009，29(2）:17-29.

［5］何友，修建娟，張晶煒，等.雷達數(shù)據(jù)處理及應用［M］.2 版.北京:電子工業(yè)出版社，2009.

［6］蔡慶宇，張伯彥，曲洪權.相控陣雷達數(shù)據(jù)處理教程［M］.北京:電子工業(yè)出版社，2011.

［7］Averbuch A，Bar-Shalom Y，Dayan J.Interacting multiple model methods in target tracking:a survey［J］.IEEE Trans.on Aerospace and Electronic Systems，1998，34(1）:103-123.