王興達(dá) 劉雪峰

1(中國(guó)科學(xué)院國(guó)家空間科學(xué)中心 北京 100190)2(中國(guó)科學(xué)院大學(xué) 北京 100049)

0 引 言

近年來(lái)，壓縮感知(CS)理論得到了越來(lái)越多的關(guān)注。單光子成像是利用壓縮感知理論的一個(gè)典型應(yīng)用。原理是先將物體成像在數(shù)字微鏡陣列上，利用測(cè)量矩陣的調(diào)制作用和單光子探測(cè)器的測(cè)量值，就能夠在低采樣率條件下利用單點(diǎn)探測(cè)器取得良好的成像效果[1]。在實(shí)驗(yàn)中起調(diào)制作用的測(cè)量矩陣是非常重要的一環(huán)，通常在理想的單光子成像實(shí)驗(yàn)中需要30%～50%采樣率的測(cè)量矩陣才能夠恢復(fù)出效果比較好的圖像[2]。對(duì)于高分辨率的單光子成像實(shí)驗(yàn)，所需測(cè)量矩陣數(shù)量可達(dá)百萬(wàn)級(jí)別。普通計(jì)算機(jī)利用MATLAB等軟件生成一個(gè)FHD(1 920×1 080)分辨率的全采樣率測(cè)量矩陣通常需要20小時(shí)以上的時(shí)間，大大降低單光子成像實(shí)驗(yàn)的效率，成為單光子成像實(shí)驗(yàn)中的一個(gè)痛點(diǎn)[3]。

近幾年隨著以Apache Spark為代表的分布式計(jì)算技術(shù)的發(fā)展為解決這一痛點(diǎn)帶來(lái)了曙光。Spark平臺(tái)本身是一個(gè)分布式的計(jì)算框架，通常用于大規(guī)模的數(shù)據(jù)處理[4]，本文通過(guò)Spark中的parallel算子生成簡(jiǎn)單RDD，然后通過(guò)對(duì)該RDD的MapPartition操作能夠?qū)y(cè)量矩陣生成和評(píng)估任務(wù)均勻分配到各個(gè)機(jī)器節(jié)點(diǎn)的Executor上進(jìn)行計(jì)算作業(yè)，利用Spark平臺(tái)調(diào)度集群的

計(jì)算性能。實(shí)驗(yàn)證明該方法具有良好的加速比和拓展性，滿足了單光子成像實(shí)驗(yàn)中對(duì)于測(cè)量矩陣的頻繁生成需求，大幅降低了成像實(shí)驗(yàn)的時(shí)間成本。

1 單光子成像與Spark平臺(tái)

1.1 壓縮感知理論

壓縮感知(Compressed sensing)，也被稱為壓縮采樣(Compressive sampling)或稀疏采樣(Sparse sampling)，是一種尋找欠定線性系統(tǒng)的稀疏解的技術(shù)[5]。壓縮感知理論指出：只要信號(hào)是可壓縮的或在某個(gè)變換域是稀疏的[6]，那么就可以用一個(gè)與變換基不相關(guān)的觀測(cè)矩陣將變換所得高維信號(hào)投影到一個(gè)低維空間上[7]，然后通過(guò)求解一個(gè)優(yōu)化問(wèn)題就可以從這些少量的投影中以高概率重構(gòu)出原信號(hào)，可以證明這樣的投影包含了重構(gòu)信號(hào)的足夠信息[8]。在過(guò)去的幾年內(nèi)，壓縮感知作為一個(gè)新的采樣理論，它可以在遠(yuǎn)小于Nyquist 采樣率的條件下獲取信號(hào)的離散樣本，保證信號(hào)的無(wú)失真重建[9]。

1.2 單光子成像

