基于块坐标下降法的外存异步图计算系统

作者：赵程; 张志斌; 郭嘉丰; 刘丁玮

来源：高技术通讯, 2022, 32(08): 825-835.

DOI：10.3772/j.issn.1002-0470.2022.08.005

• 图计算系统
• 外存
• 异步并行计算
• 块坐标下降(BCD)
• 图划分

现有外存图计算系统中,外存I/O带宽不足成为性能瓶颈。使用整体并行模型将导致冗余计算,使用异步并行模型则将引入额外的优先级计算开销和负载不均衡。本文提出了基于块坐标下降法(BCD)的外存异步图计算系统(BCDG),设计了一次选择多轮优先的调度策略,降低了优先级计算的平均开销;设计了基于优先级的块预取策略,解决了优先选择会破坏顺序执行流水线的问题;设计了计算调度分离的划分策略,实现了均衡地按边计算和按点调度。实验结果表明,相较于目前最先进的外存图计算系统GridGraph和Lumos,所提系统平均性能分别提升10.30倍与8.72倍。整体计算过程中,中央处理器(CPU)等待外存I/O的时间仅占10%～30%。

• 单位
  中国科学院大学; 中国科学院计算技术研究所