夏 菲

（東北石油大學(xué),大慶,163000）

一種基于MapReduce的分布式極圖構(gòu)造算法

夏 菲

（東北石油大學(xué),大慶,163000）

目前，傳統(tǒng)的單處理程序在較短的時(shí)間內(nèi)并不能及時(shí)解決問題，在這種背景下，大規(guī)模的圖數(shù)據(jù)處理技術(shù)成為當(dāng)前計(jì)算機(jī)領(lǐng)域的研究前沿。在研究的過(guò)程中極圖構(gòu)造法作為一個(gè)重要的研究?jī)?nèi)容，引起了越來(lái)越廣泛的關(guān)注。本文主要研究MapReduce基礎(chǔ)理論知識(shí)，以及基于MapReduce的分布式極圖構(gòu)造算法。

MapReduce；分布式；極圖構(gòu)造法；設(shè)計(jì)

1 MapReduce相關(guān)理論

1.1 MapReduce

MapReduce編程模型是由谷歌工程師率先提出的，其主要運(yùn)用的領(lǐng)域是大規(guī)模數(shù)據(jù)的并行預(yù)算。從用戶的角度出發(fā)，MapReduce共分為兩個(gè)最為基本的階段分別是Map和Reduce階段。在其中的任何一個(gè)階段輸入的都是一系列的鍵值對(duì)，其每一個(gè)階段的輸出的同樣也是一系列的鍵值對(duì)，其可以用以下的公式進(jìn)行表示。

1.2 MapReduce執(zhí)行程序

1.MapReduce庫(kù)在工作的過(guò)程中需要先將user program輸入的文件進(jìn)行劃分，每一分都有16MB到64MB，在此基礎(chǔ)之上使用fork將用戶的進(jìn)程復(fù)制到集群內(nèi)的其他機(jī)器上。

2.user program的副本之中有一個(gè)master，其余都是worker，master主要負(fù)責(zé)調(diào)度，為閑置的worker分配作業(yè)。

3.被分配了Map作業(yè)的worker，開始讀取對(duì)應(yīng)分片的輸入數(shù)據(jù)，Map作業(yè)數(shù)量是由M決定的，和split一一對(duì)應(yīng);Map作業(yè)從輸入數(shù)據(jù)中抽取出鍵值對(duì)，每一個(gè)鍵值對(duì)都作為參數(shù)傳遞給map函數(shù)，map函數(shù)產(chǎn)生的中間鍵值對(duì)被緩存在內(nèi)存中。

4.緩存的中間鍵值對(duì)會(huì)被定期寫入本地磁盤，而且被分為R個(gè)區(qū)，R的大小是由用戶定義的，將來(lái)每個(gè)區(qū)會(huì)對(duì)應(yīng)一個(gè)Reduce作業(yè);這些中間鍵值對(duì)的位置會(huì)被通報(bào)給master，master負(fù)責(zé)將信息轉(zhuǎn)發(fā)給Reduceworker。

5.master通知分配了Reduce作業(yè)的worker它負(fù)責(zé)的分區(qū)在什么位置(肯定不止一個(gè)地方，每個(gè)Map作業(yè)產(chǎn)生的中間鍵值對(duì)都可能映射到所有R個(gè)不同分區(qū))，當(dāng)Reduceworker把所有它負(fù)責(zé)的中間鍵值對(duì)都讀過(guò)來(lái)后，先對(duì)它們進(jìn)行排序，使得相同鍵的鍵值對(duì)聚集在一起。因?yàn)椴煌逆I可能會(huì)映射到同一個(gè)分區(qū)也就是同一個(gè)Reduce作業(yè)，所以排序是必須的。

6.reduceworker遍歷排序后的中間鍵值對(duì)，對(duì)于每個(gè)唯一的鍵，都將鍵與關(guān)聯(lián)的值傳遞給reduce函數(shù)，reduce函數(shù)產(chǎn)生的輸出會(huì)添加到這個(gè)分區(qū)的輸出文件中。

7.當(dāng)所有的Map和Reduce作業(yè)都完成了，master喚醒正版的user program MapReduce函數(shù)調(diào)用返回userprogram的代碼。

2 可行性分析

