在復(fù)雜網(wǎng)絡(luò)理論中,core分解是一種最基本的度量網(wǎng)絡(luò)節(jié)點"重要性"并分析核心子圖的方法.Core分解廣泛應(yīng)用于社交網(wǎng)絡(luò)的用戶行為分析、復(fù)雜網(wǎng)絡(luò)的可視化、大型軟件的代碼靜態(tài)分析等應(yīng)用.隨著復(fù)雜網(wǎng)絡(luò)的圖數(shù)據(jù)規(guī)模和復(fù)雜性的增大,現(xiàn)有研究工作基于多核CPU環(huán)境設(shè)計core分解并行算法,由于CPU核數(shù)和內(nèi)存帶寬的局限性,已經(jīng)無法滿足大數(shù)據(jù)量的高性能計算需求,嚴重影響了復(fù)雜網(wǎng)絡(luò)的分析應(yīng)用.通用GPU提供了1萬以上線程數(shù)的高并行計算能力和高于100GB/s訪存帶寬,已被廣泛應(yīng)用于大規(guī)模圖數(shù)據(jù)的高效并行分析,如廣度優(yōu)先遍歷和最短路徑算法等.為了實現(xiàn)更為高效的core分解,提出面向GPU平臺下的復(fù)雜網(wǎng)絡(luò)core分解的兩種并行策略.第1種RLCore策略基于圖遍歷思想,利用GPU高并發(fā)計算能力對網(wǎng)絡(luò)圖結(jié)構(gòu)自底向上遍歷,逐步迭代設(shè)置各節(jié)點所屬的core層;第2種ESCore策略基于局部收斂思想,對各節(jié)點從鄰居節(jié)點當(dāng)前值進行匯聚計算更新直至收斂.ESCore相比RLCore能夠大大降低遍歷過程中GPU線程更新同一節(jié)點的同步操作開銷,而其算法的迭代次數(shù)受收斂率的影響.在真實網(wǎng)絡(luò)圖數(shù)據(jù)上的實驗結(jié)果表明,所提出的兩... 

【文章來源】：軟件學(xué)報. 2020,31(04)北大核心EICSCD

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

【部分圖文】：

Fig.2ParallelexecutionflowofRLCorecoredecomposition圖2RLCore并行策略流程示例(a)RemoveList第1步對節(jié)點狀態(tài)更新(b)RemoveList第2步鄰居節(jié)點同步

【參考文獻】：
期刊論文
[1]基于Multi-GPU平臺的大規(guī)模圖數(shù)據(jù)處理[J]. 張珩,張立波,武延軍.  計算機研究與發(fā)展. 2018(02)
[2]社會網(wǎng)絡(luò)節(jié)點影響力分析研究[J]. 韓忠明,陳炎,劉雯,原碧鴻,李夢琪,段大高.  軟件學(xué)報. 2017(01)



本文編號：3622932