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

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

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

【部分圖文】：

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

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



本文編號(hào)：3622932