牟式標 金偉健

(義烏工商職業(yè)技術(shù)學(xué)院， 浙江 義烏 322000)

?

一種改進的基于粗糙集的云計算調(diào)度模型

牟式標 金偉健

(義烏工商職業(yè)技術(shù)學(xué)院， 浙江 義烏 322000)

針對調(diào)度分配效率不高的問題，提出了改進的基于粗糙集MapReduce的分配調(diào)度模型，該模型將MapReduce分配的線性處理改造成基于多處理器的模糊計算。描述了具體的實現(xiàn)算法和模型設(shè)計，在Hadoop平臺上對該模型進行了實驗分析。實驗結(jié)果表明，在復(fù)雜云計算環(huán)境下，使用基于粗糙集的MapReduce的分配調(diào)度模型具有良好的執(zhí)行效率和擴展性。

MapReduce； 粗糙集； Hadoop； 云計算

在當(dāng)前人工智能領(lǐng)域中，粗糙集理論被用于處理模糊或者不精確的難題，其原理是從大量數(shù)據(jù)中挖掘潛在的和有價值的知識。它與概率論、證據(jù)理論的不同之處在于：其不通過大量樣本數(shù)據(jù)進行統(tǒng)計分析，即無需指定隸屬度函數(shù)。云計算的蓬勃發(fā)展為大數(shù)據(jù)的處理提供了許多云計算的框架，例如GFS、MapReduce 等計算平臺，但是協(xié)調(diào)和運用好任務(wù)和資源成為了各種平臺運行良好的關(guān)鍵。

針對上述問題，本次研究將粗糙集運算運用到MapReduce分配調(diào)度模型中，在云計算環(huán)境下，實現(xiàn)了基于粗糙集算法理論的分配調(diào)度算法。理論分析和仿真實驗表明，該方法在準確進行大數(shù)據(jù)的云計算時，有效地提高了分配和調(diào)度的效率。

1 理論依據(jù)及設(shè)計思想

1.1 粗糙集理論

粗糙集理論是波蘭數(shù)學(xué)家Z.Pawlak于1982年提出的一種數(shù)據(jù)分析理論，是一種新的處理模糊和不確定性知識的數(shù)學(xué)工具。在一定集合范圍內(nèi)，通過知識約簡，導(dǎo)出決策或分類規(guī)則[1]。

粗糙集理論運用模糊學(xué)的基本思想，通過約簡、合并生成一系列標準規(guī)則或者函數(shù)[2]。

待調(diào)度節(jié)點經(jīng)過預(yù)處理后，對主機和從屬機構(gòu)造一個知識系統(tǒng)。粗糙集的知識約簡主要體現(xiàn)為：在分配信息不丟失的前提下，依據(jù)決策屬性與知識系統(tǒng)條件屬性的關(guān)聯(lián)度和依賴性,建立主機和從屬機分配的粗糙集約簡規(guī)則，從而當(dāng)新的分配任務(wù)到來時，按照規(guī)則執(zhí)行決策。

1.2 MapReduce機制

MapReduce是Google提出的一個軟件框架[3-4]。它對大數(shù)據(jù)的處理方式采用分布式的模式，即：Map和Reduce，將大數(shù)據(jù)進行分塊，即將海量數(shù)據(jù)集分割成小數(shù)據(jù)集，然后交給不同的處理器進行處理，這樣就變成了并行處理，每個元數(shù)據(jù)就是一系列的〈鍵,值〉對，數(shù)據(jù)變換處理過程則簡化成Map 映射和Reduce規(guī)約2個階段。云計算MapReduce的算法，通常是將任務(wù)和輸入元素定義為獨立單元，即集合的思維，再由Map處理器處理，將一組〈鍵,值〉對換算成一組新的〈鍵,值〉對，再輸入到Reduce單元，執(zhí)行相關(guān)操作。MapReduce執(zhí)行過程如圖1所示。

2 算法的具體實現(xiàn)及新的MapReduce調(diào)度模型

當(dāng)前的MapReduce算法雖然考慮了并行的思想，但是智能性和效率不高，需要大量處理器才能準確地進行分配調(diào)度。針對這個問題，提出了一種改進的基于粗糙集MapReduce的任務(wù)調(diào)度算法。

