IEEE TKDE'22：基于GPU的动态图处理系统

现实世界中的图通常会随着时间不断变化，这种类型的图被称为动态图。为了能够获得动态图变化过程中不同时间点的计算结果，往往需要对不同图快照进行并发处理。然而，现有基于GPU的图计算系统在支持多快照并发处理时，面领着高昂的数据访问开销等问题，最终导致GPU利用率低。针对这些问题，本文提出了一种基于GPU的动态图处理系统，它通过高效挖掘不同图快照任务之间的数据访问相似性，充分利用GPU资源和降低CPU-GPU之间的数据传输开销，从而有效支持对动态图不同图快照的并发处理。

该成果“EGraph: Efficient Concurrent GPU-based Dynamic Graph Processing”发表在IEEE Transactions on Knowledge and Data Engineering (TKDE)上，TKDE主要关注知识发现和数据挖掘等领域的前沿研究，是计算机领域数据挖掘方向的顶级期刊，2021年影响因子是6.977，属于中国计算机学会CCF A类期刊。

• 原文链接：https://doi.ieeecomputersociety.org/10.1109/TKDE.2022.3171588

为获得动态图变化过程中不同时间点的计算结果，动态图分析应用通常需要生成大量时序迭代图计算(Timing iterative Graph Processing, TGP）任务来处理动态图的不同快照。为了保证此类应用的高吞吐率，在GPU上同时运行TGP任务是一个有效途径。尽管最近已经开发了许多基于GPU的图处理系统，但是对于GPU核外动态图处理，由于CPU和GPU之间的大量数据传输以及并发运行任务之间的干扰，现有并发执行方式面临着高昂的数据访问开销，最终导致GPU利用率低。由于不同快照之间的大部分图数据是相同的，只有少量图数据随时间变化，论文观察到TGP任务在访问不同快照的图数据时具有极强的时间和空间相似性。基于以上观察，论文设计了基于GPU的动态图处理系统EGraph，它能够集成到现有的 GPU 核外静态图处理系统中，使其能够高效利用GPU资源来有效地支持TGP任务对动态图不同快照的并发处理。与现有方法不同， EGraph 提出了一种有效的加载-处理-切换执行模型。其通过充分利用TGP任务之间的数据访问相似性来有效降低CPU-GPU之间的数据传输开销，并保证更高的GPU利用率，从而实现TGP任务的高效执行。实验结果表明，在支持TGP任务时，现有的 GPU图处理系统在与EGraph 集成后能够获得2.3-3.5倍的性能提升。

在实际应用场景中，多个TGP任务通常需要在短时间内处理动态图的不同图快照（如图1(a)所示）。然而，现有解决方案在支持TGP任务的执行时，无论TGP任务是串行执行还是并发执行，它们的性能都较差。为了研究现有方案效率低下的原因，我们对现有最好的GPU动态图处理系统进行了分析，实验结果如图2所示。

从图2的实验结果中我们得出两个结论。首先，从图2（a）可以看出，数据访问成本（例如，在CPU和GPU之间传输图数据的成本）通常占总执行时间的大部分。这是因为TGP任务需要在每轮迭代中访问整个图数据，并且需要频繁地将图数据从CPU传输到GPU进行处理。其次，从图2(b)可以看出，当TGP任务的数量为1时（即，顺序地处理最新的图快照），数据访问开销最小。然而，由于单个任务的工作负载较低，导致GPU利用率也较低。当任务数增加到2、4和8时，数据访问开销会显著增加。这是因为多个任务在其相应的图快照上并发运行，不同图快照分别根据每个任务的遍历路径进行处理。随着TGP任务数量的不断增加，它们会在不同的时间重复将相同图数据的多个副本从主机内存加载到GPU内存。这会导致昂贵的数据访问开销。以上问题会导致现有方案系统吞吐量较低，无法有效支持对动态图不同快照的并发处理。

我们也通过分析发现，如图1(b)所示，图快照之间存在大量重叠部分，并且这些重叠部分的数据访存开销能够在每轮迭代中由多个TGP任务共享，这称为空间相似性。这种相似性为多个TGP任务共享这些图数据的访问提供了很大的可能性。具体而言，应允许TGP任务一起访问相同的共享图分区，以分摊数据访问成本，并且还应仅为多个任务提供相同图数据的单个副本即可，从而极大地节省GPU全局内存的消耗。如图2(c)所示，一些活跃图分区的访问频率高于其他分区（这称为时间相似性），因为在执行期间部分图顶点可能会变得不活跃（如图2(d)所示）。其中，R_a和A_ave分别是任意图分区的最大访问次数和任意图分区的平均访问次数。因此，图分区的加载顺序应该根据不同图分区的这种倾斜特性来进行安排。根据上述发现，我们提出了一种基于GPU的动态图处理系统来有效支持对动态图不同快照的并发处理。

本文提出了一种基于GPU的动态图处理系统，它能够集成到现有的GPU图处理系统中，使其有效地支持动态图中多个图快照上TGP任务的并发执行。如图3所示，EGraph的核心思想是一个加载-处理-切换（LPS）执行模型，以此来充分利用TGP任务之间的相似性。该执行模型通过动态地分析在下一轮迭代中任务需要处理图分区的访问相似度，然后使这些任务能够在下一次迭代中基于分析的相似度来更加规则地处理这些图分区。具体而言，共享图分区将根据图拓扑以共同的顺序从主机内存传输到GPU内存中。然后，对于每个加载的图分区，触发相应的TGP任务来并发处理，直到所有任务都完成了对这个图分区的处理。随后，再加载下一个分区。通过这样的方式，相关任务能够以协同执行的方式同时处理相同图分区，从而有效减少图分区从CPU到GPU的数据传输开销，并提高GPU利用率。

为了高效支持上述动态图处理过程，EGraph主要包含以下五个组件：图数据预处理器、负载调度器、图更新管理器、执行管理器和任务切换管理器。

图数据预处理器：它用于以一种细粒度方式将原始图数据的静态图分区划分为较小的图划分块。具体来说，它首先根据GPU内存中设置的图数据缓存区大小以及SM数量等信息来决定图划分块的合适大小，随后将静态图分区顺序地划分为图划分块，这为减少CPU到GPU的冗余数据传输成本提供了机会。

负载调度器：在执行阶段，EGraph收集相关TGP任务的活跃图划分块，随后根据收集的信息来构建逻辑图分区（由活跃图划分块构成）。然后，负载调度器将按照统一加载顺序（步骤1）将逻辑图分区从主机内存加载到GPU全局内存中以供TGP任务处理。通过这种方式，多个TGP任务能够共享相同图分区的CPU-GPU数据传输开销。此外，EGraph还设计了一种高效的调度策略来最大限度地提高已加载逻辑图分区的利用率。具体来说，该调度策略首先根据逻辑图分区所对应的TGP任务数量以及活跃图顶点数量等信息来为每个逻辑图分区给定一个优先级，随后将根据优先级来调度各逻辑图分区进行处理。

图更新管理器：在主机端，对于每个图更新批次，图更新管理器将根据图更新信息来确定需要更新的图划分块，然后将其传输到GPU进行图更新（步骤2）。具体来说，EGraph只将受图更新影响的图划分块分配给GPU进行顶点/边的插入/删除。通过这种方式，EGraph能够有效减少图更新过程中的CPU-GPU冗余数据传输成本。

执行管理器：处理模块能够在SMs上有效支持TGP任务的并发处理（步骤3）。当TGP任务需要发送消息以同步图顶点状态时，通信模块能够用于合并小通信消息来减少CPU和GPU之间的通信开销。此外，管理模块通过使用高效的内存管理策略来最大化GPU内存的利用率，并且避免图更新/处理过程中的GPU内存抖动。

任务切换管理器：对于正在处理的逻辑图分区，任务切换管理器将动态地确保相关任务之间的负载均衡（步骤4）。当发生负载不均衡的情况时，任务切换管理器的切换操作将会被触发来保证相关任务的负载均衡。

通过将EGraph集成到最先进的out-of-GPU-memory图处理系统（即，Subway）中进行测试。实验结果如图4所示，在支持TGP任务时，EGraph能够获得2.3-3.5倍的性能提升。

详细内容请参见：

Yu Zhang, Yuxuan Liang, Jin Zhao, Fubing Mao, Lin Gu, Xiaofei Liao, Hai Jin, Haikun Liu, Song Guo, Yangqing Zeng, Hang Hu, Chen Li, Ji Zhang, Biao Wang. 2022. EGraph: Efficient Concurrent GPU-based Dynamic Graph Processing. IEEE Transactions on Knowledge and Data Engineering. https://doi.ieeecomputersociety.org/10.1109/TKDE.2022.3171588