基于NUMA延迟发送的时变图弱连通分量求解

摘要：

时变图连通分量已经被广泛应用到不同场景,?如交通路网建设、推荐系统的信息推送等.?然而当前多数连通分量求解方法忽视了NUMA体系结构对计算效率产生的影响,?即过高的远程内存访问延迟导致低下的算法执行效率.?本文针对时变图的弱连通分量求解问题,?提出一种基于NUMA延迟发送的时变图弱连通分量求解方法,?它通过合理的数据内存布局,?合理控制NUMA节点间的信息交换次数,?最大限度减少远程内存访问数量,?显著提高了算法执行效率.?实验结果表明,?该方法的性能明显优于当前流行的图处理系统Ligra和Polymer提供的方法.

关键词：弱连通分量、NUMA、延迟发送、时变图、图计算

所属期刊栏目：32

分类号：TP302.1;O646;TQ320.5

资助基金：福建省自然科学基金项目2020J01493

在线出版日期：2023-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：322-329