梁宇軒， 邢永山， 張 千

(中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，青島 266580)

改進(jìn)貝葉斯分類算法的MapReduce并行調(diào)度算法

梁宇軒， 邢永山， 張 千

(中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院，青島 266580)

在分析作業(yè)劃分及現(xiàn)有調(diào)度策略的基礎(chǔ)上，提出了改進(jìn)貝葉斯分類算法的作業(yè)調(diào)度策略，對(duì)貝葉斯分類調(diào)度算法及MapReduce默認(rèn)調(diào)度方式處理大規(guī)模數(shù)據(jù)時(shí)面臨的問(wèn)題進(jìn)行了闡述，詳細(xì)地介紹了該改進(jìn)算法的具體思路和整體流程，描述了該改進(jìn)算法的具體實(shí)現(xiàn)，分析了該調(diào)度算法相對(duì)其它調(diào)度算法的優(yōu)勢(shì)。通過(guò)實(shí)驗(yàn)驗(yàn)證采用改進(jìn)的貝葉斯調(diào)度算法與常用調(diào)度算法執(zhí)行速度進(jìn)行比較，取得了較好的效果。

貝葉斯分類算法; MapReduce; 地震資料處理; 并行調(diào)度

0 引言

地震資料處理的的數(shù)據(jù)信息屬于海量數(shù)據(jù)，如果要將大量的數(shù)據(jù)信息進(jìn)行并行處理，需要計(jì)算機(jī)具備較強(qiáng)的系統(tǒng)性能。在對(duì)石油專業(yè)技術(shù)領(lǐng)域中已有的地震資料數(shù)據(jù)并行處理調(diào)度器進(jìn)行深入探究的過(guò)程中，利用貝葉斯調(diào)度算法對(duì)并行環(huán)節(jié)進(jìn)行全面改進(jìn)與優(yōu)化，能夠科學(xué)高效的選取最合理的任務(wù)將其與slave節(jié)點(diǎn)相結(jié)合?？梢杂行У乇苊庖蛟O(shè)置固定的無(wú)經(jīng)驗(yàn)參數(shù)，使得系統(tǒng)運(yùn)作的效率受到嚴(yán)重的影響[1]。貝葉斯調(diào)度算法在具體操作中也具有一定的不足，該技術(shù)算法將作業(yè)任務(wù)分配到不同的隊(duì)列進(jìn)行處理時(shí)的欠缺體現(xiàn)如下：

1)reduce任務(wù)在操作過(guò)程中所輸入數(shù)據(jù)，實(shí)際上就是map任務(wù)在運(yùn)作時(shí)輸出的中間結(jié)果，map輸出的數(shù)據(jù)在本地磁盤中進(jìn)行有效地存儲(chǔ)。也就是說(shuō)，reduce任務(wù)在運(yùn)作過(guò)程中，諸多的時(shí)間都是在進(jìn)行copy數(shù)據(jù)階段的操作。單炮地震資料數(shù)據(jù)在實(shí)際操作時(shí)的任務(wù)量十分龐大，若較多的節(jié)點(diǎn)同時(shí)進(jìn)行copy操作，會(huì)大大降低系統(tǒng)運(yùn)行的效率[2]。

2) 預(yù)先設(shè)置的系統(tǒng)資源參數(shù)分配屬于固定值的設(shè)置形式，在實(shí)踐應(yīng)用中未能夠有針對(duì)性的發(fā)揮作用[3]。

3) 貝葉斯調(diào)度算法在應(yīng)用過(guò)程中，是根據(jù)某一時(shí)刻負(fù)載狀況，把作業(yè)按其質(zhì)量進(jìn)行劃分，質(zhì)量較好的作業(yè)隊(duì)列中的作業(yè)任務(wù)會(huì)一直進(jìn)行調(diào)度，較差質(zhì)量的作業(yè)任務(wù)將會(huì)被丟棄，這種操作形式未能夠?qū)ο到y(tǒng)的實(shí)時(shí)負(fù)載平衡方面進(jìn)行綜合思考，而且某時(shí)刻的壞作業(yè)對(duì)于后續(xù)關(guān)鍵作業(yè)環(huán)節(jié)會(huì)造成極為嚴(yán)重性的影響，將會(huì)使得整個(gè)作業(yè)在運(yùn)作過(guò)程中無(wú)法有效地實(shí)施[4-5]。