2.1 運用MapReduce 機制改造變換過程

為了使待分配對象更加清晰，從空集開始，逐步選擇合適的分配對象加入，當(dāng)找到正確的分配對象時，參照MapReduce機制，可以把所有的對象都覆蓋到。

圖1 基于MapReduce的基本模型

基于MapReduce的Map和Reduce的設(shè)計階段有：

(1) Map階段。用粗糙集算法將待選Cj,m,n進行分塊，然后分解出最大和最小部分，規(guī)則計算為

Cj0,k,l=〈f(x,y),φn,m,(x,y)〉

得到局部結(jié)果〈Cj+1,k,l,Dj+1,k,l〉，最后輸出。

(2) Reduce階段。

輸入 〈Cj+1,k,l,Dj+1,k,l〉

根據(jù)

對Cj0,k,l進行矩陣求和運算，得到Cj+1,k,l，分別從行和列角度對Cj,m,n進行轉(zhuǎn)換，最終得到Cj0,k,l。

2.2 基于粗糙集約簡的MapReduce分配調(diào)度模型

基于改進的粗糙集MapReduce分配調(diào)度模型的建立如下：

(1) 將待分配對象切分成若干子對象；

(2) 用Map處理器將子分配對象轉(zhuǎn)換成〈Key,Value〉特征對象；

(3) 用Reduce處理器對特征對象做粗糙集變換求和；

(4) 用Reduce處理器輸出具備粗糙集變換的子對象，然后將其集成輸出。如圖2所示。

2.3 基于粗糙集的MapReduce調(diào)度模型

通過粗糙集約簡進行建模，依據(jù)MapReduce的Map和Reduce過程，實現(xiàn)調(diào)度分配的模糊化處理?；贖adoop[5-8]平臺下的MapReduce任務(wù)調(diào)度采用線性分配調(diào)度算法，其原理是將計算節(jié)點劃分為多個子節(jié)點，每個劃分計算一個調(diào)度節(jié)點，當(dāng)計算節(jié)點有空余子節(jié)點的時候，向主節(jié)點申請計算任務(wù)。新的調(diào)度算法是先按照調(diào)度分配的實例，生成約簡規(guī)則，在主節(jié)點收到請求后，將任務(wù)調(diào)度到相應(yīng)的節(jié)點。

圖2 基于粗糙集約簡的MapReduce模型

算法主要包括4個函數(shù)：Init，ReceiveM，Map，Reduce，其具體實現(xiàn)如下。

基于MapReduce的粗糙集約簡算法為：

Init ()

{∥初始化階段

F:L;：

Rules=?

}

