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

夏 菲

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

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

夏 菲

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

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

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

1 MapReduce相關理論

1.1 MapReduce

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

1.2 MapReduce執行程序

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

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

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

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

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

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

7.當所有的Map和Reduce作業都完成了，master喚醒正版的user program MapReduce函數調用返回userprogram的代碼。

2 可行性分析

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

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

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

（6）end for

（8）Job Begin

（12）end for

（15）Job End;

（16）n++;

（17）end while

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

4 結語

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

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

[2]黃斌.許舒人.蒲衛.基于MapReduce的數據挖掘平臺設計與實現[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