分布式圖計算在許多領域有著廣泛的應用,圖分割是分布式圖計算的基礎.已有分割算法大多只考慮圖的簡單拓撲特性,它們將圖計算系統(tǒng)視為同構系統(tǒng),或最多考慮CPU計算能力及通信帶寬的不同.然而,目前包含GPU的異構計算系統(tǒng)已經(jīng)越來越普遍,由于GPU獨特的并行計算架構和并行計算模式,不考慮GPU計算特點的圖分割算法不能獲得異構環(huán)境下最優(yōu)的分割方案.本文通過分析及實驗發(fā)現(xiàn),計算負載特性對于估算處理節(jié)點的圖計算時間有很大的幫助.在此基礎上,本文提出度變異系數(shù)和分片通達度兩個負載特征參數(shù),給出了通過數(shù)據(jù)集采樣和離線測試獲取負載特征參數(shù)到處理器負載計算時間的映射關系的實用方法,并結合以上工作實現(xiàn)了一個平臺特性和負載特征感知的在線圖分割算法.在真實圖數(shù)據(jù)集上的測試表明,相比于工業(yè)界和學術界領先的圖分割算法,本文提出的方法可獲得最優(yōu)的圖分割方案,可令圖計算系統(tǒng)的整體執(zhí)行時間減少50%～70%.

【文章頁數(shù)】：16 頁

【部分圖文】：

圖8 采用不同圖分割算法后全源最短路徑的執(zhí)行時間

圖7采用不同圖分割算法后PageRank的執(zhí)行時間圖9采用不同圖分割算法后多源BFS的執(zhí)行時間

圖9 采用不同圖分割算法后多源BFS的執(zhí)行時間

圖8采用不同圖分割算法后全源最短路徑的執(zhí)行時間圖10采用不同圖分割算法后圖路徑匹配的執(zhí)行時間

圖1 0 采用不同圖分割算法后圖路徑匹配的執(zhí)行時間

圖9采用不同圖分割算法后多源BFS的執(zhí)行時間可以看出，對于所有的圖算法-圖數(shù)據(jù)集組合，P&W＿Alg算法的分割效果最好，即在其生成的分割上運行圖算法的時間最短．與METIS和HEA＿Alg生成的分割方案相比，P&W＿Alg生成的分割方案可使PageRank算法的執(zhí)行時間平均縮短....

圖1 1 3種分割算法下的4個節(jié)點上的總執(zhí)行時間

可以看出，對于所有的圖算法-圖數(shù)據(jù)集組合，P&W＿Alg算法的分割效果最好，即在其生成的分割上運行圖算法的時間最短．與METIS和HEA＿Alg生成的分割方案相比，P&W＿Alg生成的分割方案可使PageRank算法的執(zhí)行時間平均縮短近50%，可使多源BFS算法的執(zhí)行時間至少縮短....

本文編號：4025245