面向GPU平台的复杂网络core分解方法研究

发布时间：2022-02-13 09:21

　　在复杂网络理论中,core分解是一种最基本的度量网络节点"重要性"并分析核心子图的方法.Core分解广泛应用于社交网络的用户行为分析、复杂网络的可视化、大型软件的代码静态分析等应用.随着复杂网络的图数据规模和复杂性的增大,现有研究工作基于多核CPU环境设计core分解并行算法,由于CPU核数和内存带宽的局限性,已经无法满足大数据量的高性能计算需求,严重影响了复杂网络的分析应用.通用GPU提供了1万以上线程数的高并行计算能力和高于100GB/s访存带宽,已被广泛应用于大规模图数据的高效并行分析,如广度优先遍历和最短路径算法等.为了实现更为高效的core分解,提出面向GPU平台下的复杂网络core分解的两种并行策略.第1种RLCore策略基于图遍历思想,利用GPU高并发计算能力对网络图结构自底向上遍历,逐步迭代设置各节点所属的core层;第2种ESCore策略基于局部收敛思想,对各节点从邻居节点当前值进行汇聚计算更新直至收敛.ESCore相比RLCore能够大大降低遍历过程中GPU线程更新同一节点的同步操作开销,而其算法的迭代次数受收敛率的影响.在真实网络图数据上的实验结果表明,所提出的两... 

【文章来源】：软件学报. 2020,31(04)北大核心EICSCD

【文章页数】：15 页

【部分图文】：

Fig.2ParallelexecutionflowofRLCorecoredecomposition图2RLCore并行策略流程示例(a)RemoveList第1步对节点状态更新(b)RemoveList第2步邻居节点同步

【参考文献】：
期刊论文
[1]基于Multi-GPU平台的大规模图数据处理[J]. 张珩,张立波,武延军.  计算机研究与发展. 2018(02)
[2]社会网络节点影响力分析研究[J]. 韩忠明,陈炎,刘雯,原碧鸿,李梦琪,段大高.  软件学报. 2017(01)



本文编号：3622932