本文介绍研究组已被ICDE23录用的一个研究成果， HyTGraph：GPU-Accelerated Graph Processing with Hybrid Transfer Management。

论文链接如下：https://arxiv.org/abs/2208.14935

系统源码：https://github.com/iDC-NEU/HyTGraph

背景

基于 GPU 的图计算系统，因为其巨大的内存访问带宽和高并行处理能力吸引了广泛的关注。然而，与真实世界图数据规模不断上升相对的是，新一代 GPU 的容量在近些年并没有突破式的飞跃，当输入图的尺寸超过 GPU 内存容量时 (memory oversubscription)，现有的基于单 GPU 的系统（例如 Medusa，CuSha，Gunrock，Frog，Tigr，SepGraph等等）则无法进行处理。这限制了 GPU 在大规模图处理中的应用。 

 

近年来，研究人员们开始关注构建支持GPU 加速的图处理系统，即将大规模图数据存储在主存中，通过不断将数据上传到 GPU 中计算以加速超大规模图。这种方法可以同时利用GPU 的高性能图处理引擎和主机端较大的存储空间，因而被认为具有较高的应用价值。

 

 

与基于外存的图处理系统类似，GPU加速图处理系统的主要挑战是GPU和主机端之间较高的数据传输开销导致的较低GPU计算资源利用率。上表展示了一个配备一个 GPU 的异构平台示例。与 GPU 中高达数百 GB/s 的全局内存访问带宽相比，主机内存和 GPU 通过慢一个数量级的 PCI-e 接口连接。例如，在 PCI-e 3.0 配置下，主机与GPU之间的带宽的速度上限为 16GB/s, 而实际上往往只有12.3GB/s左右 , 这往往使得数据传输成为GPU 加速图计算的主要瓶颈。从上表也可观察到，即使PCI-e的带宽也在不断发展，但与GPU全局内存访问带宽相比，仍然是整个系统性能的瓶颈。

 

图计算任务具有特殊的数据访问模式，边数据是只读的，需要大量内存占用；顶点数据是读写的，需要少量内存占用。基于此，在GPU加速的图计算系统中，当图数据规模超过GPU内存容量，放置相对较小的顶点数据在GPU中，并按需从主机内存访问边数据，是一种值得尝试的方法。首先，边数据因为是只读的，易于管理同时也只需要单向通信；其次，在现实世界中，顶点的数据量通常比边数量要小数十倍。即使是常用的16GB内存GPU，依然可以处理一个数百亿边图数据的顶点数据。

在以顶点为中心的图处理框架中，图算法在一系列迭代中执行直到收敛。上图展示了一个SSSP算法的计算过程，SSSP需要找到从给定源顶点到其他所有顶点的最短路径，它从源顶点a开始，其中初始距离设置为0。在每一次迭代计算中，只有那些初始化的起点或者在上一轮迭代中被更新的顶点会参与到计算中，而这些顶点会尝试更新其邻居并将那些成功更新的顶点标记为下一次迭代中要处理的顶点，这些顶点即活跃顶点。它们在大多数轮次的迭代中只占据整个顶点集的一部分，因此仅传输这些活跃顶点所需的边（即活跃边）可以有效地减少数据传输量。

 

为此，一系列 GPU 加速框架提出跟踪图算法中的变化的活跃顶点来减少 GPU 和主机内存之间的数据移动开销。根据处理活跃边的方式，现有框架可分为两类。显式传输管理（ExpTM）方法和隐式传输管理（ImpTM）方法。

每一类传输管理方法又可以进一步划分为两种，每种方法均以最小化冗余传输为目的，即尽量减少非活跃边的传输。经过深入的分析和实验后，本文发现现有的方法在使用单一方法时有着诸多不足，要么仍然具有冗余数据传输，要么有着高昂的过滤开销，要么带来低效的带宽利用率。在基于单一方法的 GPU 加速图处理框架中，其执行性能往往是次优的。 

 

 

混合传输管理方法（HyTM）

上图展示了Subway（一个基于ExpTM-压缩的框架）和EMOGI（基于ImpTM-零拷贝的框架）的性能比较。在Frienditer-snap graph上，EMOGI 在SSSP上的性能优于 Subway，但在 PageRank 上Subway要优于EMOGI。 相比之下，对于SSSP，Subway在SK数据集上击败了 EMOGI，但在UK数据集上输于EMOGI。

总而言之，尽管现有方法显著减少了数据传输，但性能仍然不理想，而且这四种引擎都不能在不同的工作负载上实现最佳性能。它们中的大多数都只能适应一种或几种情况。

因此本文提出混合传输管理（HyTM），在运行时自适应地利用这两种方法的优点。通过对图进行分区，并在每次迭代中动态地评估每个分片的开销，将它们提供给开销最小的处理引擎，以实现最优性能。经过对不同方法的深入分析，本文选择基于过滤的显式传输（ExpTM-C），基于压缩的显式传输（ExpTM-C）和基于零拷贝的隐式传输 ImpTM-ZC 作为备选方法。 

 

HyTGraph

基于此，我们提出了HyTGraph，一个基于GPU加速的大规模图计算系统，在运行时综合两种传输方法的多种实现引擎的优点，以在每次迭代中都能达到最短的执行时间。在混合传输管理方法之上，HyTGraph通过灵活的异步任务调度来进一步降低主机GPU的数据传输开销，提升计算效果。

 

 

实验评估

实验系统包括Galois，Grus，Subway，EMOGI，和基于HyTGraph代码库实现的基于过滤的ExpTM（ExpTM-F）和基于统一内存的ImpTM（ImpTM-UM）的GPU加速图计算系统。

 

上图显示了在sk-2005（SK）,twitter（TW）, Friendster-konect（FK）, uk-2007（UK）, Friendster-snap（FS）数据集上执行四个经典算法的性能。实验结果表明，与其他系统和策略相比HyTGraph展示出了非常优异的性能。具体地，是Galois的5.27到12.78倍，是ExpTM-F的2.01到28.52倍，是ImpTM-UM的1.08到6.69倍，是Grus的1.01到8.03倍，是Subway的2.36到10.27倍，是EMOGI的1.10到6.53倍。

 

总结

我们设计并实现了HyTGraph，一个同时支持显式传输/隐式传输的混合传输管理方法，灵活异步任务调度框架，丰富GPU-CPU异构优化的GPU加速的大规模图计算系统。与现有工作相比，HyTGraph具有较高的性能，较低的冗余传输和较高的带宽利用率。