亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法

        2021-09-18 06:22:04王周愷馬維綱王懷軍
        計算機應(yīng)用 2021年9期
        關(guān)鍵詞:并行算法壓縮算法監(jiān)測數(shù)據(jù)

        王周愷,張 炯,馬維綱,王懷軍

        (西安理工大學(xué)計算機科學(xué)與工程學(xué)院,西安 710048)

        (*通信作者電子郵箱zkwang@xaut.edu.cn)

        0 引言

        為保證高速列車安全、有效地運行,需要在列車運行過程中利用各種傳感器,通過鐵路綜合數(shù)字移動通信系統(tǒng)(Global System for Mobile Communications-Railway,GSM-R),對列車的運行時各部件的狀態(tài)進(jìn)行監(jiān)測[1]。遵照4 級中國列車控制系統(tǒng)(Chinese Train Control System-4,CTCS-4)的設(shè)計要求,各類車載傳感器在列車運行時,收集列車車廂及關(guān)鍵部件的實時數(shù)據(jù)狀況,包括速度、功率、風(fēng)力、濕度等;再采用變長編碼技術(shù)(Variable Length Coding,VLC)對收集的數(shù)據(jù)進(jìn)行壓縮,最后將壓縮數(shù)據(jù)通過GSM-R 傳輸并存儲于控制中心;相應(yīng)地,工作人員如果需要分析列車狀態(tài),則先對數(shù)據(jù)進(jìn)行解壓縮,在此基礎(chǔ)上,再對解壓縮結(jié)果進(jìn)行分析,從而發(fā)現(xiàn)列車運行中可能產(chǎn)生的故障問題,并及時修復(fù)故障,避免潛在風(fēng)險的發(fā)生[2]。

        然而,由于采用了變長編碼技術(shù)壓縮數(shù)據(jù),針對高速列車監(jiān)測數(shù)據(jù)的分析效率通常較低,這是因為采用變長編碼技術(shù)的數(shù)據(jù)壓縮方法通常先將數(shù)據(jù)進(jìn)行等長劃分,再將劃分結(jié)果按照頻次排序并利用哈夫曼樹進(jìn)行編碼,從而獲得更高的壓縮比[3];但這種利用變長編碼技術(shù)壓縮的數(shù)據(jù)由大小不同的數(shù)據(jù)塊組成,且塊間邊界難以確定。所以目前針對此類數(shù)據(jù)的解壓縮方法通常是從數(shù)據(jù)的起始位置開始,按照各數(shù)據(jù)塊的組成順序,從頭到尾依次對數(shù)據(jù)進(jìn)行逐塊解壓縮[4]。而這樣的串行解壓縮過程亦無法被并行化,因為在當(dāng)前數(shù)據(jù)塊未解壓縮之前,其后續(xù)數(shù)據(jù)塊的起始位置無法得知,因此,當(dāng)前針對高速列車監(jiān)測數(shù)據(jù)的分析過程受變長編碼解壓縮算法的影響,效率較低[5],難以滿足在春運等高負(fù)荷環(huán)境下對海量監(jiān)測數(shù)據(jù)及時處理的需求[6]。

        為解決傳統(tǒng)串行解壓縮算法無法高效處理高速監(jiān)測數(shù)據(jù)的解壓縮問題,基于針對變長編碼壓縮數(shù)據(jù)的結(jié)構(gòu)研究,本文以多核領(lǐng)域常用的推測并行技術(shù)作為手段,提出一種面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法。該方法使用推測手段消解壓縮數(shù)據(jù)的組成順序?qū)鈮嚎s算法執(zhí)行流程的影響,使壓縮數(shù)據(jù)的處理過程得以并行化;然后在通用大數(shù)據(jù)分析引擎Apache Spark 上實現(xiàn)并行流程,借助分布式計算框架提供的強大算力,極大地縮短數(shù)據(jù)解壓縮需要的時間,為高速列車監(jiān)測數(shù)據(jù)的解壓縮提供高效可靠的新方法,從而進(jìn)一步縮短針對高速列車監(jiān)測數(shù)據(jù)的分析時間,提高針對高速列車監(jiān)測數(shù)據(jù)的處理效率。

        1 動機

        為保證高速列車的安全、穩(wěn)定運行,按照CTCS-4 列控系統(tǒng)設(shè)計要求,列車在車廂內(nèi)部和各個關(guān)鍵部件處安裝不同類型的傳感器,實時監(jiān)控運行狀態(tài)[7]:例如,大量溫度傳感器遍布車廂和車體、監(jiān)控變壓器以及驅(qū)動軸、定子轉(zhuǎn)軸、齒輪等關(guān)鍵部位,實時測量其溫度;安裝在車軸部位速度傳感器實時監(jiān)測列車運行時速和車軸轉(zhuǎn)速;空氣制動力、風(fēng)管壓力、連接端車牽引力等由車廂外部的測力傳感器收集;而中間電壓、牽引變流器功率、電制動功率、區(qū)域控制單元電壓等信息的記錄由各式復(fù)雜的電壓、電流傳感器負(fù)責(zé)。這些傳感器以每秒一次的采集頻率記錄列車運行時各部件的狀態(tài),并通過列車內(nèi)部的有線傳輸系統(tǒng),將采集數(shù)據(jù)傳送給車載安全計算機(或稱歐洲安全計算機(European Vital Computer,EVC)),計算機對傳感數(shù)據(jù)進(jìn)行整理,以日志文件的形式存儲于車載機柜的硬盤中。在達(dá)到一定數(shù)據(jù)量后,對日志文件進(jìn)行壓縮,再通過GSM-R網(wǎng)絡(luò)提供的通信網(wǎng)絡(luò)將壓縮數(shù)據(jù)傳輸給列車控制中心(Train Control Center,TCC);最后,TCC將壓縮數(shù)據(jù)分類整理,存入分布式數(shù)據(jù)庫HDFS(Hadoop Distributed File System)中。當(dāng)需要對列車監(jiān)測數(shù)據(jù)進(jìn)行分析時,后臺工作人員從HDFS中取出數(shù)據(jù)并進(jìn)行解壓縮,再對解壓縮結(jié)果進(jìn)行分析,進(jìn)而對列車狀態(tài)進(jìn)行判斷[8]。

        高速列車監(jiān)測數(shù)據(jù)具有如下特點:數(shù)據(jù)按時間序列采集;數(shù)據(jù)類型為雙精度浮點型;相鄰數(shù)據(jù)間差距較??;部分?jǐn)?shù)據(jù)內(nèi)容可為空;監(jiān)測數(shù)據(jù)種類較多;數(shù)據(jù)量巨大[9];此外,收集的監(jiān)測數(shù)據(jù)還需要進(jìn)行傳輸和保存。綜上所述,為保證監(jiān)測數(shù)據(jù)的有效存儲和安全傳輸,需要將由監(jiān)測數(shù)據(jù)構(gòu)成的日志文件進(jìn)行壓縮。目前針對監(jiān)測數(shù)據(jù)的壓縮常采用動態(tài)哈夫曼編碼(Dynamic Huffman Coding)技術(shù)[10]實現(xiàn),這種壓縮數(shù)據(jù)由一系列不等長的數(shù)據(jù)塊組成,如圖1 所示。每個數(shù)據(jù)塊包括塊頭標(biāo)號、動態(tài)哈夫曼樹、壓縮內(nèi)容以及塊尾標(biāo)號。其中:塊頭標(biāo)號用以描述當(dāng)前壓縮數(shù)據(jù)塊的特性;動態(tài)哈夫曼樹是數(shù)據(jù)壓縮和解壓縮的依據(jù);壓縮內(nèi)容存儲了使用動態(tài)哈夫曼樹壓縮數(shù)據(jù)后的結(jié)果;塊尾標(biāo)號由一串特定字符組成,用以標(biāo)識壓縮數(shù)據(jù)塊的結(jié)束。

        針對這類數(shù)據(jù),傳統(tǒng)的解壓縮流程從監(jiān)測數(shù)據(jù)的起始位置開始,按照數(shù)據(jù)塊的組成順序,利用動態(tài)哈夫曼樹,逐塊對其中的壓縮內(nèi)容進(jìn)行還原,通常效率較低。算法1和圖2分別展示了變長解壓縮算法的偽代碼和相應(yīng)的依賴關(guān)系分析圖。從算法1 可知,傳統(tǒng)算法的每一輪循環(huán)解壓一個完整的數(shù)據(jù)塊;當(dāng)一個數(shù)據(jù)塊被解壓完后,表示位置信息的pos 更新,指導(dǎo)下一個數(shù)據(jù)塊的解壓縮。如圖2 所示,該解壓縮算法共包含三條依賴:由變量eof引發(fā)的控制依賴、由內(nèi)部循環(huán)中的pos引發(fā)的數(shù)據(jù)依賴,以及由out_stream 變量引發(fā)的數(shù)據(jù)依賴。這些依賴關(guān)系共同作用,阻礙了多重循環(huán)的并行執(zhí)行。在數(shù)據(jù)量特別大的情況下,輸入數(shù)據(jù)中包含大量的數(shù)據(jù)塊,因此由pos所引起的數(shù)據(jù)依賴是影響算法并行執(zhí)行的最大因素。

        為提升針對變長編碼壓縮數(shù)據(jù)解壓縮效率,目前主流的解決思路是采用軟硬件協(xié)同的方法,通過加速單個數(shù)據(jù)塊的處理過程,提高針對變長編碼壓縮數(shù)據(jù)的整體壓縮效率。例如將傳統(tǒng)解壓縮算法移植到圖形處理器上,通過任務(wù)分解和統(tǒng)一計算設(shè)備架構(gòu)(Compute Unified Device Architecture,CUDA)提升算法效率[11-12]。此外還有運用大數(shù)據(jù)計算引擎,設(shè)計基于分布式平臺的數(shù)據(jù)解壓縮算法[13-14]。但此類方法的思路主要聚焦于并行化哈夫曼樹還原壓縮內(nèi)容的過程,并使用大量計算資源對該過程進(jìn)行加速,通常效果不佳。從對算法運行機制的深層次分析可知,這些優(yōu)化方法只能縮短單個數(shù)據(jù)塊的處理時間,而數(shù)據(jù)解壓的整體過程仍然是按照壓縮數(shù)據(jù)的組成順序串行進(jìn)行的。如圖2 所示,若不能消解算法中的數(shù)據(jù)依賴對執(zhí)行順序的影響,從根本上將串行解壓縮的過程并行化,則對解壓縮算法的性能優(yōu)化效果有限[15]。

        圖2 傳統(tǒng)變長解壓縮算法的偽代碼和依賴關(guān)系圖Fig.2 Pseudo codes and dependence relationship diagram of conventional variable-length decompression algorithm

        要從根本上提升數(shù)據(jù)解壓縮算法的并行度,需要在解壓縮之前,將壓縮數(shù)據(jù)劃分成一系列可以被獨立解壓縮的數(shù)據(jù)塊的組合,再同時解壓縮這些數(shù)據(jù)塊,從而使數(shù)據(jù)解壓縮過程并行化。但由于變長編碼技術(shù)的影響,數(shù)據(jù)塊間的邊界在解壓縮前通常難以確定,隨意劃分可能會造成對壓縮數(shù)據(jù)塊完整性的破壞;而數(shù)據(jù)塊內(nèi)部的任何部分都存在與壓縮內(nèi)容重復(fù)的可能性,因此也不具備作為劃分?jǐn)?shù)據(jù)塊邊界的功能。

        針對上述困難,本文以推測技術(shù)為手段,實現(xiàn)高速列車監(jiān)測數(shù)據(jù)的并行解壓縮。首先,以壓縮數(shù)據(jù)的塊尾標(biāo)號作為劃分?jǐn)?shù)據(jù)塊邊界的依據(jù),假定不存在壓縮內(nèi)容與塊尾標(biāo)號重復(fù)的情況,對數(shù)據(jù)進(jìn)行嘗試性劃分;然后設(shè)計推測校驗方法,消除錯誤劃分的影響,再將劃分結(jié)果進(jìn)行推測性的并行處理;最終將并行處理結(jié)果合并。通過這種方式并行化原本串行的數(shù)據(jù)解壓縮過程,從而提升變長壓縮數(shù)據(jù)的解壓縮效率。

        2 算法設(shè)計

        基于上述對存在問題和解決思路的描述,面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法設(shè)計如下:算法被分為推測劃分、推測檢驗、并行解壓縮和結(jié)果合并四個部分。

        2.1 推測劃分

        作為算法的第一部分,推測劃分的目的是在數(shù)據(jù)解壓縮之前,盡可能地將壓縮數(shù)據(jù)劃分成獨立完整的數(shù)據(jù)塊,使這些數(shù)據(jù)塊可以不依賴于先前數(shù)據(jù)塊所提供的位置信息而被獨立處理。為達(dá)成該目的,需要確定推測劃分的依據(jù)和粒度。

        首先,推測劃分的依據(jù)按照如下方法確定。在變長壓縮數(shù)據(jù)內(nèi)部,數(shù)據(jù)塊由四部分組成,其中動態(tài)哈夫曼樹和塊尾標(biāo)號的內(nèi)容固定不變,其他部分會隨著壓縮內(nèi)容的不同而變化[15],因此,首選動態(tài)哈夫曼樹或塊尾標(biāo)號作為推測劃分的依據(jù);又因為塊尾標(biāo)號由動態(tài)哈夫曼樹編碼表中最長的編碼構(gòu)成,其長度通常小于壓縮數(shù)據(jù)塊中的動態(tài)哈夫曼樹,更容易被識別和提?。?6]。綜上原因,在算法設(shè)計中,擬選取塊尾標(biāo)號作為依據(jù),對壓縮數(shù)據(jù)進(jìn)行推測性地劃分。

        確定劃分依據(jù)的基礎(chǔ)上,再確定推測劃分的粒度。一般來說,針對數(shù)據(jù)的劃分粒度太細(xì)密,會使得劃分工作變得非常繁瑣,影響后期并行解壓縮任務(wù)的數(shù)量,使派生并行解壓縮任務(wù)的工作量陡增,影響算法的整體性能表現(xiàn);但如果將數(shù)據(jù)劃分得過大,又會導(dǎo)致劃分?jǐn)?shù)據(jù)的傳輸和并行處理成本增加,也會影響到整體的性能[17]。因此,數(shù)據(jù)的劃分粒度是影響到算法效率的重要因素。

        為了確定劃分粒度,需要建立其與算法運行時間的理論模型。假設(shè)在推測并行解壓縮算法中,單個并行解壓縮任務(wù)的執(zhí)行時間F相等,則算法總耗時T如式(1)所示,總耗時T由并行任務(wù)的派生耗時和執(zhí)行耗時組成,其中λi為單個并行任務(wù)派生耗時,M表示任務(wù)總量,C表示分布式集群中工作節(jié)點數(shù)量。

        此外,由于數(shù)據(jù)塊劃分?jǐn)?shù)量M與壓縮數(shù)據(jù)總大小E、劃分粒度H程反比,故M=。如果假設(shè)每個并行任務(wù)的派生耗時λi近似,則有=M×λ,用該式對式(1)中的M和λ進(jìn)行替換,可得算法耗時T與劃分粒度H及單個并行任務(wù)的執(zhí)行時間F的關(guān)系如式(2)所示:

        其中:E為壓縮數(shù)據(jù)總大小,λ為單個任務(wù)派生耗時,μ為算法執(zhí)行時間系數(shù),C為節(jié)點數(shù),且這幾個均為常量。因此式(3)可以表示為劃分粒度H與算法耗時T的關(guān)系,其函數(shù)圖像如圖3所示。

        圖3 推測劃分粒度與算法耗時函數(shù)關(guān)系圖Fig.3 Relationship between speculative division granularity and algorithm running time

        從實際情況出發(fā),劃分粒度應(yīng)滿足條件H>0,故選取第一象限進(jìn)行分析。觀察函數(shù)圖像可知,當(dāng)劃分粒度H趨近于0時,分塊數(shù)量趨近于+∞,會導(dǎo)致任務(wù)分派節(jié)點的負(fù)載過大,派生任務(wù)耗時所占比重不斷增加,進(jìn)而影響算法效率。

        為使算法耗時最短,需對式(3)進(jìn)行求導(dǎo),并令導(dǎo)數(shù)為0,易知當(dāng)劃分粒度H滿足式(4)時,使T取得極小值。

        綜上分析,式(4)即為確定推測劃分粒度的數(shù)學(xué)模型,通過該模型可以確定當(dāng)H滿足條件時,算法執(zhí)行時間最短。

        針對采用變長編碼的壓縮數(shù)據(jù),其數(shù)據(jù)大小E、集群節(jié)點C和任務(wù)派生平均時間λ可以在算法執(zhí)行前得知;而μ的取值依賴于輸入數(shù)據(jù)類型,一般取均值31 250[16]。經(jīng)過計算,可得H為29 MB。最后,為了使劃分粒度數(shù)值快速收斂,一般選取大于H且滿足2的n次冪的最小值。最終,在推測并行解壓縮算法中,將推測劃分粒度確定為32 MB。

        在確定劃分依據(jù)和粒度的基礎(chǔ)上,算法以輸入數(shù)據(jù)中首個數(shù)據(jù)塊的塊尾標(biāo)號為依據(jù),以32 MB 為最短步長,逐字節(jié)地掃描輸入數(shù)據(jù),以確定推測劃分點,如圖4 所示,對數(shù)據(jù)進(jìn)行初步的推測劃分。然而由于該劃分策略是以推測技術(shù)為基礎(chǔ),因此存在因數(shù)據(jù)巧合,出現(xiàn)壓縮內(nèi)容與塊尾標(biāo)號相同而被認(rèn)為誤認(rèn)為是劃分點的情況,所以在推測劃分結(jié)束后,需要對推測劃分結(jié)果進(jìn)行檢驗,以確保劃分結(jié)果的正確性。

        圖4 推測劃分過程示意圖Fig.4 Schematic diagram of speculative division

        2.2 推測檢驗

        由于通過推測所獲得的數(shù)據(jù)劃分點并不能保證數(shù)據(jù)塊的完整性,因此需要對推測劃分結(jié)果進(jìn)行驗證。參考其他基于變長編碼的并行數(shù)據(jù)壓縮方法[18],本文算法提出頭校驗、哈夫曼樹重建和數(shù)據(jù)長度校驗三種檢驗手段,通過這三種檢驗手段的結(jié)合,檢測劃分結(jié)果是否正確。

        頭校驗是指檢驗劃分結(jié)果的前3 位是否遵循塊頭標(biāo)號的編碼規(guī)則。一般來說,壓縮數(shù)據(jù)塊的前3 位只能是010 或000,分別代表該壓縮數(shù)據(jù)塊是遵循動態(tài)編碼標(biāo)準(zhǔn)的壓縮數(shù)據(jù)塊或是未被壓縮的非壓縮數(shù)據(jù)塊,如果劃分結(jié)果的前3 位不是010或000,則該劃分為錯誤劃分。

        結(jié)束頭校驗后,根據(jù)頭校驗的結(jié)果,繼續(xù)對劃分結(jié)果進(jìn)行檢驗,即哈夫曼樹重建和數(shù)據(jù)長度校驗。哈夫曼樹重建是指當(dāng)劃分?jǐn)?shù)據(jù)的前3位為010時,代表當(dāng)前劃分結(jié)果可能是以壓縮數(shù)據(jù)塊開頭的一組數(shù)據(jù),此時可以通過利用010 后的數(shù)據(jù)進(jìn)行動態(tài)哈夫曼樹的重建來判斷:如果無法重建動態(tài)哈夫曼樹,則該劃分為錯誤劃分。數(shù)據(jù)長度校驗是指當(dāng)劃分?jǐn)?shù)據(jù)的前3位為000時,代表當(dāng)前劃分結(jié)果可能是以非壓縮數(shù)據(jù)塊開頭的一組數(shù)據(jù),因此需要對非壓縮數(shù)據(jù)塊的長度進(jìn)行判斷:在采用變長編碼的壓縮數(shù)據(jù)中規(guī)定,非壓縮數(shù)據(jù)塊的長度不能超過16 KB[19]。因此,如果從000后到下一個塊頭標(biāo)號之間的字段長度超過16 KB,則該劃分為錯誤劃分,反之則為正確劃分。

        為詳細(xì)解釋推測檢驗原理,圖5 詳細(xì)模擬了該過程。在某段高速列車監(jiān)測數(shù)據(jù)中,壓縮數(shù)據(jù)的塊尾標(biāo)號為10111111,用塊尾標(biāo)號將壓縮數(shù)據(jù)劃分為四組后,對四組數(shù)據(jù)的推測檢驗過程如下:首先進(jìn)行頭校驗,由圖5可知,第3組數(shù)據(jù)劃分的開頭011 不符合壓縮數(shù)據(jù)塊的標(biāo)準(zhǔn)頭格式,因此未能通過頭校驗,該劃分錯誤。其余三組劃分?jǐn)?shù)據(jù)根據(jù)頭校驗結(jié)果的不同,繼續(xù)進(jìn)行后續(xù)校驗:在對開頭為010 的劃分結(jié)果進(jìn)行哈夫曼樹重建的過程中發(fā)現(xiàn),第2 組劃分?jǐn)?shù)據(jù)無法重建哈夫曼樹,因此未能通過校驗,該劃分錯誤;最后針對開頭為000 的劃分結(jié)果進(jìn)行數(shù)據(jù)長度校驗,亦未能通過,該劃分錯誤。至此,只有第1 組數(shù)據(jù)劃分結(jié)果通過所有校驗,說明其為正確劃分,通過該劃分點將原始壓縮數(shù)據(jù)劃分后,前后兩部分劃分內(nèi)容均可被獨立處理。

        圖5 推測劃分檢驗示意圖Fig.5 Schematic diagram of speculative division evaluation

        經(jīng)過對推測劃分?jǐn)?shù)據(jù)的檢驗后,通過檢驗的劃分依據(jù)才能真正將壓縮數(shù)據(jù)劃分成可獨立處理的數(shù)據(jù)分塊。再用這些通過檢驗的劃分依據(jù)對壓縮數(shù)據(jù)進(jìn)行二次劃分,這樣的劃分結(jié)果可以保證被獨立解壓縮,進(jìn)而被用于并行解壓縮。待二次劃分結(jié)束,算法進(jìn)入并行解壓縮階段。

        2.3 并行解壓縮

        并行解壓縮是算法的第三階段,該階段的目的是并行處理經(jīng)過推測劃分和推測檢驗的數(shù)據(jù)塊集合。在該階段,首先將經(jīng)過二次劃分的數(shù)據(jù)塊集合傳輸?shù)椒植际接嬎憧蚣艿母饔嬎愎?jié)點中,同時設(shè)置相應(yīng)的資源調(diào)度策略,以保證分布式計算框架能提供充足的算力,支持所有數(shù)據(jù)塊的并行處理。在數(shù)據(jù)傳輸和資源調(diào)度之后,由主節(jié)點根據(jù)推測劃分塊的數(shù)量,派生相應(yīng)數(shù)量的并行任務(wù),同時對所有的分塊進(jìn)行解壓縮。在該過程中,所有工作節(jié)點執(zhí)行的任務(wù)內(nèi)容相同,而處理的數(shù)據(jù)不同,每個節(jié)點內(nèi)部的具體執(zhí)行內(nèi)容如算法2所示。

        在并行解壓縮階段,分布式計算框架中的每個計算節(jié)點以動態(tài)哈夫曼樹為參考,解壓縮數(shù)據(jù)。具體流程是在讀入編碼數(shù)據(jù)時,按位逐個遍歷哈夫曼樹,得到的葉子節(jié)點信息即為該編碼數(shù)據(jù)的解壓縮結(jié)果。重復(fù)這個過程直到遇到塊尾標(biāo)號,再將所有遍歷結(jié)果收集整合,得到壓縮數(shù)據(jù)的解壓縮結(jié)果。重復(fù)上述全部過程,直到經(jīng)過推測劃分的數(shù)據(jù)全部被解壓縮,最終將全部解壓縮結(jié)果按順序合并,從而得到并行解壓縮的其中一部分執(zhí)行結(jié)果。

        2.4 結(jié)果合并

        當(dāng)分布式計算框架中的所有節(jié)點完成解壓縮任務(wù)后,算法進(jìn)入結(jié)果合并階段,該階段由兩部分組成:解壓縮結(jié)果合并和出錯處理。具體來說,如果所有節(jié)點的并行解壓縮任務(wù)均順利完成,那么這些結(jié)果將被匯總至分布式計算框架的主節(jié)點中,并按照輸出數(shù)據(jù)的組織格式,順序合并解壓縮結(jié)果,形成并行解壓縮的輸出;如果解壓縮過程出現(xiàn)問題,解壓縮出錯的節(jié)點需要上報錯誤信息給主節(jié)點,主節(jié)點則記錄出錯節(jié)點的位置,保存出錯節(jié)點之前的所有解壓縮結(jié)果,并拋棄出錯節(jié)點之后所有的解壓縮結(jié)果,將數(shù)據(jù)回滾,再重新對出錯節(jié)點之后的所有數(shù)據(jù)按順序用傳統(tǒng)的數(shù)據(jù)解壓縮算法重新解壓縮,以保證最終輸出結(jié)果的正確性。

        3 算法實現(xiàn)

        本文提出的算法通過推測劃分?jǐn)?shù)據(jù)再并行處理的方式,使原本按照壓縮順序串行處理的高速列車監(jiān)測數(shù)據(jù)可以通過推測的方式并行處理,同時通過推測校驗和結(jié)果合并機制保證推測執(zhí)行結(jié)果的正確性,使算法兼具高效性和穩(wěn)定性。為了詳細(xì)描述算法,將選取高速列車實際運行數(shù)據(jù)作為研究對象,以Apache Spark為實現(xiàn)平臺,對算法流程進(jìn)行介紹。

        研究對象數(shù)據(jù)選自2019 年4 月11 日西成高鐵成都東至西安北的D1912 次列車所產(chǎn)生的監(jiān)測數(shù)據(jù),該列車采用8 輛編組,監(jiān)測數(shù)據(jù)由CRH380BL車型的傳感器產(chǎn)生,數(shù)據(jù)量約為19 GB,采用Zlib 編碼標(biāo)準(zhǔn)進(jìn)行壓縮。表示算法在Apache Spark 上的執(zhí)行流程的有向無環(huán)圖(Directed Acyclic Graph,DAG)如圖6~7所示:Apache Spark的主控制節(jié)點(以下簡稱主節(jié)點)從分布式數(shù)據(jù)庫中讀入監(jiān)測數(shù)據(jù),形成彈性分布式數(shù)據(jù)集(Resilient Distributed Datasets,RDD),并將監(jiān)測數(shù)據(jù)存儲為鍵值對的形式,其中鍵表示數(shù)據(jù)分塊的順序,值表示監(jiān)測數(shù)據(jù)的二進(jìn)制代碼片段。

        圖6 推測并行算法執(zhí)行的有向無環(huán)圖1Fig.6 Directed acyclic graph 1 executed by speculative parallelism algorithm

        按照算法設(shè)計,第一步為獲取劃分依據(jù):指導(dǎo)集群中某單個工作節(jié)點解壓縮監(jiān)測數(shù)據(jù)RDD1 中的首個壓縮數(shù)據(jù)塊,解析動態(tài)哈夫曼樹,獲取塊尾標(biāo)號(在本示例中的值為10111),形成RDD2,接著對RDD1 進(jìn)行持久化操作(圖6 中的虛線部分),該操作的目的是備份RDD1,供推測檢驗結(jié)束后正確劃分結(jié)果指導(dǎo)監(jiān)測數(shù)據(jù)的重新劃分。

        第二步為推測劃分,即使用塊尾標(biāo)號RDD2,對RDD1 中的所有元素進(jìn)行并行劃分,具體流程是以RDD2 中塊尾標(biāo)號為依據(jù),按照32 MB 步長,對監(jiān)測數(shù)據(jù)RDD1 中所有分片同時執(zhí)行如圖4 所示過程的劃分,最終結(jié)果形成RDD3。在圖6中,RDD1 經(jīng)RDD2 劃分后形成由M個分塊組成的RDD3,在RDD3 內(nèi)部,鍵值對與RDD1 的組成略有不同:鍵仍然表示分塊順序,值變?yōu)樵M形式,其中,元組的首個元素代表劃分位置相對于監(jiān)測數(shù)據(jù)起始位置的偏移量,第二個元素代表劃分結(jié)果。

        第三步為推測檢驗,該流程類似圖5 過程,即同時展開對RDD3 中包含劃分結(jié)果的頭校驗、哈夫曼樹重建和數(shù)據(jù)長度校驗工作,并在檢驗結(jié)束后,形成由P個分塊(P≤M)組成的推測檢驗結(jié)果RDD4,其內(nèi)部數(shù)據(jù)組成形式與RDD3相同。

        第四步,使用經(jīng)過推測檢驗的RDD4 中所蘊含的偏移量,對RDD1 進(jìn)行并行重劃分,過程類似于推測劃分,最終形成RDD5,在RDD5 的每個分塊中,值代表經(jīng)過重新劃分,并可被獨立處理的二進(jìn)制代碼片段。待重新劃分結(jié)束,結(jié)果被繼續(xù)存于各工作節(jié)點的本地空間,等待后續(xù)并行處理,推測檢驗階段結(jié)束。

        第五步為并行解壓縮。如圖7 所示,在該過程中,RDD5中的所有數(shù)據(jù)分塊將遵照算法2 的流程同時進(jìn)行解壓縮,并行解壓縮的結(jié)果將形成RDD6;待并行解壓縮結(jié)束,再將結(jié)果合并,具體過程如下:所有RDD6 中的數(shù)據(jù)由各工作節(jié)點回傳至主節(jié)點,再由主節(jié)點按照RDD6 中鍵值對的排列順序,依據(jù)規(guī)定輸出結(jié)果的文件格式類型,對所有結(jié)果按順序進(jìn)行合并,形成RDD7,最后將合并結(jié)果RDD7存回分布式數(shù)據(jù)庫HDFS,完成推測并行解壓縮算法的全過程。

        圖7 推測并行算法執(zhí)行的有向無環(huán)圖2Fig.7 Directed acyclic graph 2 executed by speculative parallelism algorithm

        4 實驗與結(jié)果分析

        為全面測試推測并行解壓縮算法的功能和性能。實驗設(shè)計如下:在實驗環(huán)境配置方面,選用7臺相同配置的聯(lián)想ST58小型塔式服務(wù)器,搭配Juniper J6350 企業(yè)級高性能路由器組建計算集群,并部署最新版本的Apache Spark 3.0.1。

        實驗數(shù)據(jù)隨機選擇成都鐵路局下轄的4 列高速列車在2019 年4 月至6 月期間所產(chǎn)生的監(jiān)測數(shù)據(jù)。數(shù)據(jù)使用Zlib 編碼指導(dǎo)壓縮,大小從20 GB 到200 GB 規(guī)模不等,用以測試算法在應(yīng)對不同規(guī)模數(shù)據(jù)時的性能表現(xiàn)情況。測試數(shù)據(jù)的詳情如表1所示,其中File 4記錄的是同一列車往返的監(jiān)測數(shù)據(jù)。

        表1 實驗數(shù)據(jù)集Tab.1 Dataset used in experiment

        此外,為了探究算法的可擴展性,還設(shè)置了4 組對照實驗組,分別是傳統(tǒng)串行算法在Apache Spark 上串行執(zhí)行,以及推測并行算法在由3/5/7 節(jié)點組成的集群上并行執(zhí)行。實驗方案和具體配置如表2 所示。值得注意的是,由于傳統(tǒng)算法只能串行執(zhí)行,因此即使分配再多的節(jié)點,算法實際使用的節(jié)點數(shù)仍只有2個,即1個主節(jié)點+1個工作節(jié)點。

        遵照表2 設(shè)計的實驗方案,分別對傳統(tǒng)串行算法和推測并行算法進(jìn)行測試。為保證實驗結(jié)果的可靠性,每組實驗在Apache Spark 上分別運行五次,求取平均運行時長作為最終實驗結(jié)果。此外,在實驗中使用開源的分布式監(jiān)控系統(tǒng)Ganglia實時檢測集群中所有節(jié)點的CPU、內(nèi)存、磁盤、I/O負(fù)載以及整體網(wǎng)絡(luò)負(fù)載情況。

        表2 實驗方案的具體配置Tab.2 Specific configuration of experimental schemes

        下面從性能、可擴展性、可靠性等方面對基于推測技術(shù)的并行算法進(jìn)行測試評估,并結(jié)合實驗數(shù)據(jù),進(jìn)行相關(guān)分析。

        4.1 算法的性能測試與分析

        首先測試推測并行算法的性能。圖8 展示了在由7 個節(jié)點組成的環(huán)境下(實驗方案Experiment 4),傳統(tǒng)串行算法和推測并行算法的運行時長對比。如圖8 所示,盡管兩組實驗的硬件條件相同,但是由于傳統(tǒng)算法在Apache Spark 上串行執(zhí)行,通過Ganglia 可以檢測到在算法實際運行過程中,僅有一個主節(jié)點與一個工作節(jié)點參與有效計算,而基于相同環(huán)境的并行算法由于可以同時調(diào)度和使用集群所有資源,因此執(zhí)行時間大幅縮短。

        詳細(xì)研究圖8 可以發(fā)現(xiàn),在由7 節(jié)點組成的集群下,針對大規(guī)模數(shù)據(jù)的解壓縮過程中,并行算法在處理相同大小文件時,平均耗時比傳統(tǒng)串行算法減少了約2/3。經(jīng)過統(tǒng)計不同算法處理File1 到File4 的時長,可以計算出相較于傳統(tǒng)算法,并行算法將解壓縮的效率提高了2.10 倍。因此說明在面對大規(guī)模高速列車監(jiān)測數(shù)據(jù)的解壓縮時,基于推測并行技術(shù)的解壓縮算法比傳統(tǒng)串行解壓縮算法更高效。

        圖8 性能測試結(jié)果Fig.8 Results of performance evaluation

        4.2 算法的可擴展性測試與分析

        為了測試算法的可擴展性,設(shè)計實驗如下:在保持測試數(shù)據(jù)不變的情況下,逐漸增加集群中工作節(jié)點的個數(shù),設(shè)置如表2 所示的三組實驗方案對照組;再在這三組實驗方案下,分別使用推測并行算法解壓縮File1 到File4 的數(shù)據(jù),并統(tǒng)計算法在不同方案中的執(zhí)行時長;最后,通過觀察算法的執(zhí)行時長變化情況,驗證算法是否具有良好的可擴展性。

        圖9 展示了在不同節(jié)點數(shù)的情況下,推測并行算法在處理同規(guī)模數(shù)據(jù)時的性能變化情況。面對相同規(guī)模的壓縮數(shù)據(jù)時,隨著節(jié)點數(shù)的增加,推測并行算法的執(zhí)行時間逐漸減少。此外,由圖9 可以看出,當(dāng)測試數(shù)據(jù)增大到一定程度(大于100 GB),節(jié)點數(shù)量的變化對算法的性能影響更加明顯。

        圖9 可擴展性測試結(jié)果Fig.9 Results of scalability evaluation

        加速比計算公式如下:

        其中:p表示可并行部分的占比;s表示處理器個數(shù)或可并行部分的加速倍數(shù)。

        經(jīng)過計算,推測并行算法在不同環(huán)境下處理相同數(shù)據(jù)時的加速比變化情況如圖10 所示。隨著節(jié)點數(shù)的增加,算法加速比S(p如式(5)所示)逐步上升,特別在針對大于100 GB 的大規(guī)模壓縮數(shù)據(jù)的處理中,算法的加速比跟隨并行機數(shù)量的增加呈近似線性增長。表明本文算法具有很強的擴展性,其性能隨著工作節(jié)點數(shù)的增加而不斷提升,進(jìn)一步驗證了圖9所呈現(xiàn)出的實驗結(jié)果。

        圖10 各算法加速比變化情況Fig.10 Change of algorithms’speedup

        4.3 算法的可靠性測試與分析

        算法的可靠性,或稱算法的準(zhǔn)確性,是衡量算法是否優(yōu)秀的核心要素。從本質(zhì)上講,推測并行算法是利用之前無法被串行算法充分利用的計算資源來進(jìn)行額外計算,進(jìn)而從額外計算的成功中獲得性能提升,故其性能提升的基本原理是以資源換取效率,與基于多核架構(gòu)的并行算法原理類似。因此,如果推測并行算法中的推測錯誤率太高,不僅表示算法的準(zhǔn)確性差、可靠性低,同時會導(dǎo)致集群中大量計算資源被用于進(jìn)行無效計算,嚴(yán)重時甚至影響算法的整體性能。

        為了測試算法的可靠性,需要對推測劃分結(jié)果的準(zhǔn)確率做統(tǒng)計和分析,具體方法是:在對推測劃分的結(jié)果進(jìn)行驗證結(jié)束以后,使用插樁測試技術(shù),統(tǒng)計出現(xiàn)錯誤的推測劃分?jǐn)?shù)據(jù)的比例。結(jié)果如表3所示。

        表3 錯誤推測率的統(tǒng)計Tab.3 Statistics on mis-speculation rate

        按照32 MB 為最小劃分步長對壓縮數(shù)據(jù)進(jìn)行推測劃分,其推測劃分塊的數(shù)量如表3 的第三列所示。經(jīng)過推測檢驗,發(fā)生誤推測的數(shù)據(jù)塊數(shù)量如表3 的第四列所示。從這兩列數(shù)據(jù)內(nèi)容可以看出,只有極少數(shù)的推測劃分出現(xiàn)了錯誤。誤推測的比例始終維持在0.5%以下。這意味著在本文算法中,只有極少量的資源被浪費在基于錯誤推測結(jié)果的計算上,而大部分計算資源被用于進(jìn)行有效計算。這不僅意味著本文算法具有很強的可靠性,也說明本文算法能夠充分有效地利用Apache Spark中蘊含的計算資源,避免資源浪費等問題。

        4.4 對算法性能提升機制的分析

        通過以上實驗,證實了推測并行算法兼具高效性、可擴展性和高可靠性。在此基礎(chǔ)上,為了深入了解算法性能提升的原因,以及探究影響和制約算法性能的因素,還需對推測并行算法性能提升的機制進(jìn)行分析。具體方法如下:利用分布式監(jiān)控系統(tǒng)Ganglia 統(tǒng)計推測并行算法在執(zhí)行時各個階段的耗時情況。為統(tǒng)計分析便利,將推測劃分和檢驗階段統(tǒng)稱為推測準(zhǔn)備階段,各階段耗時如圖11所示。圖11展示了在不同實驗方案下,針對不同的測試數(shù)據(jù),并行算法的分階段執(zhí)行時間統(tǒng)計。在推測并行算法中,推測劃分、推測檢驗、并行解壓縮3 個階段為并行執(zhí)行,而結(jié)果合并階段為串行執(zhí)行。反映在實驗中,即如圖11 所示,在面對相同的實驗數(shù)據(jù)時,隨著節(jié)點數(shù)的增加,推測準(zhǔn)備和并行解壓縮階段的耗時不斷減少,使算法保持了良好的可擴展性;然而,數(shù)據(jù)合并階段不會因為計算資源的增加而減少,面對相同規(guī)模的數(shù)據(jù),該階段耗時基本保持不變。隨著數(shù)據(jù)量的不斷攀升,結(jié)果合并階段所占時間比例也越來越大,甚至明顯超過推測準(zhǔn)備與并行解壓縮階段所用時間之和。同樣地,隨著集群中計算節(jié)點數(shù)的增加,算法在處理相同規(guī)模的測試數(shù)據(jù)時,推測準(zhǔn)備與并行解壓縮階段用時逐漸減少,但結(jié)果合并階段卻不受其影響所占時間比例越來越大,反映在圖10 中的表現(xiàn)為:隨著計算節(jié)點數(shù)量的增加,算法整體加速比增長越來越不明顯。因此結(jié)果合并階段成為制約算法效率進(jìn)一步提升的重要因素。究其原因在于推測準(zhǔn)備和并行解壓縮階段是并發(fā)的,而結(jié)果合并階段則是在主節(jié)點上串行進(jìn)行的,隨著計算節(jié)點的增加,算法的并行階段耗時會越來越少,而結(jié)果合并階段耗時基本不變,因而導(dǎo)致整體性能提升幅度越來越小。因此優(yōu)化結(jié)果合并階段將成為后續(xù)的研究重點。

        圖11 本文算法各階段耗時統(tǒng)計Fig.11 Statistics on time consumption of each stage of proposed algorithm

        5 結(jié)語

        本文提出了一種面向高速列車監(jiān)測數(shù)據(jù)的并行解壓縮算法,在暫時忽略數(shù)據(jù)依賴的前提下,使用推測并行技術(shù),將采用變長編碼技術(shù)壓縮的、原本不可劃分的高速列車監(jiān)測數(shù)據(jù)進(jìn)行試探性劃分,再利用壓縮數(shù)據(jù)的結(jié)構(gòu)特點,對劃分結(jié)果進(jìn)行檢驗,在保證劃分準(zhǔn)確的基礎(chǔ)上,并發(fā)處理劃分結(jié)果,使原本只能按照數(shù)據(jù)組織結(jié)構(gòu)串行進(jìn)行的數(shù)據(jù)解壓縮過程能夠以推測的方式并行化進(jìn)行,進(jìn)而提高針對高速列車監(jiān)測數(shù)據(jù)的解壓縮效率。上述工作已經(jīng)取得了良好的實際效果,通過與北京交通大學(xué)和中車唐山機車車輛有限公司合作,本文算法及相關(guān)產(chǎn)品已應(yīng)用于包括CRH380BL 和CRH380B-002 等型號的高速列車監(jiān)測記錄數(shù)據(jù)的并行解壓縮工作中,并提高了針對此類車型監(jiān)測記錄數(shù)據(jù)的分析效率,但通過實驗分析可知,在該算法仍存在可優(yōu)化空間,對于算法中的結(jié)果合并階的優(yōu)化將是今后研究工作的重點。

        猜你喜歡
        并行算法壓縮算法監(jiān)測數(shù)據(jù)
        地圖線要素綜合化的簡遞歸并行算法
        基于參數(shù)識別的軌道電路監(jiān)測數(shù)據(jù)壓縮算法研究
        GSM-R接口監(jiān)測數(shù)據(jù)精確地理化方法及應(yīng)用
        更正聲明
        基于GPU的GaBP并行算法研究
        PMU數(shù)據(jù)預(yù)處理及壓縮算法
        GPS異常監(jiān)測數(shù)據(jù)的關(guān)聯(lián)負(fù)選擇分步識別算法
        基于小波函數(shù)對GNSS監(jiān)測數(shù)據(jù)降噪的應(yīng)用研究
        變電站監(jiān)測數(shù)據(jù)采集系統(tǒng)
        電測與儀表(2014年3期)2014-04-04 09:08:32
        基于GPU的分類并行算法的研究與實現(xiàn)
        女同国产日韩精品在线| 久久亚洲精品无码va大香大香| 国产一极毛片| 日本五十路熟女在线视频| 亚洲av高清一区二区在线观看| 久久婷婷五月综合97色一本一本| 国产欧美精品区一区二区三区 | 麻豆久久久9性大片| 国产精品自产拍在线观看免费| 精品日本免费观看一区二区三区| 日本在线一区二区三区不卡| 99久久久无码国产精品6| 日韩一区二区肥| 成人性生交大片免费看7| 中文字幕国产精品一二三四五区| 国产如狼似虎富婆找强壮黑人| 国产爆乳无码一区二区在线| 亚洲一区二区三区av无| 99精品国产在热久久无毒不卡| 国产成人亚洲精品无码mp4| 亚洲色图综合免费视频| 青青草视频在线观看精品在线| 国产a√无码专区亚洲av| 人妻av一区二区三区精品| 亚洲情精品中文字幕有码在线| 24小时在线免费av| 97夜夜澡人人双人人人喊| 国产激情久久99久久| av免费在线播放一区二区| 日本精品少妇一区二区三区| 欧美极品少妇性运交| 国产香蕉一区二区三区| 丰满精品人妻一区二区| 免费a级毛片永久免费| 久久中文字幕日韩精品| 亚洲国产精品激情综合色婷婷| 又粗又硬又大又爽免费视频播放| 青青青爽国产在线视频| 日韩美女人妻一区二区三区| 亚洲成av人片不卡无码| 丰满人妻妇伦又伦精品国产|