劉俊見(jiàn) 陶宗明
(1.陸軍軍官學(xué)院研究生管理大隊(duì) 合肥 230031)(2.陸軍軍官學(xué)院基礎(chǔ)部 合肥 230031)
大氣氣溶膠是指液體或固體微粒散布在大氣中形成的相對(duì)穩(wěn)定的懸浮體系,對(duì)人體健康環(huán)境和全球氣候都有一定的影響[1],是當(dāng)前大氣科學(xué)領(lǐng)域中的熱點(diǎn)問(wèn)題之一。在大氣環(huán)境監(jiān)測(cè)領(lǐng)域,準(zhǔn)確了解氣溶膠隨時(shí)空的分布規(guī)律具有十分重要的意義。
激光雷達(dá)以它精細(xì)的時(shí)間、空間和光譜分辨率、大的垂直跨度和高的探測(cè)精度很快便成為探測(cè)大氣氣溶膠空間分布的有力工具,被廣泛應(yīng)用于環(huán)境與大氣監(jiān)測(cè)等領(lǐng)域[2~6]?;贑CD的側(cè)向散射激光雷達(dá)是正在研究中的新技術(shù),它將發(fā)射裝置與接收裝置分兩處放置,解決了傳統(tǒng)后向散射激光雷達(dá)中的過(guò)渡區(qū)和盲區(qū)問(wèn)題,而且由于使用了側(cè)向技術(shù),其在近距離段具有極高的空間分辨率[7~10]。
為了讓側(cè)向散射激光雷達(dá)在白天也能工作,克服白天背景光過(guò)強(qiáng)的有效方法是減小曝光時(shí)間和多次曝光求信號(hào)的平均值。我們所用CCD的圖片的像素是3352*2532,大小約為16M,多次曝光(如300次)提取信號(hào)的平均值需要占用較多的計(jì)算時(shí)間,這對(duì)數(shù)據(jù)的實(shí)時(shí)處理造成一定的困難。
隨著多核處理器架構(gòu)被業(yè)界廣泛采用,通過(guò)并行計(jì)算縮短執(zhí)行時(shí)間已成為高性能計(jì)算領(lǐng)域使用最廣的方法[11]。OpenMP(Open Multi-Processing)是一種典型的共享內(nèi)存平臺(tái)下的編程API,支持跨平臺(tái)共享內(nèi)存方式的多線程并發(fā),其通過(guò)提供對(duì)并行算法的高層抽象描述,降低了并行編程的復(fù)雜性和難度[12]。
本文通過(guò)分析側(cè)向散射激光雷達(dá)數(shù)據(jù)處理流程的特點(diǎn),找出迫切需要采用并行計(jì)算提高效率的關(guān)鍵任務(wù)?;贠penMP標(biāo)準(zhǔn),設(shè)計(jì)并行優(yōu)化方案,實(shí)現(xiàn)側(cè)向散射激光雷達(dá)數(shù)據(jù)處理計(jì)算并行化,通過(guò)實(shí)驗(yàn)分析并檢驗(yàn)其并行效果,以期有效挖掘不同計(jì)算設(shè)備的潛能,為采用并行計(jì)算技術(shù)處理側(cè)向散射激光雷達(dá)數(shù)據(jù)提供一種高效、經(jīng)濟(jì)的實(shí)施方案。
激光雷達(dá)大氣探測(cè)的監(jiān)控周期一般為10分鐘,即每間隔10分鐘采集一組數(shù)據(jù)。對(duì)于基于CCD的側(cè)向散射激光雷達(dá),由于采集的圖像數(shù)據(jù)占用存儲(chǔ)空間龐大,以一張CCD圖像16M、每組300對(duì)圖像(每對(duì)為兩張圖片,用于減少背景光、干擾光)為例,白天一小時(shí)就要采集3600張(6*300*2),需要占用接近60G的硬盤空間,因此需要在一個(gè)周期內(nèi)完成該組數(shù)據(jù)的采集、處理、保存并刪除初始CCD圖像數(shù)據(jù),這對(duì)數(shù)據(jù)處理的效率提出了很高的要求。從側(cè)向散射激光雷達(dá)數(shù)據(jù)處理的需求出發(fā),計(jì)算主要集中在以下幾個(gè)方面,包括信號(hào)提取、配準(zhǔn)、反演、可視化顯示等運(yùn)算。
基于上述的側(cè)向散射激光雷達(dá)數(shù)據(jù)處理中的幾個(gè)關(guān)鍵任務(wù),下面對(duì)它們的并行需求作一個(gè)簡(jiǎn)要分析。在進(jìn)行反演計(jì)算時(shí),一般采取分像元處理的策略,由于各位置(或光束方向上各像元)之間的計(jì)算是沒(méi)有依賴關(guān)系的,因此,在多核環(huán)境下,可以同時(shí)啟動(dòng)多個(gè)進(jìn)程,每個(gè)進(jìn)程分別完成對(duì)應(yīng)某部分像元的反演計(jì)算,既能充分利用設(shè)備的系統(tǒng)資源,又避免了設(shè)計(jì)對(duì)應(yīng)的并行算法;可視化的主要目的是為了方便研究人員對(duì)原始數(shù)據(jù)做出正確解釋,相對(duì)于其他的處理任務(wù),其處理時(shí)間靈活,甚至可以在一天的觀測(cè)任務(wù)結(jié)束后再繪制當(dāng)天的氣溶膠后向散射系數(shù)時(shí)空分布圖;配準(zhǔn)的計(jì)算量相對(duì)較少,主要是循環(huán)及方差計(jì)算,直接在已有的串行代碼基礎(chǔ)上嵌入指令語(yǔ)句將其并行化就可以取得較好的加速效果。因而信號(hào)提取是側(cè)向散射激光雷達(dá)數(shù)據(jù)處理中迫切需要設(shè)計(jì)對(duì)應(yīng)并行算法的關(guān)鍵。
針對(duì)夜間圖像,信號(hào)提取主要指在減少背景光、干擾光的基礎(chǔ)上,通過(guò)高斯擬合去噪并提取對(duì)應(yīng)角寬度內(nèi)的散射光子數(shù)。減少背景光、干擾光主要通過(guò)連續(xù)拍攝曝光時(shí)間相同的兩張CCD相片[13],如圖1所示,(a)是包含所有光的CCD相片,(b)是缺少激光散射光束的CCD相片,將兩次拍攝的CCD對(duì)應(yīng)像元信號(hào)相減,獲得的結(jié)果如(c)所示,這就減少了背景光和干擾光的影響;提取散射光子數(shù)主要通過(guò)高斯擬合逐一計(jì)算沿光束方向的每個(gè)像元對(duì)應(yīng)的信號(hào)光子數(shù)與噪聲光子數(shù),從而得到光子數(shù)與位置(或光束方向上像元)的一一對(duì)應(yīng)關(guān)系。
圖1 減少背景光、干擾光
信號(hào)提取的難度主要在白天圖像的處理上,相對(duì)于夜間,白天作為主要背景光的日光太強(qiáng),曝光時(shí)間過(guò)長(zhǎng)會(huì)導(dǎo)致圖像過(guò)曝,因此需采取減少單張圖像曝光時(shí)間、多張圖像疊加的方式來(lái)獲取CCD圖像數(shù)據(jù)。為了減少局部誤差、獲得較高的信噪比,白天每次最少需要采集300對(duì)~500對(duì)的CCD圖像數(shù)據(jù),每對(duì)圖像都需要減少背景光、干擾光,去噪并提取散射光子數(shù),隨后將提取的散射光子數(shù)逐對(duì)逐像元進(jìn)行疊加求和,得到最終的結(jié)果。同時(shí)為了應(yīng)對(duì)系統(tǒng)崩潰、采集與處理不同步等意外情況,數(shù)據(jù)處理算法必須要有快速處理之前積壓的多組數(shù)據(jù)的能力,要能高效率地從上千張CCD圖像中提取出每個(gè)時(shí)段的信號(hào),這對(duì)數(shù)據(jù)處理的效率提出了更高的要求。
在側(cè)向散射激光雷達(dá)數(shù)據(jù)處理的實(shí)際情況中,由于不同情況下對(duì)數(shù)據(jù)精度及成本的雙重考慮,數(shù)據(jù)處理程序?qū)⑦\(yùn)行在不同的設(shè)備環(huán)境里,這些設(shè)備可能是雙核、4核甚至更多,同時(shí)由于超線程技術(shù)的應(yīng)用,某些型號(hào)的CPU可以同時(shí)執(zhí)行多重線程。同時(shí)對(duì)于不同的數(shù)據(jù)處理任務(wù),由于需要處理的數(shù)據(jù)量及循環(huán)次數(shù)不同,執(zhí)行該任務(wù)時(shí)需要的線程數(shù)也不同。因此需要根據(jù)設(shè)備性能的不同來(lái)自動(dòng)設(shè)置合適的線程數(shù)量,以滿足不同情況下的需求,使數(shù)據(jù)處理程序具有較強(qiáng)的可擴(kuò)展性,當(dāng)運(yùn)算量發(fā)生變化時(shí),仍能通過(guò)自動(dòng)設(shè)置使線程數(shù)量滿足要求。
通常認(rèn)為,在具體計(jì)算需要使用多少線程時(shí),主要需要考慮以下兩點(diǎn)[14]:
1)當(dāng)循環(huán)次數(shù)比較少時(shí),如果分成過(guò)多數(shù)量的線程來(lái)執(zhí)行,可能會(huì)使得總運(yùn)行時(shí)間高于較少線程或一個(gè)線程執(zhí)行的情況,并且會(huì)增加能耗。
2)如果設(shè)置的線程數(shù)量遠(yuǎn)大于CPU核數(shù)的話,那么存在著大量的任務(wù)切換和調(diào)度等開銷,也會(huì)降低整體效率。
由于不同數(shù)據(jù)處理任務(wù)的循環(huán)次數(shù)差距很大,夜間進(jìn)行信號(hào)提取時(shí),每組數(shù)據(jù)為300~500對(duì)CCD圖片,那么對(duì)每組圖片進(jìn)行信號(hào)提取需要進(jìn)行300~500次循環(huán);而進(jìn)行配準(zhǔn)計(jì)算時(shí)的循環(huán)次數(shù)只有10~30次,那么如何根據(jù)循環(huán)的次數(shù)和CPU線程數(shù)來(lái)動(dòng)態(tài)地設(shè)置線程的數(shù)量呢?通過(guò)分析側(cè)向散射激光雷達(dá)數(shù)據(jù)處理任務(wù)的特點(diǎn),確定了動(dòng)態(tài)設(shè)置線程數(shù)的需求如下:
1)多個(gè)線程運(yùn)行時(shí),由于現(xiàn)有CPU線程數(shù)一般不超過(guò)16,因此每個(gè)線程運(yùn)行的循環(huán)次數(shù)應(yīng)不低于總循環(huán)次數(shù)的十六分之一,同時(shí)不少于4次。
2)總的運(yùn)行線程數(shù)不超過(guò)CPU總線程數(shù),以避免任務(wù)切換開銷。
基于上文確定的需求,動(dòng)態(tài)設(shè)置線程數(shù)的程序流程圖如圖3所示。其中Num為CPU總線程數(shù),Run_num為設(shè)置的執(zhí)行線程數(shù)。
圖2 動(dòng)態(tài)設(shè)置線程數(shù)程序流程圖
實(shí)際編程中,將其編為一個(gè)獨(dú)立的功能函數(shù),其返回值即是針對(duì)此次循環(huán)應(yīng)設(shè)置的線程數(shù),每次并行化循環(huán)開始前調(diào)用該函數(shù)來(lái)獲取合適的線程數(shù)量,并使用num_threads子句設(shè)置線程數(shù)。
并行算法設(shè)計(jì)常見(jiàn)的模式有數(shù)據(jù)分解模式、分治模式、流水線模式、任務(wù)并行模式、任務(wù)圖調(diào)度模式、動(dòng)態(tài)任務(wù)調(diào)度模式等,針對(duì)夜間信號(hào)提取這一關(guān)鍵任務(wù),從其數(shù)據(jù)處理流程特點(diǎn)與需求出發(fā),選取了兩種最適合的模式分別進(jìn)行了并行算法的設(shè)計(jì)。
該任務(wù)的串行算法A可以簡(jiǎn)化為三層循環(huán),如下所示,內(nèi)層循環(huán)完成一對(duì)CCD圖像沿光束方向上各像元信號(hào)的提取,output即為提取出的序號(hào)為j的像元的散射光子數(shù);第二層循環(huán)完成數(shù)量為amount的一組CCD圖像的信號(hào)提取,每對(duì)圖像提取出的散射光子數(shù)進(jìn)行累加求和并存儲(chǔ)在數(shù)組a(j)中;外層循環(huán)是針對(duì)因?yàn)橐馔舛逊e的多組數(shù)據(jù),find函數(shù)采用遞歸策略掃描文件夾內(nèi)所有的CCD圖像路徑,返回值find()為圖像對(duì)數(shù)。
數(shù)據(jù)分解模式即是將數(shù)據(jù)分解為N個(gè)獨(dú)立的數(shù)據(jù)子塊,每個(gè)線程處理其中的一個(gè)或多個(gè)數(shù)據(jù)塊。由于每對(duì)CCD圖像之間都是相互獨(dú)立的,符合數(shù)據(jù)分解模式的要求,因此選擇其作為第一種方法完成并行算法的設(shè)計(jì),此方法記為算法B。
由于算法A為三層循環(huán)結(jié)構(gòu),且最外層循環(huán)次數(shù)一般較少,若對(duì)外層循環(huán)并行化,實(shí)際創(chuàng)建的線程數(shù)很可能小于CPU的總線程數(shù),不能很好地發(fā)揮CPU性能,會(huì)大大降低并行算法的效率;同時(shí)很難通過(guò)對(duì)外層循環(huán)進(jìn)行調(diào)度使內(nèi)層循環(huán)達(dá)到負(fù)載均衡。針對(duì)上述問(wèn)題,本文在進(jìn)行并行算法設(shè)計(jì)時(shí),首先將外層循環(huán)和第二層循環(huán)進(jìn)行合并,合并后的兩層循環(huán)結(jié)構(gòu)如下所示。
其中number為采集完成的圖像組數(shù),計(jì)算流程如圖3所示,隨后在內(nèi)層循環(huán)通過(guò)判斷圖像名的標(biāo)志位,將提取出的散射光子數(shù)按組別分別累加。
圖3 計(jì)算圖像組數(shù)流程圖
針對(duì)合并后的兩層循環(huán),若對(duì)內(nèi)層循環(huán)進(jìn)行并行化,就必須要解決a(j)等數(shù)組的同時(shí)操作問(wèn)題。內(nèi)層循環(huán)中,每個(gè)線程完成信號(hào)提取后,都需要和a(j)累加,因此每個(gè)線程都要對(duì)a(j)進(jìn)行讀寫操作。對(duì)這類問(wèn)題,OpenMP提供了臨界區(qū)、數(shù)據(jù)規(guī)約等方式來(lái)進(jìn)行線程之間的同步,但是不論哪種方法都會(huì)在一定程度上增加系統(tǒng)開銷。本文選擇只對(duì)外層循環(huán)進(jìn)行并行化,避開內(nèi)層循環(huán)的鎖競(jìng)爭(zhēng),經(jīng)過(guò)比較,該方法的加速性能與采用數(shù)據(jù)規(guī)約基本一致,并優(yōu)于采用臨界區(qū)的方法。
雖然需要處理的圖像對(duì)數(shù)M難以被線程數(shù)N整除,CCD圖像數(shù)據(jù)無(wú)法被劃分為計(jì)算量相同的N個(gè)數(shù)據(jù)子塊,即不使用size參數(shù)時(shí)不同線程實(shí)際分配的迭代次數(shù)會(huì)相差1,但相對(duì)于每個(gè)線程分配的任務(wù)總量而言,某一個(gè)或某幾個(gè)線程多處理一對(duì)圖像幾乎不會(huì)對(duì)總體加速性能產(chǎn)生影響,因此本文采用靜態(tài)調(diào)度方法實(shí)現(xiàn)并行算法的負(fù)載均衡,關(guān)鍵代碼如下。
由于信號(hào)提取首先需要從硬盤中讀取大量的數(shù)據(jù),很大程度上存在著IO瓶頸,本文選擇流水線模式作為第二種方法對(duì)并行算法進(jìn)行優(yōu)化,此算法記為算法C。流水線模式借鑒工業(yè)生產(chǎn)中的流水線思想,將一個(gè)數(shù)據(jù)處理流程分解為幾個(gè)步驟,每個(gè)步驟采用一個(gè)或多個(gè)線程來(lái)進(jìn)行處理,在處理具有IO瓶頸的數(shù)據(jù)處理流程有較大優(yōu)勢(shì)。
針對(duì)信號(hào)提取這一流程,我們可以將其分解為如圖4所示的三個(gè)步驟。
圖4 對(duì)信號(hào)提取過(guò)程進(jìn)行流水線分解
串行算法采用一個(gè)線程依次執(zhí)行上述的三個(gè)步驟;而采用流水線模式進(jìn)行并行實(shí)現(xiàn)時(shí),分別使用一個(gè)或多個(gè)線程來(lái)讀取CCD圖像數(shù)據(jù),減少背景光、干擾光,以及提取散射光子數(shù)。這樣就使得三個(gè)步驟的處理并行進(jìn)行,提高了處理效率,如圖5所示。在并行實(shí)現(xiàn)的過(guò)程中,當(dāng)讀取數(shù)據(jù)線程獲取了一部分CCD圖像數(shù)據(jù)后,后續(xù)的線程就可以開始進(jìn)行數(shù)據(jù)處理了。
圖5 對(duì)信號(hào)提取過(guò)程進(jìn)行并行處理
但是從上述的分析中也可以看出,運(yùn)用流水線模式對(duì)信號(hào)提取過(guò)程進(jìn)行并行實(shí)現(xiàn)時(shí),數(shù)據(jù)從上一個(gè)步驟傳遞到下一個(gè)步驟時(shí),這兩個(gè)步驟是并行執(zhí)行的,因而存在數(shù)據(jù)競(jìng)爭(zhēng),需要使用同步操作對(duì)數(shù)據(jù)進(jìn)行保護(hù),針對(duì)此問(wèn)題,本文主要采用臨界區(qū)的方法來(lái)實(shí)現(xiàn)同步操作。
并行實(shí)現(xiàn)時(shí),為避免線程資源的浪費(fèi)以及非線性讀取對(duì)讀入速度的影響,筆者首先指定了一個(gè)線程來(lái)讀取數(shù)據(jù)。在實(shí)現(xiàn)后續(xù)兩個(gè)步驟的并行化時(shí),筆者發(fā)現(xiàn)很難將這兩個(gè)步驟分開實(shí)現(xiàn)并行化,主要問(wèn)題在于以下兩點(diǎn):
1)程序設(shè)計(jì)時(shí)被要求能在不同性能的設(shè)備上高效運(yùn)行,不同設(shè)備可供使用的線程資源差距明顯,很難對(duì)其進(jìn)行線程分配。
2)上文中提到了數(shù)據(jù)保護(hù)的問(wèn)題,并行時(shí)每增加一個(gè)步驟,實(shí)際上也增加了用于數(shù)據(jù)同步的系統(tǒng)開銷。
在進(jìn)行了多次試驗(yàn)后,筆者決定將后續(xù)兩個(gè)步驟合并,共用數(shù)據(jù)處理線程來(lái)進(jìn)行并行化,結(jié)果顯示其加速性能要優(yōu)于分開并行化的方案。實(shí)際上,方法二主要是在方法一的基礎(chǔ)上對(duì)數(shù)據(jù)讀取進(jìn)行了一定的優(yōu)化,數(shù)據(jù)處理部分的并行化與方法一相同。
按照第4節(jié)中的兩種算法,對(duì)針對(duì)夜間信號(hào)提取這一關(guān)鍵與難點(diǎn)進(jìn)行并行化,并運(yùn)用型號(hào)為AlienwareM14xR1的筆記本電腦進(jìn)行測(cè)試,其CPU為主頻2.20G的i7-2670QM,內(nèi)存16G,操作系統(tǒng)為Windows7,編程環(huán)境為VS2015。從300對(duì)CCD圖像中提取散射光子數(shù),算法B和算法C的總運(yùn)行時(shí)間見(jiàn)如圖6所示,其中由于算法C無(wú)法單線程執(zhí)行,其線程數(shù)為1時(shí)直接執(zhí)行算法A(即串行算法)。
圖6 算法B和算法C運(yùn)行時(shí)間比較
圖6的橫軸為采用的線程數(shù),分別從1到8;縱軸為多線程模式下的該流程運(yùn)行時(shí)間??梢钥闯?,采用線程數(shù)較少時(shí),算法B運(yùn)行時(shí)間要比算法C少,而隨著線程數(shù)增加算法C與算法B運(yùn)行時(shí)間差距逐漸縮小,線程數(shù)為4時(shí),兩種算法的運(yùn)行時(shí)間基本相同,當(dāng)線程數(shù)大于4后,算法C的運(yùn)行時(shí)間開始少于算法B。
為了更好地對(duì)兩種并行算法結(jié)果進(jìn)行分析,我們引入了并行加速比和并行效率對(duì)并行算法的性能進(jìn)行評(píng)價(jià),其定義如下[15]:
其中,p指使用的線程數(shù);T1為串行算法運(yùn)行時(shí)間,Tp為p個(gè)線程并行執(zhí)行的時(shí)間,Sp即為并行加速比,Ep為并行效率。因此,Sp的理論值為p,而Ep的理論值為1,這里給出兩種算法的并行加速比和并行效率,如圖7。圖7(a)是加速比,虛線是其理論值p。隨著采用的線程數(shù)增多,導(dǎo)致系統(tǒng)開銷增大,兩種算法的加速比逐漸都遠(yuǎn)離理論值,但很明顯隨著線程數(shù)增加,算法C開始逐漸優(yōu)于算法B。如圖7(b)所示,并行效率的變化趨勢(shì)也是如此。當(dāng)線程數(shù)為8時(shí),算法B的并行效率約為0.49,相當(dāng)于計(jì)算速度提高到串行算法的4倍;算法C的并行效率約為0.6,相當(dāng)于計(jì)算速度提高到串行算法的5倍。
圖7 兩種算法的并行加速比和并行效率比較
算法C由于數(shù)據(jù)讀取單獨(dú)占用一個(gè)線程,以及臨界區(qū)導(dǎo)致的系統(tǒng)開銷,使其在線程數(shù)較少時(shí)的加速性能并不理想,但是隨著線程數(shù)增加,算法B的加速性能受限于IO瓶頸,算法C的優(yōu)勢(shì)也隨之體現(xiàn)出來(lái),當(dāng)線程數(shù)大于6以后,再增加線程數(shù),算法B加速性能的提升微乎其微,而算法C的加速性能仍能獲得一個(gè)相當(dāng)可觀的提升。因而在實(shí)際應(yīng)用中,可以將兩種算法結(jié)合起來(lái),無(wú)論采用多少線程,都可以獲得一個(gè)相對(duì)可觀的并行效率。
本文對(duì)基于CCD的側(cè)向散射激光雷達(dá)數(shù)據(jù)處理中的并行計(jì)算問(wèn)題進(jìn)行了研究。針對(duì)并行計(jì)算的重點(diǎn)與難點(diǎn),設(shè)計(jì)了兩種并行算法,并采用OpenMP對(duì)其進(jìn)行并行化,闡述了并行化過(guò)程的技術(shù)難點(diǎn),并對(duì)并行結(jié)果進(jìn)行數(shù)值測(cè)試與分析。分析結(jié)果表明,文中提出的兩種并行算法合理可行,結(jié)合起來(lái)后能充分利用不同性能的設(shè)備,提高側(cè)向激光雷達(dá)數(shù)據(jù)處理的運(yùn)算速度,為激光雷達(dá)大氣探測(cè)提供了計(jì)算性能的保障。同時(shí),側(cè)向激光雷達(dá)數(shù)據(jù)處理速度某種程度上仍受限于IO瓶頸,在后續(xù)的研究中,筆者將利用聚合IO技術(shù)或其他并行IO技術(shù)對(duì)數(shù)據(jù)處理性能進(jìn)行進(jìn)一步的提升,為進(jìn)一步利用基于CCD的側(cè)向散射激光雷達(dá)探測(cè)大氣氣溶膠奠定基礎(chǔ)。