OpenMP并行計算在側向散射激光雷達數據處理中的應用?

劉俊見 陶宗明

（1.陸軍軍官學院研究生管理大隊 合肥 230031）（2.陸軍軍官學院基礎部 合肥 230031）

1 引言

大氣氣溶膠是指液體或固體微粒散布在大氣中形成的相對穩定的懸浮體系，對人體健康環境和全球氣候都有一定的影響［1］，是當前大氣科學領域中的熱點問題之一。在大氣環境監測領域，準確了解氣溶膠隨時空的分布規律具有十分重要的意義。

激光雷達以它精細的時間、空間和光譜分辨率、大的垂直跨度和高的探測精度很快便成為探測大氣氣溶膠空間分布的有力工具，被廣泛應用于環境與大氣監測等領域［2～6］。基于CCD的側向散射激光雷達是正在研究中的新技術，它將發射裝置與接收裝置分兩處放置，解決了傳統后向散射激光雷達中的過渡區和盲區問題，而且由于使用了側向技術，其在近距離段具有極高的空間分辨率［7～10］。

為了讓側向散射激光雷達在白天也能工作，克服白天背景光過強的有效方法是減小曝光時間和多次曝光求信號的平均值。我們所用CCD的圖片的像素是3352*2532，大小約為16M，多次曝光（如300次）提取信號的平均值需要占用較多的計算時間，這對數據的實時處理造成一定的困難。

隨著多核處理器架構被業界廣泛采用，通過并行計算縮短執行時間已成為高性能計算領域使用最廣的方法［11］。OpenMP（Open Multi-Processing）是一種典型的共享內存平臺下的編程API，支持跨平臺共享內存方式的多線程并發，其通過提供對并行算法的高層抽象描述，降低了并行編程的復雜性和難度［12］。

本文通過分析側向散射激光雷達數據處理流程的特點，找出迫切需要采用并行計算提高效率的關鍵任務。基于OpenMP標準，設計并行優化方案，實現側向散射激光雷達數據處理計算并行化，通過實驗分析并檢驗其并行效果，以期有效挖掘不同計算設備的潛能，為采用并行計算技術處理側向散射激光雷達數據提供一種高效、經濟的實施方案。

2 側向散射激光雷達數據處理中的關鍵計算任務分析

激光雷達大氣探測的監控周期一般為10分鐘，即每間隔10分鐘采集一組數據。對于基于CCD的側向散射激光雷達，由于采集的圖像數據占用存儲空間龐大，以一張CCD圖像16M、每組300對圖像（每對為兩張圖片，用于減少背景光、干擾光）為例，白天一小時就要采集3600張（6*300*2），需要占用接近60G的硬盤空間，因此需要在一個周期內完成該組數據的采集、處理、保存并刪除初始CCD圖像數據，這對數據處理的效率提出了很高的要求。從側向散射激光雷達數據處理的需求出發，計算主要集中在以下幾個方面，包括信號提取、配準、反演、可視化顯示等運算。

基于上述的側向散射激光雷達數據處理中的幾個關鍵任務，下面對它們的并行需求作一個簡要分析。在進行反演計算時，一般采取分像元處理的策略，由于各位置（或光束方向上各像元）之間的計算是沒有依賴關系的，因此，在多核環境下，可以同時啟動多個進程，每個進程分別完成對應某部分像元的反演計算，既能充分利用設備的系統資源，又避免了設計對應的并行算法；可視化的主要目的是為了方便研究人員對原始數據做出正確解釋，相對于其他的處理任務，其處理時間靈活，甚至可以在一天的觀測任務結束后再繪制當天的氣溶膠后向散射系數時空分布圖；配準的計算量相對較少，主要是循環及方差計算，直接在已有的串行代碼基礎上嵌入指令語句將其并行化就可以取得較好的加速效果。因而信號提取是側向散射激光雷達數據處理中迫切需要設計對應并行算法的關鍵。