1 改進(jìn)貝葉斯調(diào)度算法的基本思想

結(jié)合傳統(tǒng)貝葉斯調(diào)度算法在具體應(yīng)用過(guò)程中的欠缺之處，進(jìn)行技術(shù)優(yōu)化的貝葉斯調(diào)度算法將作業(yè)任務(wù)按照合理的技術(shù)形式進(jìn)行劃分，將并發(fā)粒度比較理想的作業(yè)按其有效性，劃分為多個(gè)隊(duì)列操作形式，并分配到與計(jì)算量相匹配協(xié)調(diào)系統(tǒng)資源。在對(duì)地震資料數(shù)據(jù)信息采取技術(shù)操作的過(guò)程中，將JobTracker隊(duì)列中作業(yè)按負(fù)載狀況綜合性地分析與思考，決定采取什么樣的技術(shù)手段能夠確保對(duì)作業(yè)任務(wù)有效地并行處理，進(jìn)而合理地降低通信數(shù)據(jù)信息的花費(fèi)[6-7]。

Hadoop所對(duì)應(yīng)的進(jìn)程速率計(jì)算為式(1)。

progressRate=progressScore/t

(1)

式中：progressScore為已完成任務(wù)進(jìn)度默認(rèn)值；當(dāng)前任務(wù)所花費(fèi)的時(shí)間為t，進(jìn)而估算出此作業(yè)從當(dāng)前到完成所花費(fèi)的剩余時(shí)間(式(2))。

(2)

為了描述算法的執(zhí)行流程，我們定義該調(diào)度算法常用的作業(yè)描述詞以及判定條件如下。

定義1 慢任務(wù)：節(jié)點(diǎn)中某個(gè)task進(jìn)度值比同job中的task平均進(jìn)度的臨界值要低，用參數(shù)SlowTaskPoint表示，取值為25%。

定義2 好作業(yè)：計(jì)算概率不會(huì)造成TaskTracker作業(yè)產(chǎn)生過(guò)載情況的就是好作業(yè)，好作業(yè)將在系統(tǒng)中優(yōu)先進(jìn)行調(diào)度。

定義3 等待作業(yè)：導(dǎo)致TaskTracker出現(xiàn)過(guò)載的作業(yè)為等待作業(yè)，這種形式的作業(yè)會(huì)滯后運(yùn)行調(diào)度。

定義4 作業(yè)屬性：將作業(yè)大小、道數(shù)值設(shè)置為作業(yè)屬性的基本變量。

定義5 資源屬性：該屬性表示的是一個(gè)計(jì)算節(jié)點(diǎn)在具體運(yùn)作時(shí)資源的基本狀態(tài)。

在實(shí)際應(yīng)用過(guò)程中，本文的計(jì)量值選取了具有代表性的節(jié)點(diǎn)剩余CPU使用率、系統(tǒng)內(nèi)部剩余的內(nèi)存、硬盤可用空間大小這些基本的參數(shù)。

定義6過(guò)載條件判定：調(diào)度算法負(fù)載閾值HighLoad和LowLoad這兩個(gè)參數(shù)值設(shè)置為87%和66%。

對(duì)上述基本屬性進(jìn)行分析，任何一個(gè)屬性在實(shí)際應(yīng)用中都存在一個(gè)邊界區(qū)域，臨近此區(qū)域?qū)?huì)造成節(jié)點(diǎn)過(guò)載的情況，全部臨界區(qū)域相近的點(diǎn)有機(jī)的構(gòu)成一個(gè)超平面[8]，且作業(yè)屬性、數(shù)據(jù)信息的資源需要采取獨(dú)立的方式進(jìn)行分析與假設(shè)，采用優(yōu)化后的樸素貝葉斯分類器能夠合理有效地對(duì)作業(yè)任務(wù)進(jìn)行處理[9]。

