一種基于MapReduce的分布式極圖構造算法

夏 菲

（東北石油大學,大慶,163000）

一種基于MapReduce的分布式極圖構造算法

夏 菲

（東北石油大學,大慶,163000）

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

MapReduce；分布式；極圖構造法；設計

1 MapReduce相關理論

1.1 MapReduce

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

1.2 MapReduce執(zhí)行程序

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

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

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

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

5.master通知分配了Reduce作業(yè)的worker它負責的分區(qū)在什么位置(肯定不止一個地方，每個Map作業(yè)產(chǎn)生的中間鍵值對都可能映射到所有R個不同分區(qū))，當Reduceworker把所有它負責的中間鍵值對都讀過來后，先對它們進行排序，使得相同鍵的鍵值對聚集在一起。因為不同的鍵可能會映射到同一個分區(qū)也就是同一個Reduce作業(yè)，所以排序是必須的。

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

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

2 可行性分析

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

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

3 基于MapReduce的分布式極圖構造算法設計

3.1 相關引理

（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 算法設計

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

（6）end for

（8）Job Begin

（12）end for

（15）Job End;

（16）n++;

（17）end while

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

4 結語

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

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

[2]黃斌.許舒人.蒲衛(wèi).基于MapReduce的數(shù)據(jù)挖掘平臺設計與實現(xiàn)[J].華中科 技大學學報(自然科學版),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