科研之友
微信
新浪微博
Facebook
分享链接
摘要
分布式图计算在许多领域有着广泛的应用,图分割是分布式图计算的基础.已有分割算法大多只考虑图的简单拓扑特性,它们将图计算系统视为同构系统,或最多考虑CPU计算能力及通信带宽的不同.然而,目前包含GPU的异构计算系统已经越来越普遍,由于GPU独特的并行计算架构和并行计算模式,不考虑GPU计算特点的图分割算法不能获得异构环境下最优的分割方案.本文通过分析及实验发现,计算负载特性对于估算处理节点的图计算时间有很大的帮助.在此基础上,本文提出度变异系数和分片通达度两个负载特征参数,给出了通过数据集采样和离线测试获取负载特征参数到处理器负载计算时间的映射关系的实用方法,并结合以上工作实现了一个平台特性和负载特征感知的在线图分割算法.在真实图数据集上的测试表明,相比于工业界和学术界领先的图分割算法,本文提出的方法可获得最优的图分割方案,可令图计算系统的整体执行时间减少50%～70%.
- 单位