針對夜間圖像，信號提取主要指在減少背景光、干擾光的基礎上，通過高斯擬合去噪并提取對應角寬度內的散射光子數。減少背景光、干擾光主要通過連續拍攝曝光時間相同的兩張CCD相片［13］，如圖1所示，（a）是包含所有光的CCD相片，（b）是缺少激光散射光束的CCD相片，將兩次拍攝的CCD對應像元信號相減，獲得的結果如（c）所示，這就減少了背景光和干擾光的影響；提取散射光子數主要通過高斯擬合逐一計算沿光束方向的每個像元對應的信號光子數與噪聲光子數，從而得到光子數與位置（或光束方向上像元）的一一對應關系。

圖1 減少背景光、干擾光

信號提取的難度主要在白天圖像的處理上，相對于夜間，白天作為主要背景光的日光太強，曝光時間過長會導致圖像過曝，因此需采取減少單張圖像曝光時間、多張圖像疊加的方式來獲取CCD圖像數據。為了減少局部誤差、獲得較高的信噪比，白天每次最少需要采集300對～500對的CCD圖像數據，每對圖像都需要減少背景光、干擾光，去噪并提取散射光子數，隨后將提取的散射光子數逐對逐像元進行疊加求和，得到最終的結果。同時為了應對系統崩潰、采集與處理不同步等意外情況，數據處理算法必須要有快速處理之前積壓的多組數據的能力，要能高效率地從上千張CCD圖像中提取出每個時段的信號，這對數據處理的效率提出了更高的要求。

3 動態設置并行循環的線程數量

在側向散射激光雷達數據處理的實際情況中，由于不同情況下對數據精度及成本的雙重考慮，數據處理程序將運行在不同的設備環境里，這些設備可能是雙核、4核甚至更多，同時由于超線程技術的應用，某些型號的CPU可以同時執行多重線程。同時對于不同的數據處理任務，由于需要處理的數據量及循環次數不同，執行該任務時需要的線程數也不同。因此需要根據設備性能的不同來自動設置合適的線程數量，以滿足不同情況下的需求，使數據處理程序具有較強的可擴展性，當運算量發生變化時，仍能通過自動設置使線程數量滿足要求。

通常認為，在具體計算需要使用多少線程時，主要需要考慮以下兩點［14］：

1）當循環次數比較少時，如果分成過多數量的線程來執行，可能會使得總運行時間高于較少線程或一個線程執行的情況，并且會增加能耗。

2）如果設置的線程數量遠大于CPU核數的話，那么存在著大量的任務切換和調度等開銷，也會降低整體效率。

由于不同數據處理任務的循環次數差距很大，夜間進行信號提取時，每組數據為300～500對CCD圖片，那么對每組圖片進行信號提取需要進行300～500次循環；而進行配準計算時的循環次數只有10～30次，那么如何根據循環的次數和CPU線程數來動態地設置線程的數量呢？通過分析側向散射激光雷達數據處理任務的特點，確定了動態設置線程數的需求如下：

1）多個線程運行時，由于現有CPU線程數一般不超過16，因此每個線程運行的循環次數應不低于總循環次數的十六分之一，同時不少于4次。

2）總的運行線程數不超過CPU總線程數，以避免任務切換開銷。

基于上文確定的需求，動態設置線程數的程序流程圖如圖3所示。其中Num為CPU總線程數，Run_num為設置的執行線程數。

圖2 動態設置線程數程序流程圖

實際編程中，將其編為一個獨立的功能函數，其返回值即是針對此次循環應設置的線程數，每次并行化循環開始前調用該函數來獲取合適的線程數量，并使用num_threads子句設置線程數。

4 并行方案及并行方法

并行算法設計常見的模式有數據分解模式、分治模式、流水線模式、任務并行模式、任務圖調度模式、動態任務調度模式等，針對夜間信號提取這一關鍵任務，從其數據處理流程特點與需求出發，選取了兩種最適合的模式分別進行了并行算法的設計。

