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

摘要：

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

关键词：图计算系统、外存、异步并行计算、块坐标下降(BCD)、图划分

所属期刊栏目：32

分类号：TP391;TN911;TN47

资助基金：中国科学院战略性先导科技专项;中国科学院青年创新促进会项目;联想-中科院联合实验室青年科学家项目;重庆市基础科学与前沿技术研究专项资助项目

在线出版日期：2022-11-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：825-835