| 分布式多维大图迭代计算性能优化方法 |
| |
| 作者姓名： | 杜玉洁 王志刚 王宁 刘芯亦 衣军成 聂婕 魏志强 谷峪 于戈 |
| |
| 作者单位： | 1. 中国海洋大学计算机科学与技术学院;2. 密码技术与信息安全教育部重点实验室(山东大学);4. 东北大学计算机科学与工程学院 |
| |
| 基金项目： | 国家自然科学基金项目（61902366,61902365,62072083）;;中央高校基本科研业务费专项资金（202042008）;;中国博士后科学基金项目（2020T130623）; |
| |
| 摘 要： | 大规模图的复杂挖掘算法通常需要高频迭代分析,而在计算与存储方面扩展性良好的分布式计算是提高处理效率的有效方案.然而,图顶点之间存在自由分布的边关系,会在分布式计算任务之间产生大量消息,由此在迭代过程中产生的巨大通信开销严重制约性能收益.已有工作在传统消息推送框架下采用合并和备份等技术降低通信代价,但主要面向结构简单、易优化的单维消息类算法,并不适用于结构复杂的多维消息类算法,也难以与当前最先进的消息按需拉取框架兼容.因此提出一种新型轻量级顶点备份机制,通过备份顶点的按需同步以及本地消息的按需生成,可完美继承拉取框架在容错和内存管控等方面的系统优势,同时显著降低通信代价.此外,通过考虑通信收益与负载偏斜代价,可计算最优阈值以提高整体性能.最后在大量真实数据集上验证了相关技术的有效性.
|
| 关 键 词： | 分布式图迭代计算 多维消息图算法 通信优化 顶点备份 负载不均衡 |
|
|
