CGCGraph：高效的CPU-GPU协同执行技术，用于并发动态图处理

《ACM Transactions on Architecture and Code Optimization》：CGCGraph: Efficient CPU-GPU Co-execution for Concurrent Dynamic Graph Processing

动态图快照的CPU-GPU协同处理系统优化

　　在当前大数据和高性能计算需求不断增长的背景下，动态图处理成为一项重要任务。随着用户规模和应用数据量的增加，对大规模并发图处理的需求也日益提高。在实际应用中，动态图数据会随时间发生变化，因此，为了获取不同时间点的信息，通常需要处理对应的图快照。现有的GPU图处理系统，如Gunrock、SEP-Graph、LargeGraph和Subway，虽然在单个图处理任务中表现良好，但在处理快速变化的图数据时，往往需要将多个快照传输到GPU进行并发处理，这会导致CPU与GPU之间的数据传输开销显著增加。此外，这些系统在处理并发任务时，GPU计算资源的利用率往往不高，特别是在处理大量快照时，这种资源利用率下降的问题更加突出。

为了解决上述问题，我们提出了CGCGraph，这是一种可以集成到现有GPU图处理系统中的软件运行时系统，旨在实现高效并发图快照处理，并提升整体系统资源的利用率。CGCGraph的核心思想是将多个并发快照中未共享的图数据留在CPU上，从而减少CPU与GPU之间的数据传输开销。同时，通过CPU与GPU的协同执行，可以提升GPU计算资源的利用率。具体来说，CGCGraph利用内核融合技术，将多个快照的共享图数据在GPU上并发处理，而将所有快照在CPU上并行执行，每个快照分配一个独立线程。这种新型的CPU-GPU协同执行模型结合了三种优化策略，分别针对存储、计算和同步，以提高并发图处理的效率。

为了更深入地理解CGCGraph的设计原理，我们可以从其背景和动机开始。动态图的处理通常涉及对图结构的持续更新，这包括边的插入和删除，以及顶点状态的变化。为了提高并发图处理的效率，需要对这些变化进行有效管理。在传统的图处理系统中，每个并发任务都需要独立加载图数据到GPU，这不仅增加了数据传输的负担，还降低了GPU资源的利用率。因此，为了优化存储和计算，CGCGraph提出了将共享图数据和未共享图数据分别处理的策略，从而减少不必要的数据传输和计算资源浪费。

在CGCGraph的架构设计中，系统被划分为多个主要组件，包括预处理器、调度器、同步管理器和自适应执行管理器。预处理器负责将图快照数据划分为共享图和未共享图，并将共享图数据传输到GPU。调度器则负责在每一轮图处理中将数据分配到CPU或GPU上。同步管理器用于协调CPU和GPU之间的数据同步，确保数据的一致性。自适应执行管理器则负责在运行时根据负载情况调整执行模式，以提高资源利用率。

在并发图处理中，CGCGraph引入了三个优化技术。首先是存储优化，通过将多个任务的活跃顶点位图合并，提高数据的局部性，减少数据访问冲突。其次是计算优化，通过动态负载平衡技术，确保在GPU上并行处理多个快照时，各线程之间的负载尽可能均衡。最后是同步优化，通过自适应切换策略，根据任务的负载情况决定是否切换到GPU专用模式，从而减少CPU与GPU之间的同步开销。

CGCGraph的设计目标是提高大规模并发图快照处理的效率，减少CPU与GPU之间的数据传输开销，并充分利用计算资源。在实际应用中，CGCGraph通过将共享图数据加载到GPU，并在CPU上处理未共享图数据，实现了高效的资源利用。此外，CGCGraph通过内核融合技术，将多个任务的图数据在GPU上并发处理，从而减少重复的数据加载和计算。

CGCGraph的实验结果显示，其在执行动态图快照处理任务时，性能提升幅度显著。具体来说，CGCGraph在执行BFS、SSSP等算法时，性能提升范围从1.7倍到4.5倍不等。这表明CGCGraph在处理动态图快照时，能够有效提升并发处理的效率，并减少数据传输开销。

此外，CGCGraph的优化技术还包括对存储、计算和同步的优化。在存储方面，通过合并多个任务的活跃顶点位图，可以提高数据的局部性，减少数据访问冲突。在计算方面，通过动态负载平衡技术，可以确保在GPU上并行处理多个快照时，各线程之间的负载尽可能均衡。在同步方面，通过自适应切换策略，可以减少CPU与GPU之间的同步开销。

CGCGraph的设计不仅提高了图处理的效率，还优化了系统的资源利用率。通过将共享图数据加载到GPU，并在CPU上处理未共享图数据，CGCGraph实现了高效的资源利用。此外，CGCGraph还引入了自适应切换策略，根据任务的负载情况决定是否切换到GPU专用模式，从而减少同步开销。

综上所述，CGCGraph是一种高效处理大规模并发图快照的软件运行时系统，能够有效提升系统资源的利用率，减少数据传输开销，并提高图处理的性能。其设计和实现为大规模动态图处理提供了一种新的解决方案，具有广泛的应用前景。