改進(jìn)貝葉斯作業(yè)在調(diào)度過(guò)程中，目標(biāo)函數(shù)f(x)在有效的集合V中按照指定的技術(shù)方式進(jìn)行取值。

V={gjob，wjob}

(3)

其中：Gjob為好作業(yè)；wjob為等待作業(yè)

按照樸素貝葉斯定理實(shí)現(xiàn)作業(yè)分類，最終的計(jì)算方式為式(4)。

(4)

實(shí)例νj相關(guān)屬性值可由上述定義描述。

貝葉斯公式經(jīng)過(guò)一定形式的變換，獲取到具體的公式為式(5)。

(5)

將稀疏矩陣所存在的問(wèn)題綜合分析，在給定目標(biāo)值的情況下對(duì)每個(gè)屬性相互獨(dú)立性條件進(jìn)行定義

(6)

式(5)中P(a,…,an)在為固定值，需要對(duì)其大小進(jìn)行綜合性分析與對(duì)比，將其簡(jiǎn)化后的形式如式(7)。

(7)

式(7)在條件獨(dú)立性假設(shè)條件下，可簡(jiǎn)化為式(8)。

(8)

式中，對(duì)于?νj∈{gjob,wjob},在對(duì)應(yīng)最大值情況下，νj取值gjob時(shí)將該job確認(rèn)為好作業(yè)，νj取值wjob將該job確認(rèn)為等待作業(yè)。

對(duì)于?νj∈{gjob,wjob}、?i∈[1,n]，估算P(νi)比較容易得到，計(jì)算P(ai|νj)的計(jì)算量比要計(jì)算P(a1,…,an|νj)要小得多，它們均可在不同作業(yè)類別與屬性數(shù)據(jù)訓(xùn)練樣本集中組合，來(lái)獲得概率值或者直接設(shè)置默認(rèn)概率值。

這樣如果節(jié)點(diǎn)產(chǎn)生空閑，作業(yè)調(diào)度服務(wù)器依照心跳信息對(duì)閑置狀態(tài)進(jìn)行發(fā)現(xiàn)，利用改進(jìn)的貝葉斯調(diào)度算法在作業(yè)隊(duì)列中，選取作業(yè)任務(wù)按其上述的算法公式對(duì)其科學(xué)有效地劃分。通常情況下，這種改進(jìn)的作業(yè)調(diào)度算法能夠精準(zhǔn)高效的獲取到適當(dāng)?shù)淖鳂I(yè)任務(wù)[10-11]。

2 改進(jìn)貝葉斯調(diào)度算法的流程

通過(guò)改進(jìn)貝葉斯調(diào)度算法的綜合分析與闡述，采用簡(jiǎn)單的學(xué)習(xí)過(guò)程或設(shè)置默認(rèn)概率，結(jié)合過(guò)載與心跳信息，將該參數(shù)作為調(diào)節(jié)因子進(jìn)行具體地應(yīng)用，系統(tǒng)在實(shí)踐操作過(guò)程通過(guò)自適應(yīng)地調(diào)節(jié)形式，以不同屬性值在任務(wù)操作時(shí)的基本情況為核心，對(duì)其先驗(yàn)概率大小進(jìn)行判定[12]，所對(duì)應(yīng)的實(shí)時(shí)調(diào)度算法操作流程如圖1所示。

在整個(gè)操作過(guò)程中，對(duì)地震資料數(shù)據(jù)信息的綜合分析與調(diào)度，能夠有效地獲取到經(jīng)過(guò)優(yōu)化改進(jìn)的貝葉斯調(diào)度算法流程(圖2)。

圖1 改進(jìn)的貝葉斯調(diào)度算法流程圖Fig.1 The flowchart of improved the Bayes scheduling algorithm

圖2 貝葉斯算法改進(jìn)的并行調(diào)度流程圖Fig.2 The flowchart of parallel scheduling based on improved Bayes algorithm

根據(jù)圖2能夠清晰地判定出，經(jīng)過(guò)改進(jìn)的貝葉斯調(diào)度算法的基本步驟：