設(shè)計(jì)分布式并行算法設(shè)計(jì)一個(gè)十分有效的反法是：通過(guò)對(duì)現(xiàn)在固有的并行算法進(jìn)行檢測(cè)和拓展，并在此基礎(chǔ)之上降之并行化。目前，對(duì)原始計(jì)算問題進(jìn)行分解的方法主要有以下兩種方案：第一種方案是按照計(jì)算算法的功能進(jìn)行劃分，被稱之為功能分解。第二種方法是按照算法的數(shù)據(jù)進(jìn)行劃分，也被稱之為域分解。第一種計(jì)算方案主要將關(guān)注的重點(diǎn)放在被執(zhí)行計(jì)算上，比較適合計(jì)算比較復(fù)雜，但是這些計(jì)算所涉及到的數(shù)據(jù)又相互重疊的數(shù)據(jù)。第二種計(jì)算方案主要是計(jì)算程序中的數(shù)據(jù)，這些數(shù)據(jù)既包括輸入數(shù)據(jù)也包括輸出數(shù)據(jù)，同時(shí)還有中間結(jié)果數(shù)據(jù)，在實(shí)際應(yīng)用的過(guò)程當(dāng)中絕大多數(shù)算法都采用了這種方法。無(wú)論是這兩種算法中的哪一種方案在使用的過(guò)程中，一個(gè)最為基本的要求是：在進(jìn)行劃分之后盡可能保證各個(gè)數(shù)據(jù)之間的獨(dú)立性。這樣每一個(gè)進(jìn)行數(shù)據(jù)處理的計(jì)算任務(wù)都不會(huì)再需要其他任務(wù)之中的數(shù)據(jù)，可以明顯建設(shè)任務(wù)間進(jìn)行通信需求的代價(jià)。因此在設(shè)計(jì)分布式極圖構(gòu)造算法時(shí),首先需要分析FCG算法中固有的并行性后再將其并行化。

在算法1階段所處理的圖像都是相互的獨(dú)立的，因此不需要其他基礎(chǔ)圖就可以獨(dú)立完成該圖的臨界圖構(gòu)造，在對(duì)一個(gè)基礎(chǔ)圖進(jìn)行計(jì)算時(shí)計(jì)算的復(fù)雜程度也比較低。待計(jì)算的基礎(chǔ)圖集合的規(guī)模將變得愈來(lái)愈龐大,并且隨著輸入數(shù)據(jù)規(guī)模的膨脹,FCG算法構(gòu)造出來(lái)的中間結(jié)果圖的規(guī)模也會(huì)達(dá)到相應(yīng)4-6倍的增長(zhǎng)。數(shù)據(jù)膨脹相對(duì)于在階段2中判定的構(gòu)造圖G'與已經(jīng)生成的臨界圖集合中的圖的同構(gòu)關(guān)系帶來(lái)了很嚴(yán)重的影響。

3 基于MapReduce的分布式極圖構(gòu)造算法設(shè)計(jì)

3.1 相關(guān)引理

（6）end for

（13）end for

（14）else

（15）if G is a critical graph and

（17）end if

（21）end for

（22）end if

（23）end for

（25）end while

（26）n++

（27）end while

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

通過(guò)對(duì)FCG算法的研究我們可以得出，串行算法FCG是以個(gè)嵌套循環(huán)算法，第2行到27行的循環(huán)代碼塊(可以將之標(biāo)記為代碼塊1)實(shí)現(xiàn)了構(gòu)造算法的整體過(guò)程,循環(huán)構(gòu)造了頂點(diǎn)數(shù)從6到且邊數(shù)不小于N的所有臨界圖集合。其中第4行至6行的for循環(huán)是對(duì)輸入的每一個(gè)n-1個(gè)頂點(diǎn)的臨界圖添加新頂點(diǎn)后得到集合的過(guò)程。而第7行至25行的while循環(huán)代碼塊(標(biāo)記為代碼塊2)是對(duì)集合:中的每一個(gè)圖添加與頂點(diǎn)vo相關(guān)聯(lián)的邊和刪除導(dǎo)致出現(xiàn)禁止子圖的其他邊的過(guò)程,其算法偽代碼。

（6）end for

（8）Job Begin

（12）end for

（15）Job End;

（16）n++;

（17）end while