ReceiveM (){∥獲取對象階段

While F≠?do

Begin

Rule=?;

For i=1 to 待分配對象 do

Computes POS(IND(cy0g0ao))

End

選擇使得card(POS(IND(wcoawq0))達到最大的對象a;

當(dāng)多個屬性同時達到最大值時，則選擇a屬性使得H(u0kkeo0|{a})最小;

SelecAttr=SelectAttr∪{a};

unSelecAttr=unSelectAttr-{a};

if POS(IND(weqmm00))≠? then

begin

用屬性SelectAttr從對象集POS(IND(8ywwuoi)) 導(dǎo)出規(guī)則；

將化簡后的規(guī)則并入到Rules;

End}

Map (){∥規(guī)則化Map階段

while(規(guī)則集眾的每條規(guī)則Rules) {

設(shè)定key 為該類別;}

while (該行對象記錄沒有讀完) {

讀下一個特征屬性，并記錄;

}

for ( Map輸出中間過程向量){

解析value;

}}

3 實驗分析

在Hadoop 0.20.0[9-12]開發(fā)平臺上進行仿真實驗， 操作系統(tǒng)為LINUX，基本PC配置為:雙核 8 G CPU，Java Development Kit 1.7版本。

同時，基于規(guī)則集的調(diào)度算法可以使Map及Reduce對象更加可靠，使調(diào)度分配的時間和穩(wěn)定性加強，但線性變換算法的執(zhí)行情況不可控。由于串行執(zhí)行的原因，處理器處理時間的多少表現(xiàn)在當(dāng)前運行的軟硬件環(huán)境上。因此從自適應(yīng)角度分析，基于 MapReduce的粗糙集約簡具有更加穩(wěn)定的自適應(yīng)優(yōu)勢。

4 結(jié)語

引入粗糙集理論到MapReduce的分配設(shè)計中，提出了一種新的粗糙集約簡的分配調(diào)度模型。為了提高云計算資源調(diào)度的效率, 并利于實時應(yīng)用, 先通過粗糙集產(chǎn)生資源分配調(diào)度規(guī)則，再通過規(guī)則搜索分配調(diào)度對象。為提高調(diào)度分配的智能性, 提出將粗糙集應(yīng)用到云計算的資源分配調(diào)度中，該并行算法可以達到負載平衡且無效分配少的目的, 適用于粗糙集約簡。

[1] 鄧維斌,王國胤,胡峰.基于優(yōu)勢關(guān)系粗糙集的自主學(xué)習(xí)式模型[J].計算機學(xué)報,2014,37(12):2408-2418.

[2] 張艷,孫世新,劉錦德.網(wǎng)格結(jié)構(gòu)上圖像小波變換的并行算法[J].計算機工程與科學(xué),2000,22(3):25-27.

[3] ZADEH L A. Responses to Elkan: Why the Success of Fuzzy Logic is not Paradoxical[J].IEEE Expert, 2003, 9(4):43-46.

[4] 王攀峰,杜云飛,周海芳，等.基于復(fù)小波變換的遙感圖像并行融合算法[J].計算機工程與科學(xué),2008,30(3):35-39.

[5] BURROWS M. The Chubby Lock Service for Loosely-Coupled Distributed Systems[J].Proceedings of the 7th Symposium on Operating Systems Design and Implementation,2006, 6(2):335-350.

[6] BERLINSKA J, DROZDOWSKI M. Scheduling Divisible MapReduce Computations[J].Journal of Parallel and Distributed Computing, 2011, 71 (3):450-459.

[7] SANDHOLM T, LAI K. Dynamic Proportional Share Scheduling in Hadoop Job Scheduling Strategies for Parallel Processing[J].Dynamic Proportional Share Scheduling in Hadoop Job Scheduling Strategies for Parallel Processing, 2010, 62 (2):110-131.

[8] KAMBATLA K. Towards Optimizing Hadoop Provisioning in the Cloud[J].Proc of the First Workshop on Hot Topics in Cloud Computing, 2009, 3(2):118-118.

[9] WU R, SHUAI L,LIAO H. Cyclic Workflow Execution Mechanism on Top of MapReduce Framework[C]∥Seventh International Conference on Semantics,Knowledge and Grids.Washington,DC: IEEE Computer Society,2011: 28 -35．

[10] NIELSEN O M, HEGLAND M. Parallel Performance of Fast Wavelet Transform [J]. International Journal of High Speed Computing, 2000, 11 (1) : 55-73.

[11] WANG C, WANG Q, REN K. Privacy-Preserving Public Auditing for Data Storage Security in Cloud Computing[J].In Proceedings of IEEE INFOCOM, 2010, 3(2):59-60.

[12] PIKE R,DORWARD S, GRIESEMER R，et al. Interpreting the Data: Parallel Analysis with Sawzall[J]. Scientific Programming,2005,13(4):277-298.

An Improved Cloud Computing Dispatch Model Based on Rough Set Selection

MUShibiaoJINWeijian

(Yiwu Industrial & Commercial College, Yiwu Zhejiang 322000, China)

At present scheduling allocation efficiency is not high, so in this paper an improved cloud computing dispatch model based on rough set selection MapReduce is proposed. This model transforms the line process to parallel computing based on rough set theory. Specific implementation algorithm and model design are also given, and the experimental result on Hadoop platform shows that MapReduce allocation scheduling model based on rough set selection is more efficient and more scalable.

MapReduce; rough set; Hadoop; cloud computing

2015-12-30

浙江省教育科學(xué)規(guī)劃課題“以社會服務(wù)IT項目為載體的程序語言類課程設(shè)計研究” (2015SCG196)

牟式標(1979 — )，男，講師，研究方向為計算機應(yīng)用。

TP393

A

1673-1980(2016)05-0071-04