Abstract: GPU is not fully utilized when processing large-scale dynamic graph and the limitations of GPU-oriented graph partitioning methods lead to performance bottlenecks. To improve the performance of graph computing, a CPU/GPU heterogeneous graph computing engine is proposed to improve the performance of heterogeneous processors. Firstly, a new heterogeneous graph partitioning algorithm is proposed. It uses streaming algorithm for graph partitioning as the core to achieve dynamic load balancing between computing nodes and between CPU and GPU. The greedy strategy assigns vertices based on the maximum neighboring vertices during initial graph partitioning and dynamically adjusts vertex position based on the minimum connected edges during iteration. Secondly, the system introduces a GPU heterogeneous computing model to improve graph computing efficiency by functional parallelism. The experiment takes PageRank, Connected Component, SSSP, and K-core as examples to conduct comparative experiments with other graph computing systems. Compared to other graph engines, heterogeneous graph engine can better balance the computing load of each node and the load between heterogeneous processors to shorten delay and accelerate the overall computing speed. The results show that the CPU/GPU synergy of this system tends to 1 and the graph computing speedup ratio reaches 5 times compared with others. The Distributed Heterogeneous Engine (DH-Engine) can provide better graph heterogeneous scheme.

摘要： 在GPU异构集群中处理大规模动态图时GPU计算资源未被充分利用,并且面向GPU的图划分方法存在局限性导致出现性能瓶颈。为提高图计算系统性能提出一种CPU/GPU异构图计算引擎，用于提升异构处理器的计算性能。首先提出新的异构图分割算法，该分割算法以流式图划分为核心，通过贪心策略调整顶点位置，进而实现计算节点之间、CPU/GPU之间的动态负载均衡。在初始图划分时该方法基于最多邻居顶点来分配图顶点，在迭代时基于最少连接边动态调整顶点位置。其次，设计面向的GPU异构计算模型，通过CPU/GPU功能并行的方式实现协同计算。CPU与GPU并行执行图算法，提高CPU核心的利用率，进而提升图计算效率。实验以图算法PageRank、Connected Component、SSSP与K-core为例，与其他图计算系统展开对比。与未考虑异构计算的图引擎相比，异构图引擎DH-Engine（Distributed Heterogeneous Engine）能更好地平衡各节点计算负载以及计算节点内部的异构处理器之间的负载，通过缩短局部时延来提高整体的计算速度。实验结果表明DH-Engine的CPU/GPU协同度趋于1。相较于其他图系统，DH-Engine异构计算的加速比达5倍。分布式异构引擎可以提供更好的图异构计算方案。