系統(tǒng)在進(jìn)行算法并行計(jì)算時(shí)，代碼2的功能是由map函數(shù)實(shí)現(xiàn)的,將會(huì)由多個(gè)map函數(shù)并發(fā)的對(duì)個(gè)字輸入的數(shù)據(jù)子集合中的每一個(gè)圖進(jìn)行臨界圖構(gòu)造。下面以k個(gè)map與1個(gè)reduce的設(shè)計(jì)為例來(lái)說(shuō)明該過(guò)程。首先將臨界圖集合中的圖分成yt個(gè)子集。每個(gè)子集將由一個(gè)map負(fù)責(zé),那么第個(gè) map通過(guò)執(zhí)行代碼塊2中的操作來(lái)生成相應(yīng)的臨界圖集合,記作。Reduce函數(shù)主要實(shí)現(xiàn)了對(duì)這A個(gè)臨界圖子集合的合并運(yùn)算,即,合并所要實(shí)現(xiàn)的目的是為了過(guò)濾掉這些子集中相同構(gòu)造的臨界圖。通過(guò)一輪MapReduce過(guò)程完成了頂點(diǎn)數(shù)為n的臨界圖集合構(gòu)造過(guò)程,而通過(guò)引理4可知,本次Job作業(yè)的輸出結(jié)果將要作為下一輪頂點(diǎn)數(shù)為的臨界圖集合構(gòu)造過(guò)程的輸入數(shù)據(jù),最后經(jīng)過(guò)多輪構(gòu)造得到不同頂點(diǎn)下的臨界圖集合,其中最多邊數(shù)的即為所求極圖集合。如上式所示,算法FCG-MR完整的體現(xiàn)了這個(gè)分布式極圖構(gòu)造的過(guò)程。從算法FCG-MR中可以看出,對(duì)于頂點(diǎn)數(shù)不同的圖,都需要一輪MapReduce過(guò)程來(lái)實(shí)現(xiàn)其臨界圖的構(gòu)造過(guò)程,而每個(gè)過(guò)程都要分為兩個(gè)階段。第一階段處理已經(jīng)被劃分好的輸入數(shù)據(jù)子集,對(duì)集合中的每一個(gè)圖進(jìn)行臨界圖構(gòu)造,同時(shí)判同構(gòu)保證了每一個(gè)輸出的臨界圖集合中無(wú)同構(gòu)的圖。第二階段的主要工作是合并每個(gè)任務(wù)所構(gòu)造的臨界圖集合,同樣要確保沒有同構(gòu)的圖,即合并的目的就是要過(guò)濾掉那些由不同map任務(wù)產(chǎn)生的結(jié)果集合之間的同構(gòu)圖。

4 結(jié)語(yǔ)

近年來(lái)，隨著計(jì)算機(jī)科學(xué)的快速發(fā)展，在圖論研究中遇到的許多難題，越來(lái)越依靠與計(jì)算機(jī)通過(guò)算法進(jìn)行解決。進(jìn)行基于MapReduce分布式極圖算法的研究對(duì)于利用云計(jì)算技術(shù)對(duì)圖論領(lǐng)域的問題進(jìn)行研究具有重要的研究意義。

[1]于戈,谷略,鮑玉斌,王志剛.云計(jì)算環(huán)境下的大規(guī)模圖數(shù)據(jù)處理技術(shù).計(jì)算機(jī)學(xué)報(bào),2011(10).

[2]黃斌.許舒人.蒲衛(wèi).基于MapReduce的數(shù)據(jù)挖掘平臺(tái)設(shè)計(jì)與實(shí)現(xiàn)[J].華中科 技大學(xué)學(xué)報(bào)(自然科學(xué)版),2011(6).

夏菲，女 出生年1990-3-21，漢，本科，黑龍江省大慶市人。

A distributed pole figure construction algorithm based on MapReduce

Xia Fei
（Daqing Petroleum Institute Daqing 163000）

At present, the traditional single handler can not solve the problem in a timely manner,in this context,a massive figure data processing technology become the research frontier in the field of computer.The pole figure construction algorithm is the important content gains more and more attention.This paper mainly studies graphs basic theoretical knowledge, as well as distributed pole figure construction algorithm based on MapReduce.

MapReduce; Distributed;pole figure construction algorithm;design

TP301.6

A