發(fā)布時間：2025-01-09 05:50

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

【文章頁數】：16 頁

【部分圖文】：

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

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

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

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

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

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

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

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

本文編號：4025245