該任務的串行算法A可以簡化為三層循環，如下所示，內層循環完成一對CCD圖像沿光束方向上各像元信號的提取，output即為提取出的序號為j的像元的散射光子數；第二層循環完成數量為amount的一組CCD圖像的信號提取，每對圖像提取出的散射光子數進行累加求和并存儲在數組a（j）中；外層循環是針對因為意外堆積的多組數據，find函數采用遞歸策略掃描文件夾內所有的CCD圖像路徑，返回值find（）為圖像對數。

4.1 方法一

數據分解模式即是將數據分解為N個獨立的數據子塊，每個線程處理其中的一個或多個數據塊。由于每對CCD圖像之間都是相互獨立的，符合數據分解模式的要求，因此選擇其作為第一種方法完成并行算法的設計，此方法記為算法B。

由于算法A為三層循環結構，且最外層循環次數一般較少，若對外層循環并行化，實際創建的線程數很可能小于CPU的總線程數，不能很好地發揮CPU性能，會大大降低并行算法的效率；同時很難通過對外層循環進行調度使內層循環達到負載均衡。針對上述問題，本文在進行并行算法設計時，首先將外層循環和第二層循環進行合并，合并后的兩層循環結構如下所示。

其中number為采集完成的圖像組數，計算流程如圖3所示，隨后在內層循環通過判斷圖像名的標志位，將提取出的散射光子數按組別分別累加。

圖3 計算圖像組數流程圖

針對合并后的兩層循環，若對內層循環進行并行化，就必須要解決a（j）等數組的同時操作問題。內層循環中，每個線程完成信號提取后，都需要和a（j）累加，因此每個線程都要對a（j）進行讀寫操作。對這類問題，OpenMP提供了臨界區、數據規約等方式來進行線程之間的同步，但是不論哪種方法都會在一定程度上增加系統開銷。本文選擇只對外層循環進行并行化，避開內層循環的鎖競爭，經過比較，該方法的加速性能與采用數據規約基本一致，并優于采用臨界區的方法。

雖然需要處理的圖像對數M難以被線程數N整除，CCD圖像數據無法被劃分為計算量相同的N個數據子塊，即不使用size參數時不同線程實際分配的迭代次數會相差1，但相對于每個線程分配的任務總量而言，某一個或某幾個線程多處理一對圖像幾乎不會對總體加速性能產生影響，因此本文采用靜態調度方法實現并行算法的負載均衡，關鍵代碼如下。

4.2 方法二

由于信號提取首先需要從硬盤中讀取大量的數據，很大程度上存在著IO瓶頸，本文選擇流水線模式作為第二種方法對并行算法進行優化，此算法記為算法C。流水線模式借鑒工業生產中的流水線思想，將一個數據處理流程分解為幾個步驟，每個步驟采用一個或多個線程來進行處理，在處理具有IO瓶頸的數據處理流程有較大優勢。

針對信號提取這一流程，我們可以將其分解為如圖4所示的三個步驟。

圖4 對信號提取過程進行流水線分解

串行算法采用一個線程依次執行上述的三個步驟；而采用流水線模式進行并行實現時，分別使用一個或多個線程來讀取CCD圖像數據，減少背景光、干擾光，以及提取散射光子數。這樣就使得三個步驟的處理并行進行，提高了處理效率，如圖5所示。在并行實現的過程中，當讀取數據線程獲取了一部分CCD圖像數據后，后續的線程就可以開始進行數據處理了。

圖5 對信號提取過程進行并行處理

但是從上述的分析中也可以看出，運用流水線模式對信號提取過程進行并行實現時，數據從上一個步驟傳遞到下一個步驟時，這兩個步驟是并行執行的，因而存在數據競爭，需要使用同步操作對數據進行保護，針對此問題，本文主要采用臨界區的方法來實現同步操作。

