基于MapReduce編程模型的圖計算框架

</div>

一. 框架的基礎

1. MPI:

結算節點之間通信通過MPI實現；

2. MapReduce編程模型

3. 圖劃分:

為了將整圖的不同部分放到不同的計算節點進行并行計算，需要將整劃分為若干子圖。本框架中每個子圖包含三個部分{inners, borders, neighbors}, inners表示子圖內與其他子圖沒有連接的頂點；borders表示子圖內與其他子圖又連接的頂點；neighbors表示子圖外與本子圖連接的頂點。

二、迭代計算過程

1. 數據交換:

第一步,先遍歷自己計算的子圖graph與其他子圖的鄰居情況,并收集需要向其他節點發送的字節數,并申請發送緩沖區;

第二步,通過MPI_Alltoall()與其他節點交換其他節點需要接受的字節數,每個節點收到信息后,各自計算和申請接受數據需要的空間。

第三步,再次遍歷自己計算的子圖graph,并將需要發往其他節點的頂點信心拷貝到發送緩存char *sb;

第四部,調用MPI_Alltoallv(),將發送緩存中的數據發往各節點.

2. 計算1th/2:map

將子圖graph和接受緩沖區中的數據實例化為頂點Vertex，再調用業務邏輯函數map將Vertex生成key/value list。

3. 對生成key/value list進行排序: sort

4. 計算2th/2:reduce

將排序好的key/value list按照業務邏輯函數reduce進行規約.

5. 將reduce計算的結果更新到graph中

三. 編譯和運行

1. (not mandatory)切圖

切圖采用了metis庫，其源碼和說明位于include/metis中，其編譯使用可參考include/metis/README.md. 已經有切好的例圖，位于graph/下。

2. 編譯gmr

make clean && make

3. 運行

mpirun -np graph_nparts ./gmr

四. 例子

4.1 PageRank

4.1.1. 如下包含10個頂點的簡單圖，劃分之后包含三個子圖subgraphs[3]:

4.1.2. 迭代過程

• 每個子圖現將自己的邊界頂點發送給其所連接的鄰居節點，采用MPI_Alltoall()實現；

• 在每個計算節點的內部，將每個頂點映射為若干鍵值對: > {key, value1},其中key in [neighbors], value1 = value / neighbors.size()

  void map(Vertex &v, std::list<KV> &kvs){
  int neighbor_count = 0;
  while(v.neighbors[neighbor_count] != 0)neighbor_count++;
  
  float value = v.value / neighbor_count;
  for (int i = 0; i < neighbor_count; i++)
      kvs.push_back({v.neighbors[i], value});
  }

• 在每個節點內將map生成的鍵值對按鍵值進行排序

• 根據鍵值，對鍵值相同的鍵值組執行reduce函數

  KV reduce(std::list<KV> &kvs) {
  float sum = 0.0;
  for (auto kv : kvs) {
      sum += kv.value;
  }
  
  /*Pagerank=a*(p1+p2+…Pm)+(1-a)*1/n，其中m是指向網頁j的網頁j數，n所有網頁數*/
  sum = 0.5 * sum + (1 - 0.5) / (sizeof(vs) / sizeof(Vertex) - 1); 
  return {kvs.front().key, sum};
  }

4.2.3 PageRank終止點問題和陷阱問題

上述上網者的行為是一個馬爾科夫過程的實例，要滿足收斂性，需要具備一個條件： 圖是強連通的，即從任意網頁可以到達其他任意網頁： 互聯網上的網頁不滿足強連通的特性，因為有一些網頁不指向任何網頁，如果按照上面的計算，上網者到達這樣的網頁后便走投無路、四顧茫然，導致前面累 計得到的轉移概率被清零，這樣下去，最終的得到的概率分布向量所有元素幾乎都為0。假設我們把上面圖中C到A的鏈接丟掉，C變成了一個終止點，得到下面這個圖：

另外一個問題就是陷阱問題，即有些網頁不存在指向其他網頁的鏈接，但存在指向自己的鏈接。比如下面這個圖：

上網者跑到C網頁后，就像跳進了陷阱，陷入了漩渦，再也不能從C中出來，將最終導致概率分布值全部轉移到C上來，這使得其他網頁的概率分布值為0，從而整個網頁排名就失去了意義。

4.2 單源最短路算法SSSP（DJ算法）

4.3 并行廣度優先搜索算法的MapReduce實現

4.4 二度人脈算法:廣度搜索算法

五、對比實驗

Processor\Platform | GMR | Spark | GraphX | GraphLab | Pregel | 1 | | | | | | 3 | | | | | | 8 | | | | | | 16 | | | | | | 64 | | | | | |