單光子成像是壓縮感知理論的一個(gè)典型應(yīng)用。借鑒計(jì)算成像中的高通量測(cè)量的思想，如圖1所示，首先用光源打在物體上，通過(guò)成像透鏡將物體的像成在可調(diào)制的數(shù)字微鏡陣列(DMD)上，再利用測(cè)量矩陣對(duì)DMD進(jìn)行0-1的掩膜調(diào)制，每個(gè)測(cè)量矩陣都隨機(jī)調(diào)制圖像的部分像素點(diǎn)，再用一個(gè)收集透鏡將這些像素點(diǎn)的光路聚集到一個(gè)探測(cè)點(diǎn)上，利用單光子探測(cè)技術(shù)對(duì)其進(jìn)行測(cè)量，得到光子計(jì)數(shù)測(cè)量值[10]。最后，通過(guò)TVAL3等壓縮感知恢復(fù)算法及測(cè)量矩陣和測(cè)量值就能進(jìn)行圖像恢復(fù)，這樣就能夠利用單點(diǎn)探測(cè)器取得良好的成像效果[11]。根據(jù)壓縮感知理論的成像經(jīng)驗(yàn)，每次成像實(shí)驗(yàn)大約需要30%～50%的采樣率才能取得比較好的成像效果。測(cè)量矩陣的數(shù)目與采樣率的關(guān)系如下：

matrix_num=width×height×sample_rate

圖1 單光子成像原理圖

在高分辨率的情況下，所需的測(cè)量矩陣數(shù)目往往是百萬(wàn)級(jí)別的，普通計(jì)算機(jī)利用MATLAB生成一次FHD分辨率的測(cè)量矩陣大約需要20小時(shí)，非常影響單光子成像實(shí)驗(yàn)的效率。

1.3 Spark平臺(tái)介紹

Spark 是一個(gè)分布式計(jì)算框架，專為大規(guī)模數(shù)據(jù)處理而設(shè)計(jì)，具有快速且通用的特點(diǎn)[12]。Spark原本是加州大學(xué)伯克利分校的AMP實(shí)驗(yàn)室開源的類似于Hadoop MapReduce的通用并行框架，它擁有Hadoop MapReduce所具有的優(yōu)點(diǎn)，但不同于MapReduce的是Spark中間的輸出結(jié)果可以保存在內(nèi)存中，從而不再需要讀寫HDFS，因此能夠獲得比MapReduce更快的大數(shù)據(jù)處理速度[13]。圖2展示了Spark的基本框架。用戶通過(guò)Driver向Master注冊(cè)申請(qǐng)資源，由Master通過(guò)各個(gè)worker的心跳包獲取集群當(dāng)前的資源狀況，找到合適的資源給本任務(wù)，然后在各個(gè)worker上啟動(dòng)Executor進(jìn)程去運(yùn)行用戶提交任務(wù)中的每一個(gè)task，Executor向Driver通過(guò)心跳包報(bào)告運(yùn)行狀態(tài)，直到作業(yè)完成。分布式計(jì)算技術(shù)的瓶頸往往在與集群的網(wǎng)絡(luò)IO，想提高計(jì)算性能應(yīng)該盡可能地避免shuffle的過(guò)程出現(xiàn)，而測(cè)量矩陣的生成和校驗(yàn)是非常獨(dú)立的過(guò)程，不需要與其他的節(jié)點(diǎn)進(jìn)行通信或數(shù)據(jù)交互[14],因此非常適合于spark這種分布式計(jì)算框架,能夠非常充分地利用集群機(jī)器的計(jì)算性能快速生成和評(píng)估測(cè)量矩陣。

圖2 Spark框架的工作流程

2 分布式測(cè)量矩陣生成算法

2.1 算法設(shè)計(jì)