1) JobTracker需要在TaskTracker中定時(shí)有效地獲取到相應(yīng)的心跳信息，結(jié)合心跳信息實(shí)時(shí)對(duì)作業(yè)任務(wù)及節(jié)點(diǎn)屬性等參數(shù)進(jìn)行相應(yīng)的處理。

2) 通過(guò)上個(gè)步驟的操作，能夠判斷某個(gè)節(jié)點(diǎn)是否為空閑節(jié)點(diǎn)的參數(shù)條件，如果不是空閑節(jié)點(diǎn)可以停止操作；如果是空閑節(jié)點(diǎn)，需要在此環(huán)節(jié)中調(diào)入作業(yè)，繼續(xù)步驟3)的操作。

3) JobTracker周期性地對(duì)集群內(nèi)部執(zhí)行的任務(wù)進(jìn)行綜合性的分析與計(jì)算，并且需要綜合性的將所計(jì)算獲取到的節(jié)點(diǎn)的任務(wù)狀態(tài)與慢任務(wù)進(jìn)行結(jié)合，對(duì)臨界值SlowTaskPoint深入分析和對(duì)比，如果運(yùn)作過(guò)程中有慢任務(wù)，需要在其中對(duì)慢任務(wù)進(jìn)行有效地處理；沒(méi)有慢任務(wù)存在的情況下，直接操作步驟4)即可。

4) 針對(duì)章任務(wù)劃分后的作業(yè)隊(duì)列，在隊(duì)列有效的選取除本地節(jié)點(diǎn)數(shù)據(jù)相對(duì)應(yīng)的任務(wù)執(zhí)行，如果不對(duì)劃分后的數(shù)據(jù)信息進(jìn)行科學(xué)性的處理，需要進(jìn)行步驟5)的操作。

5) 通過(guò)改進(jìn)的貝葉斯調(diào)度計(jì)算算法，利用最大概率方式有效地獲取到最佳的作業(yè)，將其有效的劃分為4操作步驟：①JobTracker作用是對(duì)TaskTracker的心跳信息進(jìn)行有效的接收；② 結(jié)合設(shè)置操作過(guò)程中相應(yīng)的過(guò)載條件和學(xué)習(xí)階段相應(yīng)的屬性概率，對(duì)上次通過(guò)貝葉斯分類調(diào)度方式所實(shí)施的TaskTracker的任務(wù)在具體操作過(guò)程中的執(zhí)行狀況進(jìn)行全面的分析與對(duì)比，進(jìn)而能夠重新生成每一種屬性在最佳狀態(tài)中的概率值；③在系統(tǒng)中最長(zhǎng)的等待隊(duì)列中進(jìn)行作業(yè)的選取，通過(guò)公式(8)的最大概率估計(jì)，有效的明確作業(yè)的劃分；④如果獲取到的計(jì)算作業(yè)是好作業(yè)，需要將此類作業(yè)分配至資源節(jié)點(diǎn)對(duì)其進(jìn)行專業(yè)性的處理，有效的實(shí)現(xiàn)此階段的調(diào)度，反之繼續(xù)進(jìn)行③作業(yè)的分析與判。

6) 在TaskTracker任務(wù)中有效的實(shí)施之后，該TaskTracker需要結(jié)合心跳信息，把任務(wù)的實(shí)際情況向JobTracker進(jìn)行傳送，繼續(xù)步驟1)～步驟6)的操作。

3 實(shí)驗(yàn)測(cè)試

將改進(jìn)的貝葉斯調(diào)度算法在應(yīng)用過(guò)程中，與MapReduce常用的FIFO、公平調(diào)度以及計(jì)算能力調(diào)度的三種調(diào)度算法進(jìn)行對(duì)比。

