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