測(cè)量矩陣生成分為矩陣生成，矩陣評(píng)估和數(shù)據(jù)取回三個(gè)階段。通過(guò)spark-submit腳本中的參數(shù)并配置本次任務(wù)的矩陣類型、分辨率和采樣率等。Spark的計(jì)算框架通常用于分布式的處理數(shù)據(jù)，如果想使用該框架進(jìn)行數(shù)據(jù)生成可以通過(guò)Spark中內(nèi)置的parallel算子生成簡(jiǎn)單RDD，然后對(duì)RDD使用Spark中的MapPartition算子，MapPartition算子是Map算子的一個(gè)變種，雖然它們都可進(jìn)行分區(qū)的并行處理，但兩者的主要區(qū)別是調(diào)用的粒度不一樣：Map的輸入變換函數(shù)是應(yīng)用于RDD中每個(gè)元素，而MapPartition的輸入函數(shù)是應(yīng)用于每個(gè)分區(qū)[15]。通過(guò)Spark中的調(diào)度系統(tǒng)將本次矩陣生成與評(píng)估任務(wù)均勻地分布在各個(gè)節(jié)點(diǎn)上，在每個(gè)節(jié)點(diǎn)根據(jù)配置的參數(shù)進(jìn)行測(cè)量矩陣的生成作業(yè)。對(duì)于每個(gè)生成的測(cè)量矩陣需要在本地進(jìn)行矩陣質(zhì)量的評(píng)估，以隨機(jī)測(cè)量矩陣為例，一般需要做計(jì)算矩陣的隨機(jī)偏差，在偏差允許范圍內(nèi)的矩陣才會(huì)被認(rèn)為是合格的矩陣而保留下來(lái)。對(duì)于不合格的矩陣，則會(huì)進(jìn)行丟棄然后重新生成一個(gè)新的測(cè)量矩陣，為了進(jìn)行對(duì)比實(shí)驗(yàn)，在進(jìn)行生成與評(píng)估作業(yè)中會(huì)進(jìn)行數(shù)據(jù)統(tǒng)計(jì)(包括生成矩陣數(shù)目、矩陣質(zhì)量和矩陣保留個(gè)數(shù)等)。因?yàn)闇y(cè)量矩陣本身是0-1矩陣，為節(jié)省存儲(chǔ)空間并沒(méi)有將結(jié)果寫入HDFS中，而是通過(guò)Spark中的collect算子將已生成好的測(cè)量矩陣和統(tǒng)計(jì)數(shù)據(jù)拉回提交作業(yè)的Driver端，通過(guò)二進(jìn)制文件的方式寫入本地，供后續(xù)進(jìn)行單光子成像實(shí)驗(yàn)使用。圖3展示了一次完整的測(cè)量矩陣的生成和評(píng)估作業(yè)的流程。

圖3 算法流程圖

2.2 工程化實(shí)現(xiàn)

工程化實(shí)現(xiàn)過(guò)程主要是利用Spark中的編程模型，主要用到的算子包括Spark中的mapPartition、parallel、collect等，其算法流程的偽代碼如算法1所示。

算法1 測(cè)量矩陣生成 輸入:矩陣大小,節(jié)點(diǎn)數(shù),矩陣數(shù)目 輸出:經(jīng)過(guò)評(píng)估合格的測(cè)量矩陣二進(jìn)制文件1. val sc=new SparkContext()2. val config=sc.getConf.get()3. val partitionNum=sc.getConf.get()4. val matrixNumPerPartition=matrixNum / partitionNum5. val matrix=sc.parallelize(0 until partition,partition).mapPartitions {part=> for(0 to matrixNumPerPartition){ generate matrixes if(evaluate matrixes is qualified) save qualified matrix count++ else regenerate unqualified matrix count++ } Calculate matrix save rate }6. val result=matrix.collect()7. val resultFile=new FileOutputStream()8. resultFile.write(result)

3 實(shí)驗(yàn)和結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

由于實(shí)驗(yàn)室單光子成像實(shí)驗(yàn)的需要，在實(shí)驗(yàn)室搭建了8臺(tái)服務(wù)器搭建的物理集群，并且安裝配置好了Spark環(huán)境。為了便于進(jìn)行對(duì)比實(shí)驗(yàn)，單機(jī)實(shí)驗(yàn)采用的機(jī)器環(huán)境和集群中單節(jié)點(diǎn)的硬件完全相同，表1中列出了單個(gè)節(jié)點(diǎn)機(jī)器的物理硬件配置，表2中列出了集群機(jī)器的主要軟件環(huán)境版本信息。