FIFO調(diào)度算法在實(shí)施過(guò)程中十分地簡(jiǎn)便，而公平份額調(diào)度算法與計(jì)算能力調(diào)度算法則需要在任務(wù)服務(wù)器上設(shè)置最多同時(shí)運(yùn)行的任務(wù)數(shù)目，并且需要增加對(duì)逐個(gè)資源的描述，不僅增加提交任務(wù)的難度及工作量，對(duì)沒(méi)有經(jīng)驗(yàn)的管理員來(lái)言，每更換一批任務(wù)是非常大的難題，若參數(shù)設(shè)置不合適也會(huì)對(duì)整體運(yùn)行性能造成不利影響。因此，在測(cè)試中需要對(duì)CPU設(shè)置占用較多的參數(shù)方式，因而減少對(duì)公平調(diào)度算法和計(jì)算能力調(diào)度算法的性能影響[13]。

在測(cè)試中，筆者采用節(jié)點(diǎn)的靜態(tài)分配與全局?jǐn)?shù)組存儲(chǔ)資源，通過(guò)簡(jiǎn)單的訓(xùn)練學(xué)習(xí)，設(shè)置在等待作業(yè)與好作業(yè)的屬性概率，分別計(jì)算600、500、400及200炮地震資料數(shù)據(jù)，并對(duì)各炮集處理結(jié)果進(jìn)行比較，在實(shí)驗(yàn)操作過(guò)程中相應(yīng)炮集數(shù)據(jù)處理的對(duì)比結(jié)果如圖4所示。

圖3 處理不同炮數(shù)據(jù)的調(diào)度算法比較Fig.3 Comparison of different scheduling algorithms in processing mass gun data

根據(jù)圖4中的數(shù)據(jù)信息能夠分析出，F(xiàn)IFO調(diào)度算法在實(shí)際應(yīng)用中的處理效率分布與直線較為相近，與同種類型的作業(yè)運(yùn)作情況相比，在安全穩(wěn)定性方面較為理想，但調(diào)度算法運(yùn)作效率比較差。改進(jìn)的調(diào)度算法在實(shí)際應(yīng)用中，首先對(duì)簡(jiǎn)單的學(xué)習(xí)過(guò)程進(jìn)行一定的優(yōu)化，隨著操作過(guò)程中數(shù)據(jù)信息的不斷增加，運(yùn)行時(shí)間與其他三種調(diào)度算法相比具有一定顯著性的功能特性。

4 結(jié)論

將改進(jìn)的貝葉斯分類調(diào)度技術(shù)操作算法與系統(tǒng)默認(rèn)調(diào)度算法進(jìn)行綜合性的分析與對(duì)比，發(fā)現(xiàn)此算法的優(yōu)勢(shì)體現(xiàn)如下：

1) 通過(guò)自適應(yīng)的對(duì)相應(yīng)屬性特征，設(shè)置默認(rèn)概率值進(jìn)行調(diào)整，在節(jié)點(diǎn)出現(xiàn)空閑的情況下，本地慢任務(wù)可以優(yōu)先進(jìn)行技術(shù)操作。

2) 對(duì)相應(yīng)任務(wù)操作過(guò)程中的最大估計(jì)剩余時(shí)間進(jìn)行分析，對(duì)慢任務(wù)的認(rèn)定不是通過(guò)簡(jiǎn)單的進(jìn)度值來(lái)確定，而是某個(gè)task的進(jìn)度值小于同一job下task平均進(jìn)度某一百分比時(shí)才認(rèn)定為慢任務(wù)。

3) 在慢任務(wù)未出現(xiàn)的情況下，將優(yōu)先調(diào)度靜態(tài)作業(yè)隊(duì)列中相關(guān)的任務(wù)執(zhí)行，進(jìn)一步提高M(jìn)ap并行任務(wù)的速度，避免頻繁交互通信及復(fù)制數(shù)據(jù)，最大限度減小云計(jì)算環(huán)境的資源浪費(fèi)。

將上述調(diào)度算法與地震資料數(shù)據(jù)信息處理相結(jié)合，這種技術(shù)方式能夠合理地減少數(shù)據(jù)信息在不同節(jié)點(diǎn)間中進(jìn)行數(shù)據(jù)處理的資源消耗，大大增強(qiáng)算法的運(yùn)算效率。

