平台和负载特征感知的在线图分割算法

• 作者: 华蓓 陆李
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 图计算 图分割 GPU 异构系统 负载特征挖掘
• 年，卷（期）: 2020,（7）
• 所属期刊栏目: 大数据与智能图象处理
• 页码范围: 1230-1245
• 页数: 16页
• 分类号: TP391
• 字数: 16261字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2020.01230

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	华蓓	中国科学技术大学计算机科学与技术学院	37	225	8.0	14.0
2	陆李	中国科学技术大学计算机科学与技术学院	2	3	1.0	1.0