表1 Spark集群?jiǎn)喂?jié)點(diǎn)硬件配置信息

表2 Spark集群?jiǎn)喂?jié)點(diǎn)軟件配置信息

3.2 評(píng)估指標(biāo)

本文的實(shí)驗(yàn)選擇了單機(jī)、2節(jié)點(diǎn)、4節(jié)點(diǎn)、8節(jié)點(diǎn)等4組進(jìn)行對(duì)比的橫向?qū)Ρ龋x擇了三種不同的分辨率進(jìn)行縱向?qū)Ρ?，測(cè)量矩陣選擇了相對(duì)簡(jiǎn)單的隨機(jī)測(cè)量矩陣。主要選取運(yùn)行時(shí)間、矩陣評(píng)估存留率、加速比和拓展性作為評(píng)價(jià)指標(biāo)。各評(píng)價(jià)指標(biāo)說(shuō)明如下：

(1) 運(yùn)行時(shí)間(Runtime)：該指標(biāo)是本次實(shí)驗(yàn)的主要目的指標(biāo)，運(yùn)行時(shí)間指從提交作業(yè)成功到測(cè)量矩陣的二進(jìn)制文件寫入硬盤完畢所需的總時(shí)間。

(2) 矩陣評(píng)估留存率(Matrix Save Rate)：該指標(biāo)是衡量矩陣生成質(zhì)量的指標(biāo)，其值定義為：

(3) 加速比(Speedup)：該指標(biāo)主要是用來(lái)驗(yàn)證并行算法的效率，根據(jù)阿姆達(dá)爾定律，其值在理想的狀態(tài)下通常被定義為：

(4) 可拓展性(Extension)：該指標(biāo)主要反映出集群節(jié)點(diǎn)的變化對(duì)該并行算法的性能影響大小，可以通過(guò)此指標(biāo)預(yù)判集群數(shù)目與該算法的效率匹配性。

3.3 實(shí)驗(yàn)分析

為了驗(yàn)證以上的實(shí)驗(yàn)指標(biāo)，分別選擇分辨率在512×512、1 024×768、1 920×1 080下進(jìn)行標(biāo)準(zhǔn)隨機(jī)測(cè)量矩陣算法生成進(jìn)行實(shí)驗(yàn)。

實(shí)驗(yàn)1本實(shí)驗(yàn)對(duì)比了不同節(jié)點(diǎn)數(shù)N對(duì)于生成隨機(jī)測(cè)量矩陣的運(yùn)行時(shí)間(單位：min)，實(shí)驗(yàn)數(shù)據(jù)如表3所示。

表3 運(yùn)行時(shí)間實(shí)驗(yàn)結(jié)果

從表中的實(shí)驗(yàn)數(shù)據(jù)的對(duì)比來(lái)看，可以看出隨著節(jié)點(diǎn)數(shù)的增加，相同分辨率下測(cè)量矩陣的生成時(shí)間在減小，大致呈現(xiàn)線性關(guān)系；測(cè)量矩陣的生成時(shí)間隨著分辨率的提高而大幅度增加，呈現(xiàn)倍數(shù)關(guān)系，基本符合預(yù)期。

實(shí)驗(yàn)2矩陣評(píng)估存留率是指生成的測(cè)量矩陣經(jīng)過(guò)評(píng)估算法之后合格的比例，實(shí)驗(yàn)以常用的隨機(jī)測(cè)量矩陣為例，高分辨情況下選擇隨機(jī)偏差小于0.001的矩陣為合格矩陣，保存到最后的測(cè)量矩陣結(jié)果中，0-1隨機(jī)測(cè)量矩陣的隨機(jī)偏差通常用以下公式計(jì)算：

式中：pos_num是矩陣中正元素的個(gè)數(shù)，neg_num是矩陣中非正元素的個(gè)數(shù)。隨機(jī)測(cè)量矩陣的隨機(jī)偏差一般會(huì)隨著測(cè)量矩陣分辨率的提高而降低。

