TianheGraph：一种具有拓扑感知能力的图处理框架

《ACM Transactions on Architecture and Code Optimization》：TianheGraph: Topology-aware Graph Processing

大规模图数据处理需求激增，现有方法在存储效率与通信优化方面存在瓶颈。本文提出TianheGraph框架，通过TianheWare存储格式整合低度顶点压缩，将内存占用降低超90%；并设计拓扑感知分区策略，基于多级互连网络动态调整路由表，使通信开销平衡度提升近3倍。实验表明，在Tianhe-Exa超算（79,024节点）上，TianheGraph的BFS吞吐量达164,949 GTEPS，较Fugaku系统提升6%，内存占用减少25%，且通信负载均衡因子趋近1。研究为超大规模图计算提供了新的优化范式。

　　在当今数据处理领域，随着图数据规模的不断扩大，对大规模图的高效处理成为一项关键挑战。图数据可以达到数十亿甚至数万亿条边，这种规模的数据对计算资源提出了极高的要求。传统的图处理引擎和方法在扩展性方面存在局限，通常无法有效支持超过几十个计算节点的并行处理，这主要归因于两方面的问题：一方面，它们在处理大规模图时需要大量的内存，导致存储和计算成本高；另一方面，它们未能充分考虑不同层级网络连接结构所带来的通信成本差异。为了克服这些挑战，本文提出了TianheGraph，一种专门设计用于提升大规模并行系统中图处理效率的软件方法。

TianheGraph的核心在于其独特的空间-时间高效图压缩技术，以及其创新的图划分方法。通过将图的顶点按度数进行分类，并采用一种基于图结构的划分策略，TianheGraph显著降低了内存占用，同时优化了通信效率。这种划分策略不仅考虑了图中顶点的连接度，还结合了HPC系统的网络拓扑结构，确保计算任务在不同的网络层级上实现均衡分布。在实验评估中，TianheGraph被应用于合成数据和真实世界图数据，其性能在多个方面都优于现有的图处理引擎，尤其是在处理大规模并行计算任务时，其表现尤为突出。

HPC系统通常采用分层结构，如“胖树”拓扑，以连接多个计算组件。这种结构内部由多个层级的通信域组成，包括机架、刀片、插槽和主板。Tianhe-Exa作为评估平台，展现了不同通信层级之间的显著延迟差异。这种差异对于图处理任务而言至关重要，因为通信延迟会影响整体性能。在TianheGraph中，通过动态调整路由表，可以平衡不同方向上的通信流量，从而减少跨域通信的开销。

在图处理过程中，存储和划分是两个关键环节。传统的图存储格式，如压缩稀疏行（CSR），虽然在存储稀疏图时表现出一定的优势，但在大规模图处理中却存在明显的瓶颈。这是因为CSR格式未能区分低度数顶点与高度数顶点，导致内存使用效率低下。TianheGraph通过引入一种更高级的存储格式，即TianheWare，有效解决了这一问题。TianheWare将相同度数的顶点进行分组，使得内存访问更加集中，减少了不必要的内存开销。

在图划分方面，TianheGraph采用了基于拓扑结构的划分策略，使得高连接度顶点及其邻居被分配到同一计算节点上，从而增强了数据本地性。这一策略不仅提高了计算效率，还显著降低了通信开销。通过这种方式，TianheGraph能够在不同的通信层级上实现负载均衡，从而优化整体性能。此外，TianheGraph还结合了通信延迟模型，确保在划分过程中能够预测并最小化通信开销。

为了验证TianheGraph的性能，本文进行了广泛的实验评估，涵盖了多种图处理算法，包括广度优先搜索（BFS）、最短路径（SSSP）、连通分量（CC）、页面排名（PR）以及基于标签传播的社区检测（CDLP）。这些实验不仅在合成数据上进行，还在真实世界数据集上进行，如欧罗巴2015、clueweb12和twitter-2010等。实验结果显示，TianheGraph在多个方面都优于现有的图处理方法，尤其是在高计算节点数量下，其吞吐量和内存效率得到了显著提升。

此外，TianheGraph在Graph500基准测试中表现出色，成功在使用多达77,200个计算节点的情况下取得了最佳成绩。这一结果不仅证明了TianheGraph在大规模并行计算中的优越性，也展示了其在不同硬件配置下的广泛适用性。通过与多个图处理引擎和划分方法的对比实验，TianheGraph在多个维度上展现了其性能优势，包括吞吐量、内存使用效率和计算时间等。

本文的贡献在于，不仅提出了TianheGraph这一新的图处理框架，还对其核心组件TianheWare进行了深入探讨。TianheWare的引入，使得图的存储和划分更加高效，为大规模图处理提供了坚实的基础。同时，TianheGraph的划分策略通过优化图的分布，有效减少了跨域通信，提高了整体计算效率。这些改进使得TianheGraph能够在实际应用中展现出良好的扩展性和性能表现。

在实验设置中，TianheGraph被部署在三个不同的HPC平台上，包括Tianhe-Exa、Wuzhen Light和Intel Cluster。这些平台的硬件配置各不相同，但TianheGraph的优化策略能够适应各种环境，从而确保其性能的稳定性。实验还对比了TianheGraph与多种图处理方法，包括Gemini和GraphScope，结果表明TianheGraph在多个方面都优于这些系统。

总体而言，TianheGraph通过其创新的图存储和划分方法，显著提升了大规模图处理的效率和性能。它不仅解决了传统图处理方法在内存使用和通信开销方面的不足，还通过优化通信延迟模型，实现了计算资源的高效利用。实验结果表明，TianheGraph在处理大规模图时，能够实现更高的吞吐量，更低的内存占用，以及更优的计算效率。这些优势使其在当前的图处理领域中具有重要的应用前景。