[1] 邢永山.基于云計(jì)算的并行調(diào)度的研究[D].青島：中國(guó)石油大學(xué)(華東),2012. XING Y S. Study on parallel dispatching based on cloud computing [D]. Qingdao: China University of Petroleum (East China), 2012.(In Chinese)

[2] LU HAO,LIN JUN,ZENG XIAO-XIAN.Research and application of improved naive bayesian classification algorithm[J].Journal of Hunan University Natural Sciences,December 2012,39(12):56-61.

[3] JIN L-C,WAN W-G,CUI B.A new multimedia classification approach: Bayesian of inductive cognition algorithm based on dirichlet process[J].Imaging Science Journal,December 2010,58(6):331-339.

[4] AL BATAINEH,MOHAMMAD,AL-QUDAH ZOUHAIR.A novel gene identification algorithm with Bayesian classification[J].Biomedical Signal Processing and Control,January 1,2016,31(4):6-15.

[5] KIM HYUN-CHUL,GHAHRAMANI, ZOUBIN.Bayesian Gaussian process classification with the EM-EP algorithm[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(12):1948-1959.

[6] WANG X Z.A layered Bayesian network intrusion detection algorithm[J].Metallurgical and Mining Industry,2015,7(9):724-732.

[7] ZHANG YU,ZHOU GUOXU,JIN JING.Sparse Bayesian classification of EEG for brain-computer interface[J].IEEE Transactions on Neural Networks and Learning Systems,September 23,2015,30(8)：99-102.

[8] GOPAL SIDDHARTH,YANG YIMING.Hierarchical bayesian inference and recursive regularization for large-scale classification[J].ACM Transactions on Knowledge Discovery from Data,2015, 9(31):136-140.

[9] LI ZHI QIANG,YANG DE QUAN,TAN YUAN.An improved naive Bayesian classification algorithm for sentiment classification of microblogs[J].Applied Mechanics and Materials.2014,43(5):3614-3620.

[10]RIDGWAY JAMES,ALQUIER PIERRE.Chopin Nicolas PAC-Bayesian AUC classification and scoring[J].Advances in Neural Information Processing Systems,2014,21(1):658-666.

[11]DU CHANGYING,HE JIA,ZHUANG FUZHEN.Nonparametric bayesian multi-task large-margin classification[J].Frontiers in Artificial Intelligence and Applications,2014, 63(2): 255-260.

[12]SALAMA KHALID M,FREITAS, ALEX A.Classification with cluster-based Bayesian multi-nets using Ant Colony Optimisation[J].Swarm and Evolutionary Computation,2014, 18:54-70.

[13]HU DIE,WAN MENG.Common bayesian network for classification of EEG-based multiclass motor imagery BCI[J].IEEE Transactions on Systems,June 2016,46(6):843-854.

Parallel scheduling algorithm with improved Bayesian classification algorithm

LIANG Yuxuan, XING Yongshan, ZHANG Qian

(School of Computer and Communication Engineering, China University of Petroleum (East China), Qingdao 266580, China)

Based on the analysis of job partitioning and existing scheduling strategies, we proposes a job scheduling strategy that improves the Bayesian classification algorithm, and expounds the problems faced by the Bayesian classifier and the MapReduce default scheduling method in dealing with large-scale data in this paper. The concrete idea and the whole process of the improved algorithm, describes the concrete realization of the improved algorithm, and analyzes the advantages of the algorithm compared with other scheduling algorithms are introduced. The experimental results show that the improved Bayesian scheduling algorithm is more effective than the conventional scheduling algorithm.

Bayesian classification algorithm; MapReduce seimic data; processing; parallel scheduling

2016-12-17 改回日期：2017-03-08

國(guó)家自然基金(61671482)

梁宇軒(1996-)，男，碩士,研究方向?yàn)楦咝阅苡?jì)算,E-mail：liangh@upc.edu.cn。

張千(1980-)，女，博士，副教授，研究方向?yàn)楦咝阅苡?jì)算，E-mail：zhangqian@upc.edu.cn。

1001-1749(2017)03-0411-05

TP 319

A

10.3969/j.issn.1001-1749.2017.03.18