矩陣評(píng)估存留率實(shí)驗(yàn)結(jié)果如表4所示。

表4 矩陣評(píng)估存留率實(shí)驗(yàn)結(jié)果

可以看出，隨著節(jié)點(diǎn)數(shù)的增加，矩陣評(píng)估保留率一直表現(xiàn)比較穩(wěn)定，沒(méi)有顯著有趨勢(shì)性的變化，說(shuō)明利用Spark進(jìn)行分布式的測(cè)量矩陣生成依然能夠獲得與單機(jī)版測(cè)量矩陣生成任務(wù)質(zhì)量相近的矩陣；隨著測(cè)量矩陣分辨率的提高，矩陣評(píng)估存留率會(huì)逐漸提高，且與單機(jī)版實(shí)驗(yàn)的指標(biāo)保持一致。

實(shí)驗(yàn)3計(jì)算不同節(jié)點(diǎn)數(shù)目下的加速比關(guān)系繪制折線圖，如圖4所示。

圖4 不同節(jié)點(diǎn)數(shù)下的加速比

從圖中可以看出，利用Spark框架生成測(cè)量矩陣的過(guò)程中，算法的加速比基本是接近線性的，隨著分辨率的增加，數(shù)據(jù)規(guī)模成倍的增加，加速比也沒(méi)有因?yàn)閿?shù)據(jù)分散后，最后從各個(gè)節(jié)點(diǎn)收集數(shù)據(jù)的時(shí)間增加而出現(xiàn)明顯下降。這是因?yàn)镾park這種運(yùn)行在JVM上的平臺(tái)，隨著數(shù)據(jù)在各個(gè)節(jié)點(diǎn)上的分散，單個(gè)節(jié)點(diǎn)所需的內(nèi)存按比例下降，JVM中消耗在內(nèi)存回收(GC)的時(shí)間也會(huì)逐漸減少了。說(shuō)明該算法有非常良好的加速比，可以期待該算法在未來(lái)高分辨測(cè)量矩陣生成中也具有非常好的表現(xiàn)。

實(shí)驗(yàn)4可拓展性分析。根據(jù)實(shí)驗(yàn)1的數(shù)據(jù)將集群使用的節(jié)點(diǎn)數(shù)和作業(yè)的運(yùn)行時(shí)間作折線圖，如圖5所示。

圖5 擴(kuò)展性實(shí)驗(yàn)結(jié)果圖

由圖5可以看出，在以上三個(gè)分辨率的測(cè)量矩陣生成實(shí)驗(yàn)中，運(yùn)行時(shí)間隨著節(jié)點(diǎn)數(shù)增加明顯下降，基本呈現(xiàn)線性關(guān)系。實(shí)驗(yàn)說(shuō)明，該分布式測(cè)量矩陣生成算法具有良好的可擴(kuò)展性。

4 結(jié) 語(yǔ)

傳統(tǒng)利用MATLAB等軟件工具生成測(cè)量矩陣的算法在面對(duì)高分辨率或高采樣率等數(shù)據(jù)規(guī)模較大的情況時(shí)，完整生成一次測(cè)量矩陣所需的時(shí)間成本往往非常巨大，嚴(yán)重影響了成像實(shí)驗(yàn)的效率。通過(guò)Spark分布式計(jì)算框架可以為測(cè)量矩陣的生成和評(píng)估提供可靠、簡(jiǎn)單、有效的解決方案，大大縮短了測(cè)量矩陣的生成時(shí)間，為調(diào)試測(cè)量矩陣和成像實(shí)驗(yàn)提供了有力支撐。實(shí)驗(yàn)表明，利用Spark平臺(tái)通過(guò)分布式的生成算法可以近似線性的縮減生成時(shí)間，測(cè)量矩陣質(zhì)量基本與單機(jī)算法相同，并且可拓展性良好，在可預(yù)見的情況下能夠支撐更大分辨率的單光子成像實(shí)驗(yàn)。