GraphMapReduce圖計算框架
GraphMapReduce: 基于MapReduce編程模型的圖計算框架
(名詞約束: 頂點Vertex-圖中頂點;節(jié)點Process-計算單元節(jié)點),目錄說明:
代碼主要包含四個文件: gmr.cpp gmr.h algorithms.h graph.h
|__graph/---------#此目錄包含測試用的圖例數(shù)據(jù)
|__include/-------#此目錄包含所使用到的第三方庫的頭文件(目前只用到了ParMetis，去掉了GKlib)
|__lib/------------#包含了使用到的第三方庫
|__gmr.cpp------#程序的main函數(shù)入口和迭代循環(huán)
|__gmr.h---------#包含主要的計算過程函數(shù)computing()和計算結(jié)果更新函數(shù)updateGraph()
|__algorithm.h---#常用圖算法的MapReduce實現(xiàn)
|__graph.h-------#定義了圖數(shù)據(jù)結(jié)果和常用的集中圖操作函數(shù)
一. 框架的基礎(chǔ)
1. MPI:
結(jié)算節(jié)點之間通信通過MPI實現(xiàn)；
2. MapReduce編程模型
3. 圖劃分:
為了將整圖的不同部分放到不同的計算節(jié)點進行并行計算，需要將整劃分為若干子圖。本框架中每個子圖包含三個部分{inners, borders, neighbors}, inners表示子圖內(nèi)與其他子圖沒有連接的頂點；borders表示子圖內(nèi)與其他子圖又連接的頂點；neighbors表示子圖外與本子圖連接的頂點。
二、迭代計算過程
1. 數(shù)據(jù)交換:
第一步,先遍歷自己計算的子圖graph與其他子圖的鄰居情況,并收集需要向其他節(jié)點發(fā)送的字節(jié)數(shù),并申請發(fā)送緩沖區(qū);
第二步,通過MPI_Alltoall()與其他節(jié)點交換其他節(jié)點需要接受的字節(jié)數(shù),每個節(jié)點收到信息后,各自計算和申請接受數(shù)據(jù)需要的空間。
第三步,再次遍歷自己計算的子圖graph,并將需要發(fā)往其他節(jié)點的頂點信心拷貝到發(fā)送緩存char *sb;
第四部,調(diào)用MPI_Alltoallv(),將發(fā)送緩存中的數(shù)據(jù)發(fā)往各節(jié)點.
2. 計算1th/2:map
將子圖graph和接受緩沖區(qū)中的數(shù)據(jù)實例化為頂點Vertex，再調(diào)用業(yè)務邏輯函數(shù)map將Vertex生成key/value list。
3. 對生成key/value list進行排序: sort
4. 計算2th/2:reduce
將排序好的key/value list按照業(yè)務邏輯函數(shù)reduce進行規(guī)約.
5. 將reduce計算的結(jié)果更新到graph中
三. 編譯和運行
1. (not mandatory)切圖
切圖采用了metis庫，其源碼和說明位于include/metis中，其編譯使用可參考include/metis/README.md. 已經(jīng)有切好的例圖，位于graph/下。
2. 編譯gmr
make clean && make
3. 運行
mpirun -np graph_nparts ./gmr
四. 例子
4.1 PageRank
4.1.1. 如下包含10個頂點的簡單圖，劃分之后包含三個子圖subgraphs[3]:
4.1.2. 迭代過程
每個子圖現(xiàn)將自己的邊界頂點發(fā)送給其所連接的鄰居節(jié)點，采用MPI_Alltoall()實現(xiàn)；
-
在每個計算節(jié)點的內(nèi)部，將每個頂點映射為若干鍵值對: > {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});} 在每個節(jié)點內(nèi)將map生成的鍵值對按鍵值進行排序
-
根據(jù)鍵值，對鍵值相同的鍵值組執(zhí)行reduce函數(shù)
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是指向網(wǎng)頁j的網(wǎng)頁j數(shù)，n所有網(wǎng)頁數(shù)*/sum = 0.5 * sum + (1 - 0.5) / (sizeof(vs) / sizeof(Vertex) - 1); return {kvs.front().key, sum};}
4.2.3 PageRank終止點問題和陷阱問題
上述上網(wǎng)者的行為是一個馬爾科夫過程的實例，要滿足收斂性，需要具備一個條件： 圖是強連通的，即從任意網(wǎng)頁可以到達其他任意網(wǎng)頁： 互聯(lián)網(wǎng)上的網(wǎng)頁不滿足強連通的特性，因為有一些網(wǎng)頁不指向任何網(wǎng)頁，如果按照上面的計算，上網(wǎng)者到達這樣的網(wǎng)頁后便走投無路、四顧茫然，導致前面累 計得到的轉(zhuǎn)移概率被清零，這樣下去，最終的得到的概率分布向量所有元素幾乎都為0。假設(shè)我們把上面圖中C到A的鏈接丟掉，C變成了一個終止點，得到下面這 個圖：
另外一個問題就是陷阱問題，即有些網(wǎng)頁不存在指向其他網(wǎng)頁的鏈接，但存在指向自己的鏈接。比如下面這個圖：
上網(wǎng)者跑到C網(wǎng)頁后，就像跳進了陷阱，陷入了漩渦，再也不能從C中出來，將最終導致概率分布值全部轉(zhuǎn)移到C上來，這使得其他網(wǎng)頁的概率分布值為0，從而整個網(wǎng)頁排名就失去了意義。