基于NUMA延迟发送的时变图弱连通分量求解
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

福建省自然科学基金 (2020J01493)


NUMA-based Delayed Sending Method for Weakly Connected Components of Time-evolving Graph
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    The weakly connected components of the time-evolving graph have been widely used in many areas, such as traffic network construction, information push of recommendation systems, etc. However, most methods for the weakly connected components ignore the impact of the non-uniform memory access (NUMA) architecture, that is, the high remote memory access delay leads to low execution efficiency. This study proposes a NUMA-based delayed sending method to find the weakly connected components of the time-evolving graph. It minimises the number of remote accesses and improves computational efficiency through reasonable data memory layout and controlling the number of exchanges between NUMA nodes. The experimental results show that the performance of the NUMA-based delayed sending method is better than the methods provided by the current popular graph processing systems Ligra and Polymer.

    参考文献
    相似文献
    引证文献
引用本文

梁锐杰,程永利.基于NUMA延迟发送的时变图弱连通分量求解.计算机系统应用,2023,32(3):322-329

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2022-08-23
  • 最后修改日期:2022-09-27
  • 录用日期:
  • 在线发布日期: 2022-12-23
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号