并行實現時，為避免線程資源的浪費以及非線性讀取對讀入速度的影響，筆者首先指定了一個線程來讀取數據。在實現后續兩個步驟的并行化時，筆者發現很難將這兩個步驟分開實現并行化，主要問題在于以下兩點：

1）程序設計時被要求能在不同性能的設備上高效運行，不同設備可供使用的線程資源差距明顯，很難對其進行線程分配。

2）上文中提到了數據保護的問題，并行時每增加一個步驟，實際上也增加了用于數據同步的系統開銷。

在進行了多次試驗后，筆者決定將后續兩個步驟合并，共用數據處理線程來進行并行化，結果顯示其加速性能要優于分開并行化的方案。實際上，方法二主要是在方法一的基礎上對數據讀取進行了一定的優化，數據處理部分的并行化與方法一相同。

5 并行測試及結果分析

按照第4節中的兩種算法，對針對夜間信號提取這一關鍵與難點進行并行化，并運用型號為AlienwareM14xR1的筆記本電腦進行測試，其CPU為主頻2.20G的i7-2670QM，內存16G，操作系統為Windows7，編程環境為VS2015。從300對CCD圖像中提取散射光子數，算法B和算法C的總運行時間見如圖6所示，其中由于算法C無法單線程執行，其線程數為1時直接執行算法A（即串行算法）。

圖6 算法B和算法C運行時間比較

圖6的橫軸為采用的線程數，分別從1到8；縱軸為多線程模式下的該流程運行時間。可以看出，采用線程數較少時，算法B運行時間要比算法C少，而隨著線程數增加算法C與算法B運行時間差距逐漸縮小，線程數為4時，兩種算法的運行時間基本相同，當線程數大于4后，算法C的運行時間開始少于算法B。

為了更好地對兩種并行算法結果進行分析，我們引入了并行加速比和并行效率對并行算法的性能進行評價，其定義如下［15］：

其中，p指使用的線程數；T1為串行算法運行時間，Tp為p個線程并行執行的時間，Sp即為并行加速比，Ep為并行效率。因此，Sp的理論值為p，而Ep的理論值為1，這里給出兩種算法的并行加速比和并行效率，如圖7。圖7（a）是加速比，虛線是其理論值p。隨著采用的線程數增多，導致系統開銷增大，兩種算法的加速比逐漸都遠離理論值，但很明顯隨著線程數增加，算法C開始逐漸優于算法B。如圖7（b）所示，并行效率的變化趨勢也是如此。當線程數為8時，算法B的并行效率約為0.49，相當于計算速度提高到串行算法的4倍；算法C的并行效率約為0.6，相當于計算速度提高到串行算法的5倍。

圖7 兩種算法的并行加速比和并行效率比較

算法C由于數據讀取單獨占用一個線程，以及臨界區導致的系統開銷，使其在線程數較少時的加速性能并不理想，但是隨著線程數增加，算法B的加速性能受限于IO瓶頸，算法C的優勢也隨之體現出來，當線程數大于6以后，再增加線程數，算法B加速性能的提升微乎其微，而算法C的加速性能仍能獲得一個相當可觀的提升。因而在實際應用中，可以將兩種算法結合起來，無論采用多少線程，都可以獲得一個相對可觀的并行效率。

6 結語

本文對基于CCD的側向散射激光雷達數據處理中的并行計算問題進行了研究。針對并行計算的重點與難點，設計了兩種并行算法，并采用OpenMP對其進行并行化，闡述了并行化過程的技術難點，并對并行結果進行數值測試與分析。分析結果表明，文中提出的兩種并行算法合理可行，結合起來后能充分利用不同性能的設備，提高側向激光雷達數據處理的運算速度，為激光雷達大氣探測提供了計算性能的保障。同時，側向激光雷達數據處理速度某種程度上仍受限于IO瓶頸，在后續的研究中，筆者將利用聚合IO技術或其他并行IO技術對數據處理性能進行進一步的提升，為進一步利用基于CCD的側向散射激光雷達探測大氣氣溶膠奠定基礎。