一句话：Grafu 通过电梯执行序、条件屏障与贪心着色重排，在外存同步图处理中充分释放未来值计算的 IO 优化潜力。
随着图规模指数级增长，外存图系统把海量数据存放在存储中并逐迭代处理，以同步语义强制顶点值在迭代间的计算依赖，从而便于编程。未来值计算可提前算出后续迭代的顶点值，是有效的 IO 优化手段，但要在保证迭代依赖的同时充分发挥其潜力十分困难：已有最优工作仍与理想 IO 缩减相去甚远，并带来可观的计算开销与额外内存占用。本文提出 Grafu，从三个角度优化未来值计算：新的电梯执行序显著增加可提前计算的顶点数量以大幅减少 IO；条件屏障在保证依赖的前提下自适应地移除屏障，缓解计算开销；贪心着色图重排减少未来值计算所需的额外内存。在多个十亿级图上的评测表明，Grafu 显著优于其他最先进系统。
As graphs exponentially grow recently, out-of-core graph systems have been invented to process large-scale graphs by keeping massive data in storage. Among them, many systems process the graphs iteration-by-iteration and provide synchronous semantics that allows easy programmability by forcing the computation dependency of vertex values between iterations. On the other hand, although future value computation is an effective IO optimization for out-of-core graph systems by computing vertex values of future iterations in advance, it is challenging to take full advantage of future value computation while guaranteeing iteration-based dependency. In fact, based on our investigation, even state-of-the-art work along this direction has a wide gap from optimality in IO reduction and further requires substantial overhead in computation as well as extra memory consumption. This paper presents Grafu, an out-of-core graph system unleashing the full potential of future value computation while providing synchronous semantics. For this goal, three main designs are proposed to optimize future value computation from different perspectives. First, we propose a new elevator execution order to significantly increase the number of future-computed vertices for considerable IO reduction. Second, unlike existing work that uses high-cost barriers to ensure dependency under future value computation, we present conditional barrier to alleviate this computational overhead by adaptively removing the barriers while guaranteeing dependency. Third, we introduce a new graph reordering technique, greedy coloring, to reduce the extra memory consumption required for future value computation. Our evaluation of various billion-scale graphs reveals that Grafu significantly outperforms other state-of-the-art systems.
@inproceedings{YangELLY24,
title = {Grafu: Unleashing the Full Potential of Future Value Computation for Out-of-core Synchronous Graph Processing},
author = {Tsun-Yu Yang and Cale England and Yi Li and Bingzhe Li and Ming-Chang Yang},
booktitle = {ASPLOS},
year = {2024},
doi = {10.1145/3620665.3640409}
}