计算机研究与发展

作者：杜玉洁,王志刚,王宁,刘芯亦,衣军成,聂婕,魏志强,谷峪,于戈,

关键词：分布式图迭代计算, 多维消息图算法, 通信优化, 顶点备份, 负载不均衡,

大规模图的复杂挖掘算法通常需要高频迭代分析，而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而，图顶点之间存在自由分布的边关系，会在分布式计算任务之间产生大量消息，由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价，但主要面向结构简单、易优化的单维消息类算法，并不适用于结构复杂的多维消息类算法，也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制，通过备份顶点的按需同步以及本地消息的按需生成，可完美继承拉取框架在容错和内存管控等方面的系统优势，同时显著降低通信代价.此外，通过考虑通信收益与负载偏斜代价，可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.

来源：2023年第3期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2023年第3期