有做外贸个人网站,南昌二手网站开发方案,苏州晶体公司网站建设,惠州seo顾问转载请注明出处#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 此内容为机器翻译的结果#xff0c;若有异议的地方#xff0c;建议查看原文。 机器翻译的一些注意点#xff0c;比如#xff1a; 纪元、时代 epoch工人 worker火车、培训、训练师 train Effic… 转载请注明出处小锋学长生活大爆炸[xfxuezhang.cn] 此内容为机器翻译的结果若有异议的地方建议查看原文。 机器翻译的一些注意点比如 纪元、时代 epoch工人 worker火车、培训、训练师 train Efficient Data Loader for Fast Sampling-Based GNN Training on Large Graphs | IEEE Journals Magazine | IEEE Xplore 目录
高效的数据加载器用于对大型图形进行基于采样的GNN快速训
Abstract 摘要
Introduction 介绍
Background and Motivation 背景和动机
2.1 Graph Neural Networks 图神经网络
2.2 Sampling-Based Training With GPU 使用 GPU 进行基于采样的训练
2.3 Problems and Opportunities 问题与机遇
PaGraph
3.1 GNN Computation-Aware Caching GNN 计算感知缓存
3.2 Data Parallel Training and Partition 数据并行训练与分区
3.3 Pipelining Data Loading and GNN Computation 流水线数据加载和GNN计算
Implementation 实现
Computation-Balanced and Cross-Partition Access Free Graph Partition 计算平衡和跨分区访问自由图形分区
Evaluation 评估
5.1 Experimental Setup 5.1 实验设置
5.2 Single GPU Performance 单显卡性能
5.3 Effectiveness of Caching Policy 缓存策略的有效性
5.4 Multi-GPU Performance 多显卡性能
5.5 Implications of Graph Partition 图分区的含义
5.6 Effects of Pipelining 流水线的影响
5.7 Impact of Data Loading Volumes 数据加载量的影响
5.8 Supporting Other Sampling Method 支持其他采样方法
5.9 Training Convergence 训练收敛
Related Work 相关工作
Discussion and Future Work 讨论和今后的工作
Conclusion 结论
ACKNOWLEDGMENTS 高效的数据加载器用于对大型图形进行基于采样的GNN快速训
Abstract 摘要
新兴的图神经网络GNN已经将深度学习技术针对图像和文本等数据集的成功扩展到更复杂的图形结构数据。通过利用 GPU 加速器现有框架将小批量和采样相结合在大型图形上进行有效和高效的模型训练。但是此设置面临可扩展性问题因为通过有限的带宽链接将丰富的顶点特征从 CPU 加载到 GPU 通常会主导训练周期。在本文中我们提出了PaGraph这是一种新颖高效的数据加载器支持在具有多GPU的单服务器上进行通用且高效的基于采样的GNN训练。PaGraph 通过利用可用的 GPU 资源将经常访问的图形数据保存在缓存中从而显著缩短了数据加载时间。它还体现了一个轻量级但有效的缓存策略该策略同时考虑了基于采样的GNN训练的图形结构信息和数据访问模式。此外为了在多个GPU上横向扩展PaGraph开发了一种快速GNN计算感知分区算法以避免数据并行训练期间的跨分区访问并实现更好的缓存效率。最后它重叠了数据加载和GNN计算以进一步隐藏加载成本。使用邻接和层分两种采样方法对两个具有代表性的GNN模型GCN和GraphSAGE的评估表明PaGraph可以消除GNN训练管道的数据加载时间并在最先进的基线上实现高达4.8×的性能加速。结合预处理优化PaGraph 进一步提供了高达 16.0× 的端到端加速。
Introduction 介绍 最近图神经网络GNN [1] [2] [3] [4] 被提出将深度神经网络从处理图像和文本等非结构化数据扩展到结构化图数据并已成功应用于各种重要任务包括顶点分类 [2] 、、、 [3] 链接预测 [5] 、 [4] 关系提取 [6] 和神经机器翻译 [7] .然而一方面像PowerGraph [8] 这样的传统图形处理引擎缺乏自动微分和基于张量的抽象。另一方面当前流行的深度学习框架如TensorFlow [9] 对顶点规划抽象和图运算原语的支持不足。为了弥合这两个领域之间的差距提出了新的系统如DGLPython [10] GeometricMindSpore [11] GraphEngine [12] 和NeuGraph [13] 以提供与GNN兼容的方便高效的图操作原语。 许多现实世界的图表都是巨大的。例如Facebook友谊图的最新快照由7亿个顶点和超过1000亿条边 [14] 组成。除了图形结构数据之外与顶点和边关联的高维特征通常范围为 300 到 600会导致更大的计算和存储复杂性。在时间和资源的限制下将一个完整的巨型图列车完全作为一个批次将不再有效甚至不可行。因此典型的做法是采样 [2] 它重复从原始图中采样子图作为小批量的输入 [15] 从而减少单个小批量计算 [16] 同时仍收敛到预期的准确性。 不幸的是基于采样的GNN训练面临着严重的数据加载性能问题。特别是在加载高维顶点特征例如用户描述、纸张语义嵌入时从主机内存到 GPU 内存的数据移动非常耗时 [17] 。例如我们观察到当使用单个GPU在LiveJournal [18] 数据集上训练GCN [3] 模型时74%的训练时间花在数据加载上。主要原因是与海量数据相比GNN模型通常使用计算复杂度相对较低的深度神经网络。因此在 GPU 中执行的 GNN 计算比数据加载花费的时间要短得多。更糟糕的是当一台机器中的多个GPU用于加速训练时对从CPU加载到GPU的数据样本的需求成比例增长。一些优化的策略如预处理 [19] 修剪了GNN模型以获得更好的训练性能。然而即使有了这些优化的策略数据移动仍然主导着训练过程。 本文重点介绍如何在多 GPU 机器上加速基于采样的大型图形 GNN 训练。我们的关键思想是减少 CPU 和 GPU 之间的数据移动开销。这项工作主要基于以下观察。首先由于在GNN计算中引用顶点和图结构不同的训练迭代可能会使用重叠的小批量数据并表现出冗余的顶点访问模式。如下面的案例研究 Section 2.3 所示与目标图的顶点种群相比它可以加载多达 4× 个纪元期间的顶点数。其次在每次迭代中训练计算只需要保留与当前小批量对应的采样子图这只消耗一小部分例如不超过 10%的 GPU 内存。因此GPU 内存的其余部分可用于免费缓存最常访问的顶点的特征避免从主机内存重复加载。但是当前的数据加载器尚未探索备用GPU内存的可用性来实现它。 引入缓存以加速基于采样的 GNN 训练面临以下系统挑战。首先由于采样性质的随机访问模式很难预测下一个小批量中将访问哪些图形数据。我们没有预测下一次访问的图形数据而是利用了具有较高出度的顶点具有更高的概率被采样到小批量中的事实。在此之后作为我们的第一个贡献我们采用静态缓存策略将经常访问的图形数据保存在 GPU 内存中并引入了一种新的支持缓存的数据加载机制。当采样的小批量到达 GPU 时将从本地 GPU 缓存和原始图形存储服务器管理的主机内存中获取所需的特征数据。 其次当前的系统设计平衡了多个GPU之间的训练工作负载同时在它们之间共享完整图形数据的单个副本。这种单图并行性使上述缓存解决方案效率低下。为了避免这种低效率作为我们的第二个贡献我们将“数据并行性”适应基于采样的GNN训练并在单个多GPU机器中进行缓存其中每个GPU都在其图形分区上工作。显然数据并行性的好处是可以提高数据局部性并且缓存顶点的总数将增加。为此我们设计了一种新颖的GNN感知图分区算法该算法与传统的通用图分区算法 [20] 在两个方面 [21] 有所不同。首先为了平衡 GPU 之间的训练工作负载我们必须确保每个分区包含与工作负载相关的相似数量的训练目标顶点而不是任意顶点。其次为了避免采样时的跨分区访问我们为其分区中的每个火车顶点复制其 L 所有 -hop 可到达的邻居。由于通常不大于 2 、 [2] 、 [3] 、 [4] 并且我们的分区算法经过高度优化因此 L 生成的冗余是可以接受的。 第三缓存带来的性能提升与高出度的缓存顶点数量成正比。鉴于 GPU 内存通常限制为 10–30 GB缓存机制可能不足以支持大型图形上的 GNN 计算其中大多数顶点无法缓存。例如为了在enwiki [22] 图上训练GCN [3] 使用单个GPU最多只能缓存其顶点的51.2%。这将数据加载时间从 38.9 毫秒减少到 9.7 毫秒但仍占单次迭代训练时间的 34.3%。为了补充缓存和分区我们进一步探索了将数据加载开销隐藏到计算时间中的机会。这要求我们设计一个新的管道来并行化当前的小批量计算和下一个小批量的预取图形数据。 我们将上述设计理念整合到PaGraph中PaGraph是一种新颖高效的数据加载器用于支持在单个多GPU机器上对大型图形进行基于采样的GNN训练。PaGraph进一步与Deep Graph LibraryDGL [10] 和PyTorch [23] 集成。我们使用两种重要的采样算法即邻居采样和逐层采样 [2] [15] 在七个大型真实世界图上训练两个著名且常用评估的 GNN GCN [3] 和 GraphSAGE [2] 。实验结果表明PaGraph 完全屏蔽了每个训练周期的数据加载开销在相同数量的 epoch 内收敛到大致相同的精度的同时与 DGL 相比实现了高达 4.8× 的加速其中缓存和流水线策略分别对整体加速贡献了大约 70-75% 和 25-34%。结合预处理优化PaGraph甚至实现了高达16.0×的加速比DGL。 总之我们做出了以下贡献 对具有多GPU的单服务器上基于采样的GNN训练的分析表明训练性能已成为数据加载的瓶颈。 一种新颖的数据加载器 PaGraph用于合并静态 GPU 缓存从而减少从主机内存运送到 GPU 的数据量。通过 1 分区图以利用更好的数据局部性进行多 GPU GNN 训练以及 2 流水线数据加载和 GNN 计算从而减轻 GPU 缓存和计算之间潜在的 GPU 内存争用进一步提高了其缓存效率。 与DGL最先进的GNN库相比对PaGraph进行了深入评估包括两个具有代表性的GNN模型和七个真实世界的图形。 对PaGraph的局限性、应用范围、泛化机遇和挑战以及未来方向进行了富有远见的讨论。
Background and Motivation 背景和动机
2.1 Graph Neural Networks 图神经网络
在这项工作中我们以属性图为目标除了图结构信息外顶点或边还与大量特征通常超过数百个相关联。GNN 模型通常由多个层组成。 Fig. 1 显示了两层 GNN 模型的体系结构其中蓝色和绿色分别表示第一层和第二层。 跨不同层的计算遵循传统的以顶点为中心的图迭代处理模型 [8] 。 [24] 在每一层每个顶点都遵循其传入的边来聚合来自邻居的特征细箭头然后使用神经网络将特征转换为输出特征粗箭头输出特征将作为输入特征 [2] 馈送到下一层。在同一层中所有顶点共享相同的聚合神经网络和转换神经网络。单个GNN层只能实现从直接1跳邻域顶点传递的信息。对于 2 个 GNN 层通过将前一层的输出作为输入摄取到下一层我们可以连接 2 跳邻居。同样在 L 层 GNN 中顶点可以从 L 跳中的邻居收集信息。最后一层的输出可用于增强顶点分类 [2] 等任务 [3] 或用作关系提取 [6] 的嵌入。
2.2 Sampling-Based Training With GPU 使用 GPU 进行基于采样的训练 训练GNN模型以达到理想的精度通常需要几十个epoch每个epoch都定义为对目标图的所有训练顶点进行完全扫描。纪元由一系列迭代组成在每次迭代期间将随机选择一小批训练顶点来评估和更新该模型。但是与每个数据样本都是独立的图像和句子等训练数据不同图形数据是高度结构化连接的。因此在顶点上进行训练不仅需要加载顶点相关数据还需要加载其链接边和连接顶点的数据这使得GNN中的数据加载与传统的机器学习训练有很大不同。 GNN 计算的独特数据访问模式使得很难有效地处理顶点数及其相关特征的指数增长以训练 GNN 层数。相反为了解决这个问题采样作为一种典型的优化解决方案被广泛采用 [2] [15] [16] . [19] 基于采样的训练选择有限数量的小批量的层跳可到达邻居并以更低的计算成本 [19] 实现几乎相同的训练精度。 此外图形处理单元GPU提供了前所未有的计算密度和编程灵活性几乎每个深度学习框架都支持包括PyTorchTensorFlow [23] [9] 和MXNet [25] 使其成为深度学习训练的事实标准加速器。GPU 由大量强大的处理器和高带宽专用 GPU 内存组成是执行张量相关计算的绝佳选择。因此现有的GNN库如DGL遵循相同的实践使用GPU进行训练加速。我们的实验表明当通过LiveJournal [18] 数据集训练GCN [3] 模型时单个1080Ti GPU提供的性能是仅CPU设置16核设置的3×。随着更多GPU的参与性能差距将逐渐扩大。 Fig. 2 绘制了基于 GPU 的基于采样的 GNN 训练的工作流程。有一个全局图形存储服务器它管理完整的图形结构以及CPU内存中的特征数据。每次训练迭代都涉及三个主要步骤即采样1、数据加载2-3和模型计算4。在每次迭代中数据采样器随机收集训练顶点的数量小批量大小然后遍历图形结构并对其 L-hop 邻居顶点进行采样以形成输入数据样本 1。作为采样方法中的代表性示例邻域采样 NS [2] 只是从当前访问的顶点中选取少量随机邻域。例如在 2 个相邻采样中如 所示 Fig. 3 对于训练顶点 v1 它 v2,v5 从其 1 跳入的相邻点中进行选择。然后它 v6,v2,v9,v8 从选定的 1 跳顶点 v2,v5 的直接邻居中采样 2 跳内邻居。数据加载步骤为 GPU 计算准备特征数据。在这里我们要强调的是数据加载不仅仅是通过 PCIe 将数据从 CPU 传输到 GPU。相反数据加载过程经历以下两个阶段。数据加载器选取一个小批量并查询图形存储以从该批次中收集所有顶点的特征 2并通过 PCIe 链接将这些样本加载到 GPU 内存中 3。最后CPU 上的训练器启动 GPU 内核在加载的数据样本上在 GPU 上执行 GNN 计算 4。该过程将迭代运行直到目标模型收敛。 2.3 Problems and Opportunities 问题与机遇 尽管利用了 GPU 提供的强大计算资源但使用 GPU 改进 GNN 训练的空间仍然很大。特别是基于 GPU 的基于采样的 GNN 训练存在需要解决的严重数据加载问题。为了理解这一点我们在 1 到 4 个 GPU 上训练一个 2 层 GCN [3] 作为我们的演练示例。我们使用广泛使用的邻居采样和逐层采样 LS [15] 为每个训练迭代创建小批量顶点。LS 与 NS 几乎相同只是它将一个层视为一个整体并限制每层而不是每个顶点的采样顶点总数从而避免采样顶点的数量随着层的加深呈指数增长。正如现有工作 [15] 所建议的那样 [19] 这里的邻域采样方法为每个顶点选择 2 个邻域而逐层采样方法将每层采样的顶点数限制为 2,400。如下我们报告了我们对性能效率低下的主要观察结果并揭示了它们的根本原因这些原因共同激励了我们的工作设计。我们从流行的 DGL 库 [26] 和 GTX-1080Ti GPU 的单 GPU 训练开始。 数据加载主导训练时间。在对 3 个大型真实世界图livejournal [18] 、lj-large [27] 和 enwiki 的实验中 [22] 我们发现从 CPU 到 GPU 的数据加载通常主导端到端 GNN 训练时间。在实验中我们采用了具有代表性的GNN模型即2层GCN [3] 并使用广泛使用的邻域采样和逐层采样 [2] [15] 来创建小批量的顶点用于训练性能理解。 Fig. 4 总结不同图形上的训练时期时间并显示时间细分为数据加载和计算。请注意我们省略了采样开销因为采样运行速度比数据加载快并且已经与数据加载重叠。显然在所有三个图形数据集中数据加载比计算花费的时间要长得多。例如当使用邻居和逐层采样时livejournal 上的 GCN 分别花费了 74% 和 56% 的端到端训练时间在数据加载上。当使用多个 GPU 共同训练共享模型时这种情况会变得更糟因为计算时间将减少数据加载开销将变得更加占主导地位。 通过对结果的深刻理解我们确定了以下严重减慢整个培训过程的因素。同时它们还为我们提供了进一步提高基于 GPU 采样的 GNN 训练性能的机会。 冗余顶点访问模式。我们继续了解从 CPU 发送到 GPU 以完成训练周期的数据总量。令人惊讶的是加载的数据量可以超过我们实验中目标图顶点总数的 4×。这表示某些顶点被多次加载。为了验证这一点我们收集不同训练作业的顶点访问跟踪并计算每个顶点的访问次数。 Fig. 5 是一个 CDF 图用于使用 NS 和 LS 采样方法时用于在 wiki-talk 图上训练 GCN 的加载顶点的访问频率。我们观察到超过 32.4% 的顶点被重复使用了多达 519 次。这种冗余的顶点访问模式加剧了数据加载负担并为每个纪元创建数十 GB 的数据加载。我们进一步发现这些顶点比其他不常访问或未访问的顶点具有更高的出度。这是因为图中具有高出度的顶点可能与多个火车顶点相连使其有机会被不同的小批量多次选择。 基于这一观察结果我们得出了一个启示即在GPU内存中缓存高出度顶点的特征信息将减少从CPU到GPU的数据加载量从而加速基于采样的GNN训练。但是这种优化会带来一些挑战例如将 GPU 内存与 GNN 计算竞争产生维护此类缓存的开销等。 GPU 资源未充分利用。由于数据加载阶段先于 GPU 训练阶段因此我们进一步探讨了数据加载瓶颈的负面影响。我们总结了两个GNN模型GCN和GraphSAGE正在训练的资源利用率 Table 1 。令人惊讶的是无论采用何种采样方法GPU上只有一小部分计算和内存资源被利用。例如使用邻居采样时只有大约 20% 的 GPU 计算资源在使用中内存消耗更少例如不到 10%。这是因为 CPU 发送到 GPU 的小批量数据不足以充分探索 GPU 中的硬件并行性。同时GPU 处于空闲状态等待训练数据样本在大多数时间到达。 这一观察结果促使我们考虑利用备用 GPU 资源来缓存经常访问的顶点的特征信息以便尽可能便宜地重复使用。从理论上讲这种缓存解决方案可以消除应该收集并从CPU发送到GPU的特征信息量从而消除基于采样的GNN训练中的CPU特征收集和PCIe数据传输瓶颈。 采样和特征收集之间的 CPU 争用很高。然后我们分解了在数据加载过程的不同阶段所花费的时间发现特征收集阶段是 CPU 密集型的并且比 CPU-GPU 数据移动花费的时间要长得多。例如对于三个使用的数据集它分别占总数据加载时间的 50.4%、55.1% 和 56.3%。这个令人惊讶的结果导致1使用单个GPU我们实现了最大约8 GB / s的PCIe带宽利用率容量为16 GB / s而平均利用率较低;2对于多个 GPU用于收集特征的并发工作线程将与采样器争用 CPU 资源例如采样和特征收集的时间分别比 1-GPU 情况增加了 88% 和 59%而 GPU 计算时间保持不变。在 4-GPU 情况下最大 PCIe 带宽利用率下降到一半平均值甚至更糟。这表明 CPU 容量无法应对 GPU 计算需求因为每次迭代都需要大量数据。因此为了降低特征收集成本我们必须考虑减少在此阶段应收集的数据量以及隔离采样和特征收集的资源分配。 数据加载和GNN计算的顺序执行。使用占主导地位的库 DGL尽管数据加载消耗 CPU 和 PCIe并且 GNN 计算被调度到 GPU但它们仍然以串行顺序执行。DGL不会利用训练管道中的两个阶段来重叠主要是因为数据加载主导了整个训练空间GNN计算运行得更快。然而在我们的工作中采用缓存会显著影响训练管道因为它降低了数据加载成本同时随着更多的数据样本被馈送而增加了计算密度。因此新情况为我们提供了管道数据加载和GNN计算的机会以将一个人的成本隐藏到另一个人的成本中反之亦然。这种管道设计还引入了积极的效果可以在面对大型图形时提高缓存效率因为它可以减少需要在 GPU 内存中缓存的数据量。
PaGraph 在实验 Section 2.3 结果的激励下我们提出了PaGraph一种新颖高效的数据加载器可以在大型图上进行基于快速采样的GNN数据并行训练。我们向PaGraph介绍了三种关键技术1GNN计算感知缓存机制用于减少从CPU加载到GPU的数据2缓存友好的数据并行训练方法用于在多个GPU上扩展GNN训练以及3两阶段训练管道重叠数据加载和GNN计算。 Fig. 6 显示了 PaGraph 的整体架构。对于具有 GPU 的 N 单台计算机整个图形被划分为 N 子图形。这些分区的图形结构信息以及顶点特征数据存储在 CPU 共享内存中的全局图形存储服务器中。有 N 独立的培训师。每个训练器负责在专用 GPU 上训练计算。它复制目标 GNN 模型并且仅使用自己的数据分区。每个 GPU 都包含一个缓存用于保存经常访问的顶点的要素。 在每次训练迭代期间每个训练器都会收到采样器生成的小批量的图形结构信息。如 所示 Fig. 7 它还通过直接从自己的 GPU 缓存中获取如果缓存的关联顶点要素标记为绿色或查询 Graph Store 服务器以查找缺失的要素标记为黄色来获取数据加载器收集的关联顶点要素。前一种情况节省了从 CPU 到 GPU 的数据复制开销而后一种情况则不能。之后该小批量的结构数据以及缓存和加载来自主机的顶点特征被馈送到GNN模型中以计算梯度。训练器之间除了在每次迭代结束时同步本地生成的梯度以更新模型参数外不会相互交互。 3.1 GNN Computation-Aware Caching GNN 计算感知缓存 缓存策略。为了生成更好的模型对于每个纪元大多数训练算法都需要随机洗牌的训练样本序列这使得无法在运行时预测每个小批量中的顶点。顶点的邻居也是随机选择的因此在训练期间也是不可预测的。因此很难预测哪个顶点最有可能在下一个小批量中被访问。但是由于邻域采样方法的独特访问模式顶点的出度表示在整个纪元中被选中的概率。这表示随着出度越高顶点更有可能是其他顶点的邻域因此更有可能以小批量进行采样。因此用高出度顶点填充缓存就足够了。 通常首选动态缓存策略。但是它不适合缓存位于 GPU 内的情况。这是因为 GPU 不能独立工作在 GPU 上执行的所有计算都必须组装到 GPU 内核中并由 CPU 启动。大多数当前的GNN都是轻量级 [1] 的因此CPU内存和GPU内存之间的图形数据交换在训练期间具有无法忍受的开销请参阅 Section 2.3 。因此我们不是即时决定要缓存的内容例如 LRU [28] 而是使用静态缓存来避免动态数据交换的开销。为此我们可以离线按出度对顶点进行预排序并在运行时选择最高出度顶点以填充 GPU 缓存。我们将探索高效的动态缓存策略留给未来的工作。尽管它很简单如 所示 Section 5 此静态缓存策略有效地实现了高缓存命中率。 缓存空间。为了避免高优先级训练计算的资源争用我们需要估计缓存分配的最大可用 GPU 内存量。为了实现这一目标我们利用了内存消耗在训练迭代中相似的事实。这是因为基于采样的小批量训练使用几乎相同数量的数据样本作为输入并执行几乎相同的计算量来训练每次迭代的共享GNN模型。因此通过对 GPU 内存使用情况进行一次性采样来确定正确的缓存大小就足够了。更详细地说在第一次小批量训练之后我们会在训练期间检查可用 GPU 内存的大小并相应地分配可用的 GPU 内存来缓存图形数据有关更多详细信息请参阅 Section 4 。 数据管理。在 GPU 缓存中我们通过维护两个单独的空间来管理缓存的顶点要素。首先我们为特征数据分配连续的内存块。顶点的缓存要素数据被组织为几个大 [N,Ki] 矩阵其中 N 表示缓存顶点的数量 Ki 是 i 第绪个要素名称字段下的要素维度。其次为了实现快速查找我们将顶点元数据组织到一个哈希表中以回答查询的顶点是否被缓存以及它的位置以供以后检索。元数据远小于缓存的特征数据例如对于具有 1000 万个顶点的分区不超过 50 MB。 讨论。较少的偏斜或大量的图形会限制缓存优化的效率。然而许多真实世界的图包括求值的图是幂律图 [8] [30] [29] 并且表现出高偏度。因此我们的解决方案可以使常见的GNN培训工作受益。对于那些具有较少偏斜或大图形的人来说一种可能的解决方案是将预取和动态缓存结合起来以实现良好的缓存效率。我们将在 中 Section 3.3 解决此问题。
3.2 Data Parallel Training and Partition 数据并行训练与分区 GNN系统如DGL的当前设计在多个GPU之间平衡计算但使它们共享图形数据的 [26] 单个副本。当将上述GNN感知缓存方法直接应用于此设置时我们观察到缓存效率低下的现象即缓存命中率随着GPU数量的增加而不断降低。这是因为单个图形为多个 GPU 上的并行训练器提供数据访问位置因此所有 GPU 缓存都将保持相似的顶点。 为了解决这种缓存效率低下的问题我们在PaGraph中引入了“数据并行性”它已被广泛用于利用多个GPU来有效地训练神经网络模型。在我们的系统中Trainer 不是访问共享图而是使用其数据分区子图执行训练计算以获取局部梯度然后在对等方之间交换梯度以同步更新其模型副本。显然数据并行性的好处是可以提高数据局部性并且将增加缓存顶点的总数。为了实现这一点尽管存在许多图分区算法 [8] [20] [21] 我们仍然需要设计一个新的算法来满足数据并行GNN训练特有的以下两个目标。首先它应该在不同的训练师之间保持计算平衡因为不平衡的计算可能会导致不同训练师每个时期的小批次数量不同。这将破坏梯度同步并使训练卡住。其次它需要尽可能避免来自不同训练器的跨分区访问。 计算平衡。若要在不同训练器之间实现计算平衡所有分区都应具有相似数量的训练顶点。假设我们需要 K 分区。我们扫描整个火车顶点集并迭代地将扫描的顶点分配给其中一个 K 分区。在每次迭代中一个训练顶点被分配一个维度分数向量 t 其中第个元素表示将顶点 vt 分配给 i i 第1个分区的可行性 i∈[1,K] 。 K 分数由方程计算。 (1) TVi 表示已分配给 i 第 th 个分区的训练顶点集。 IN(Vt) 表示火车顶点的 L -hop 邻域集 vt 。 PVi 控制工作负载平衡并表示 i 第 th 分区中的顶点总数包括复制的顶点。 vt 最有可能分配给具有最小 PV 的分区。 TVavg 是最后一个 i 分区中预期的火车顶点数。为了实现计算平衡我们设置为 TVavg |TV|K 这表示所有分区将获得几乎相同数量的训练顶点。 自力更生。对于包含跨不同分区的边缘的查询必须将它们转发到 Graph 存储服务器以获取完整的邻居集。受 的 [8] [31] 启发PaGraph 在每个分区中引入了最小的额外顶点和边来处理跨分区边。 Fig. 8 演示如何对单层 GNN 模型的自力更生图形进行分区。阴影顶点表示火车顶点白色顶点表示值/测试顶点虚线顶点表示引入的冗余顶点。 对于每个分区PaGraph 使用冗余顶点和边扩展子图以包括采样期间所需跃点的所有相邻顶点。对于具有GNN层的GNN模型我们将为每个火车顶点包含 L -hops相邻顶点例如单层GNN模型只需要包含每个火车顶点的 L 直接邻中。PaGraph 仅为扩展顶点引入必要的边以满足训练期间所需的消息流。请注意扩展顶点可能包括训练顶点。这些扩展的列车顶点被视为镜 [8] 子不会被训练。这样分区彼此独立。每个训练器都可以完全从自己的子图对小批量进行采样而无需访问全局图结构。
3.3 Pipelining Data Loading and GNN Computation 流水线数据加载和GNN计算 如前所述缓存的性能改进与具有高出度的缓存顶点的数量成正比。尽管大多数真实世界的图形都表现出高偏度但鉴于 GPU 内存大小通常限制为 10-30 GB独立缓存机制可能不足以支持大型图形上的 GNN 计算其中大多数顶点无法缓存。因此在这些情况下数据加载仍将是瓶颈。为了补充缓存和分区我们进一步探索了将数据加载开销隐藏到计算时间中的机会。这要求我们设计一个新的管道来并行化当前的小批量计算和下一个小批量的预取图形数据。 Fig. 9a 展示了我们的两阶段训练管道设计我们将原始的顺序执行分解为两个并行的流式执行即加载和计算。我们使用消息队列来协调两个流的执行。通过从 Sampler 获取输入加载流式执行器负责组织图形存储和 GPU 缓存中所选小批量顶点所需的特征信息请参阅 Fig. 9b 。加载完成后它会将一条就绪消息包括批处理数据在 GPU 内存中的位置发布到共享消息队列。另一方面计算执行器位于循环中并定期检查来自加载执行器的新消息的到达。它从共享队列的头部弹出一条消息并计划相应的GNN计算这将消耗已经预取的数据。 新的流水线设计使我们进一步将 GPU 内存分为三个部分分别用于 GNN 计算、图形数据缓存和缓冲预取数据请参阅 Fig. 9b 。但是由于以下原因我们声称预取缓冲区不会加剧 GPU 内存紧张。首先每个小批量数据占用的内存空间不到 900 MB在我们评估中使用的一台设备上仅占用 GPU 内存的 8%。其次我们限制了预取任务的最大数量以避免内存争用。我们还使用消息队列的长度作为反馈来指导加载执行器自适应减慢或加快预取速度。
Implementation 实现 我们在Deep Graph LibraryDGLv0.4 [10] 和PyTorchv1.3 [23] 的顶部构建了PaGraph。由于梯度同步不是GNN训练中的主要关注点我们只是采用现有的解决方案NCCL RingAllReduce来实现数据并行GNN训练 [32] 。我们使用 DGL 实现的图形存储服务器将图形结构数据和特征数据存储在 CPU 共享内存中。 1 我们将完整的图结构存储为 CSC 格式 [33] 的邻接矩阵。CSC 格式在连续内存空间内聚合每个顶点的邻域集从而允许快速访问以获取它们。整个实现由 Python 中的 1.47 K 行代码组成其中 293 行用于数据加载器436 行对应于分区算法737 行是对原始采样训练工作流所做的更改。我们正在重构代码库并计划使其在线提供以支持可重现性。 缓存初始化和维护。我们扩展了数据加载器以合并简单的 Python API用于从本地 GPU 内存或 CPU 内存获取所需的数据如 所示 Fig. 10 。首先我们通过将数据加载器连接到 Graph Store Server 并使其了解数据并行训练配置来初始化数据加载器例如使用了多少 GPU它为哪个 GPU 服务等。在第一次小批量训练期间数据加载器将检查总 GPU 内存表示为 total_mem 和 PyTorch 分配的峰值 GPU 内存表示为 used_mem 。我们还保留了一定大小的 GPU 内存未用于训练期间的内存波动表示为 preserved_mem 我们发现在实践中 1.0 GB 就足够了。之后我们调用 loader.auto_cache它计算可用内存的大小并通过减 used_mem 去和 preserved_mem from total_mem 来将此内存量分配给缓存。分配缓存后数据加载器将持续加载到具有最高出度的折点的缓存要素由 field_names 指定中直到缓存已满。为了减少此初始化过程的时间成本我们离线分析子图结构并根据顶点的出度对顶点进行排名。从第二次迭代开始数据加载器通过调用 loader.fetch_data 从 Graph Store Server 和本地 GPU 缓存获取数据mini_batch 对此进行参数化。此新加载流对训练作业是透明的。 Computation-Balanced and Cross-Partition Access Free Graph Partition 计算平衡和跨分区访问自由图形分区 脱机图形分区。Algorithm 1 提供了我们特定于GNN的分区方法用于拆分大型图形以适应支持缓存的数据并行训练。我们实现了基于线性确定性贪婪LDG [20] 的分区算法这是一种基于流的分区解决方案。我们只评估训练顶点第 3 行根据 scores 计算第 4-5 行将它们分配给具有索引 ind 的目标分区第 6 行并且还将它们的 L -hop 邻域第 7 行包含在分区中。为 GNN 模型训练准备分区是训练前的脱机作业。尽管此步骤引入了额外的时间成本并消耗了额外的资源但由于以下原因它是可以接受的。首先分区是一次性脱机作业因此不会阻塞训练过程。其次最近的研究发现 [34] [35] 许多机器学习作业是由参数调优实验生成的它们共享的大多数配置包括数据集和分区。因此此一次性作业在这些参数优化实验中可能非常有用。 为了减轻分区的存储负担我们删除了在训练期间没有贡献的冗余顶点和边。对于给定 L 的层图神经网络我们检查 val/test 顶点 L 是否远离所有训练顶点。如果是这样我们从子图中删除此顶点及其相关边。此外我们删除冗余边缘以避免低效的消息流。如果不需要其中一个消息流方向那么非有向边将转换为有向边。随着图结构的细化与冗余顶点和边相关的图数据也被移除。 流水线。由于 DGL 已经将小批量采样与数据加载路径上的其余步骤重叠因此我们只考虑将数据加载成本隐藏到计算中。最初我们引入了一个守护进程线程用于在当前小批处理正在计算时预取下一个小批处理。不幸的是这个版本效率低下因为python的传统GIL全局解释器锁功能序列化了多个线程。为了避免这种不必要的序列化我们启动一个守护进程来执行目标预取任务并通过 PyTorch 队列管理进程之间的通信。但是由于进程隔离这种多进程解决方案也带来了额外的成本用于将预取的小批量数据从共享队列复制到计算进程的内存空间。为了进一步隐藏这种不可忽略的成本我们另外从主进程生成一个守护进程线程以将数据从队列异步复制到后台的主进程。 资源隔离。GNN库通常在深度学习框架之上实现并为这些框架添加额外的图形存储和采样功能。在其实现中采样和数据加载都放在单个进程中并同时使用 OpenMP [36] 执行并发作业例如采样多个小批处理、收集小批处理数据并将其复制到受保护的固定内存空间等。我们观察到采样和数据加载之间的干扰与单个进程其中两者都竞争 CPU 资源。这种干扰还会降低内核从 CPU 主机启动到 GPU 设备的频率。为了消除这种资源争用在我们的实现中我们使采样和数据加载使用单独的进程并调整 OpenMP 配置以平衡它们之间的 CPU 资源。 局部洗牌。为了在数据并行训练中实现更好的经验性能 [37] 需要对数据样本进行洗牌。可以跨分区全局或在每个分区本地内进行随机排序其中前一种情况可能会导致更快的收敛但比后一种情况成本更高。然而局部洗牌在现实世界的实践中被广泛采用最近的研究表明在收 [38] 敛速度稍慢的情况下它仍然可以表现良好。因此PaGraph 会锁定每个训练器分配的分区并在每个纪元开始之前打乱该分区中数据样本的访问顺序。我们进一步表明 Section 5.9 局部洗牌不会影响模型精度和收敛速度。 讨论。目前PaGraph 在单个多 GPU 服务器上工作但缓存、图分区和流水线的核心思想可以直接应用于分布式 GNN 训练以利用更多的 GPU 来处理无法放入单个服务器内存的更大图。在该扩展中唯一需要仔细设计的是有效地同步服务器之间的梯度以避免同步瓶颈。
Evaluation 评估 我们使用具有代表性的GNN模型和真实世界数据集对PaGraph的性能进行了深入评估。特别是我们探索了单GPU性能和多GPU的扩展效率对分区算法在不同条件和质量下的缓存性能进行了细分分析并了解了缓存和流水线在面对大型图时的联合效应。
5.1 Experimental Setup 5.1 实验设置 环境。我们在多GPU服务器上部署实验该服务器由双Intel Xeon E5-2620v4 CPU512 GB DDR4主内存和4个NVIDIA GTX 1080Ti11 GB内存GPU组成没有NVLink连接。机器安装了 CentOS 7.6、CUDA 库 v10.1、DGL [10] v0.4、PyTorch [23] v1.3。 数据。我们使用中 Table 2 列出的七个真实世界图形数据集进行评估包括reddit [2] 社交网络wiki-talk [39] page版本历史网络livejournal的三种变体通信网络 [27] livejournallj-linklj-large [40] [18] 和enwiki维 [22] 基百科链接网络。“特征”列表示顶点特征的维度“标签”列显示顶点类的数量。按照 Reddit [2] 的设置我们将每个数据集中的顶点拆分为训练、价值和测试顶点类别比例为 651025。 抽样方法。我们采用邻域采样和逐层采样 [2] [15] 结合跳过连接 [16] 来评估PaGraph。最近的一项工作 [19] 已经表明基于邻域的采样训练可以实现与全图训练相当的模型性能其中每个邻域层仅采样两个邻域。因此在我们的评估中我们选择遵循他们的建议即对每层中的一个顶点对两个随机邻居进行采样以形成一个小批量。根据 DGL [26] 的建议我们将整个评估的训练批次大小设置为 6,000。我们将层大小设置为 2,400以便按照 FastGCN [15] 的建议进行逐层采样。由于空间限制我们大多数时间报告与邻居采样相对应的结果而只显示 和 5.9 中 Sections 5.7 逐层采样的结果。我们在两种采样方法中观察到类似的趋势证明我们的解决方案适用于各种采样方法。 模型。我们使用两个具有代表性的GNN模型Graph Convolutional Network GCN [3] 和GraphSAGE [2] 来评估PaGraph并在中 Table 3 进行了详细配置。GCN 对图的卷积操作进行推广如下。GCN 图层中的每个折点都使用 sum 操作聚合其相邻折点的要素。然后聚合要素通过全连接层和 ReLU 激活以生成输出表示。GCN在分类 [3] 和神经机器翻译 [7] 等任务中表现出色。GraphSAGE [2] 是一种归纳学习模型用于学习不同跳数上的不同聚合函数。GraphSAGE中有四种聚合类型GCNsumMeanLSTM和Pooling。我们选择展示 GraphSAGE-Mean 模型的实验结果因为所有四个聚合器都显示出相似的执行成本 [2] 。 基线。我们将原始 DGL 部署为第一个基线。此外我们运行一个高级 DGL其中预处理 [19] 优化作为另一个基线启用表示为“DGLPP”。预处理背后的想法是通过离线聚合相应的特征来删除GNN模型的第一层。尽管如此数据加载仍然主导着支持预处理的训练的性能并使其无法充分利用这种优化。除非另有说明否则所有性能数字都是 10 个时期的结果的平均值。
5.2 Single GPU Performance 单显卡性能 我们首先评估PaGraph在单个GPU上的训练性能。 Fig. 11 显示了GCN和GraphSAGE在不同数据集上的训练性能。总体而言与DGL相比PaGraph在GCN的训练性能加速从2.4×lj-large提高到3.9×reddit在GraphSAGE上从1.3×lj-large加速到4.9×reddit。我们观察到预处理和DGLDGLPP的组合在两个GNN模型中表现不同即通过预处理实现的GCN性能加速优于GraphSAGE。这是由于GCN和GraphSAGE中使用的不同转发过程。在 GCN 中转发期间每个折点聚合来自其相邻要素的要素并将这些要素求和为一个要素。与GCN不同对于相应小批量中的每个顶点GraphSAGE必须保存自己的特征和来自其邻居的聚合特征。与GCN相比这导致GraphSAGE有更多的CPU-GPU数据传输。相比之下我们进一步观察到除了普通DGL之外我们在PaGraph中的优化可以更好地利用预处理优化的潜力。例如PaGraphPP将GCN和GraphSAGE在前6个数据集中的DGLPP性能提高了2.1×至3.0×和1.8×至6.2×。 训练时间细分。为了进一步探索 PaGraph 减少的数据加载开销我们将 DGL 和 PaGraph 上的 GCN 训练时间分解为 GPU 计算时间和 CPU-GPU 数据加载时间。我们使用nvprof [41] 和PyTorch Profiler [42] 收集此类系统统计信息。 Fig. 12 显示了与GCN相关的实验相对应的分解结果 Fig. 11 我们还观察到GraphSAGE的类似踏板。在此簇状条形图中从左到右每个条形聚类分别显示 DGL、DGLPP、PaGraph 和 PaGraphPP 的结果。与中 Section 2 给出的结果一致使用内置数据加载器的DGL面临严重的加载问题。尽管预处理可以节省计算和数据加载但它仍然受到数据加载瓶颈的影响该瓶颈占用了多达 61% 的训练时间。 与基线数据加载器相比由于缓存和流水线的共同努力PaGraph 完全重叠了数据加载阶段和 GPU 计算阶段从而消除了原始 GNN 模型及其启用预处理的变体的训练管道的加载成本。我们发现独立缓存足以在前三个数据集上训练目标模型。这是因为这些数据集很小可以完全缓存到 GPU 内存中并且数据加载时间可以忽略不计。与此不同的是尽管通过缓存后三个更庞大的数据集的数据加载时间已经从 65.7% 减少到 78.7%但它仍然占整个训练时间的 34.9%。在这种情况水线数据加载和计算可以完全将前一种情况的成本隐藏到后一种情况下。有趣的是在某些情况下计算时间略有减少例如 lj-large 数据集的“PaGraphPP”因为我们小心翼翼地避免了并行训练作业之间的 CPU 争用。但是在某些情况下计算时间略有增加例如enwiki数据集的“PaGraph”。这是因为后台预取过程会花费一些 CPU 周期这可能会影响 GPU 内核的启动。
5.3 Effectiveness of Caching Policy 缓存策略的有效性 接下来我们将静态缓存策略与 AliGraph [43] 中提供的策略进行比较该策略支持跨多个 CPU 机器的 GNN 训练。如果顶点的入度与出度比超过阈值则在本地缓存顶点从而降低训练任务与远程存储系统之间的通信成本。我们还比较了随机策略该策略将顶点随机保留在加载器中。为了帮助了解不同的缓存策略如何执行我们推导出了如果所有后续顶点访问都可以在缓存中吸收则可以获得最佳缓存命中率。我们将此最佳缓存命中率表示为“最佳”。推导是通过分析训练的访问痕迹来完成的。我们没有直接将PaGraph与AliGraph进行比较因为AliGraph的开源版本不包含缓存代码它是建立在TensorFlow之上而不是PyTorch的是为CPU机器设计的。为了进行公平的比较我们按照其论文中的描述在PaGraph中实现AliGraph缓存策略。 Fig. 13 分别显示了使用单个 GPU 的不同缓存比率下的缓存命中率。我们观察到当只有 20% 的图形被缓存时我们可以实现超过 50% 的命中率这是其他策略性能的 200% 以上。更有趣的是它表明我们的缓存策略并不复杂但非常有效非常接近最佳情况。我们还在其他数据集上实现了类似的接近最优缓存命中率。此外我们还探讨了PaGraph和AliGraph实现的不同缓存命中率的性能影响。如 所示 Fig. 14 随着缓存图数据比例的增加DGL 和 PaGraph 实现的每纪元训练时间不断下降并在缓存所有必需数据时收敛到 6.7 秒。但是当缓存大小受到限制时PaGraph的缓存策略比AliGraph的策略实现了高达1.5×的性能加速。更有趣的是当缓存百分比达到 40% 时训练性能变得稳定并且当使用更多缓存空间时没有观察到进一步的改进。这是因为在那个关键点数据加载时间减少到比 GPU 计算时间短我们的流水线机制可以完全重叠这两个阶段。这进一步揭示了结合缓存和流水线的额外好处这使得我们的解决方案适用并在 GPU 内存限制下提供良好的性能。 通过我们的缓存策略与DGL相比PaGraph在大型图形上实现了大量的数据加载减少。 Table 4 显示了 GCN 训练期间每个训练器中每个 epoch 的平均减少数据加载量。总体而言我们分别实现了 lj-link、lj-large 和 enwiki 数据集的 91.8%、80.9% 和 81.0% 的负载减少。 5.4 Multi-GPU Performance 多显卡性能 我们评估不同数量 GPU 的可扩展性。 Fig. 15 显示了针对具有不同数量 GPU 的真实数据集 enwiki 训练 GCN 和 GraphSAGE 的实验结果。当使用更多的GPU时DGL和PaGraph都能实现更高的吞吐量。然而一般来说PaGraph的性能优于DGL并且在不同的硬件配置下显示出更好的可扩展性例如PaGraph的性能优于DGL高达2.4×GCN为4个GPU。我们进一步评估了PaGraph在多个GPU上的性能以显示其在不同算法优化上的有效性。为此我们放大了使用 2 个 GPU 时的性能数字并在 中 Fig. 16 总结了结果。PaGraph在所有数据集上实现了2.1×至5.6×的DGL性能。通过预处理优化PaGraph 可以在 DGL 上实现从 2.8× 加速到 8.5×。显著加速的原因有两个。首先多个GPU为缓存提供更多可用内存从而实现更高的缓存命中率和更低的数据加载成本。为了确认这一点我们还在 enwiki 上测试了 GCN 的性能在四个 GPU 上总缓存大小固定为 6 GB。它表明 4-GPU 上的加速比仅为 3.7×比在没有缓存大小限制的情况下实现的加速比低 23%。其次在所有测试案例中数据加载比计算运行得更快因此我们的管道机制将其完全隐藏在计算中。 5.5 Implications of Graph Partition 图分区的含义 为了验证图分区支持的数据并行训练的好处我们首先调整 DGL 以使用我们的缓存机制表示为“DGLCache”然后将 PaGraph 与 DGLCache 进行比较唯一的区别是只有前者使用分区图数据而后者使用非分区的完整图。 Fig. 17a 说明了不同数量 GPU 下的缓存命中率。由于 DGLCache 中的训练器共享相同的全局图形存储该存储保持完整的图形结构因此每个训练器访问的 GPU 缓存中的缓存部分是相同的。但是在 PaGraph 中随着训练器数量的增加每个训练器都会使用从较小的训练顶点集采样的顶点并表现出更好的数据局部性。因此当使用更多的 GPU 时PaGraph 实现的缓存命中率不断提高而 DGLCache 观察到缓存命中率下降。这种差异可以直接转化为 Fig. 18 性能差距使用 4 个 GPU。通过将缓存与分区相结合PaGraph的性能分别比DGLCache和DGL高出25%和52%。流水线机制可以进一步将GCN的训练速度提高27%。 然而图分区的改进是有代价的即跨分区的冗余和离线时间成本。接下来我们定量分析它们的影响。 Fig. 17b 显示分区数变化时单个分区中的顶点与整个图形的比例。 y -axis 表示每个分区相对于完整图形所占的比例。随着分区数的增加每个分区的顶点数也会减少。使用我们的算法我们在 8 分区配置中为每个分区带来一小部分冗余顶点占完整图形大小的 2.5% 到 21.5%。考虑到使用分区实现的训练加速此成本仍然是可以承受的。其次显示总共 6 个数据集中 4 个较大数据集的总体分区成本 Table 5 范围从 6.0 到 32.2 分钟。我们认为这是可以接受的因为分区是离线执行的一次性任务其成本可以在多个时期和重复训练中分摊以进行超参数调优 [44] 。 5.6 Effects of Pipelining 流水线的影响 接下来我们将注意力转移到理解流水线数据加载和计算的影响上。在这里我们选择 friendster 数据集它比 中的 Table 2 其他六个数据集大得多。这个大型数据集消耗 358 GB CPU 内存即使使用 4 个 GPU也只能缓存其顶点要素的 25%。因此有了这个数据集我们可以将流水线的性能优势与缓存隔离开来。为此我们通过增量添加 中 Section 3 介绍的每个优化来训练 GCN 和 GraphSAGE并在 中 Fig. 18 报告训练速度数字。在这里我们使用邻居采样方法并启用预处理。与原版DGL相比由于缓存机制GCN和GraphSAGE的“DGLCache”实现了1.4×和1.3×的加速。除了缓存之外启用图形分区还可以将两个 GNN 模型的性能分别提高 25.1% 和 28.1%。但是在这种情况下将缓存和分区组合在一起不足以充分探索训练加速机会因为降低但未消除的数据加载成本仍然会对整体性能产生负面影响。因此最后打开流水线可以进一步将GCN和GraphSAGE的每个epoch训练时间分别减少27.3%和29.3%。
5.7 Impact of Data Loading Volumes 数据加载量的影响 为了验证 PaGraph 的鲁棒性我们评估了每次训练迭代所需的图形数据量的性能加速。 Fig. 19 显示了在 DGL、DGLPP、PaGraph 和 PaGraphPP 上不同数量的采样邻居的训练性能。随着采样邻居数量的增加GNN 计算将消耗更多的 GPU 内存例如在 GCN 中将邻居大小从 2 更改为 16 时从 1 GB 增加到 5 GB从而导致缓存容量降低。由于缓存的图形功能较少这可能会限制 PaGraph 带来的性能改进。然而如 所示 Fig. 19 PaGraph 的性能不断优于 DGL其变体与预处理相结合可以实现均匀幅度的加速例如在 16 个采样邻居中livejournal 的 27.6× 和 lj-link 的 29.2×。当面对更大的邻居尺寸时PaGraph 的性能大幅提升有三个原因。首先对于DGL基线采样邻居的数量更大数据加载和计算之间的不平衡更严重。其次尽管空间减少但 GPU 上的缓存仍然会显著缩小数据加载量因为缓存策略更喜欢保留具有较高出度的顶点。第三流水线可以补偿具有较小缓存的性能改进损失正如对缓存有效性的评估所证明的那样请参阅 Fig. 14 和 Section 5.3 。 5.8 Supporting Other Sampling Method 支持其他采样方法 为了验证PaGraph设计对其他采样方法的有效性我们选择逐层采样方法作为另一个案例研究该方法与相邻采样的不同之处在于固定每层的大小以避免感受野呈指数增长。 Fig. 20a 显示了GCN和GraphSAGE使用单个GPU在三个数据集上的训练性能。在没有预处理的情况下PaGraph实现了GCN从2.5×lj-large到3.1×enwiki的训练加速以及GraphSAGE从2.3×lj-large到2.5×enwiki的训练加速。启用预处理后对于GCN和GraphSAGEPaGraphPP的训练速度分别提高了1.9×至2.7×和1.9×至2.6×。这些结果表明PaGraph也适用于其他采样方法并带来类似的性能加速。我们通过预测 中的 Fig. 20b 分解时间成本来进一步了解对训练加速的贡献。我们观察到PaGraph比DGL减少了高达93.5%的数据加载时间PaGraphPP比DGLPP减少了高达91.3%。同时数据加载时间可以通过计算隐藏这将进一步减少高达34.1%的训练时间。最后我们研究使用PaGraph进行GNN训练的可扩展性。 Fig. 20c 表明与之前评估的邻居采样方法类似PaGraph 还可以通过分层采样实现线性扩展以便在最多 4 个 GPU 上的三个数据集上训练 GCN 和 GraphSAGE。 5.9 Training Convergence 训练收敛 为了确认我们实现的正确性以及洗牌的影响我们评估了在PaGraph启用预处理之上使用邻居采样和逐层采样NS以及4个GPU上的reddit数据集上的DGL库训练两个执行的GNN模型的验证准确性。DGL采用全局洗牌而PaGraph采用局部洗牌。如 所示 Fig. 21a 无论使用哪种采样方法在 GCN 模型上PaGraph 收敛到与原始 DGL 大致相同的精度但在收敛速度上优于 DGL 7.4× NS 和 8.5× LS。这是因为与DGL相比PaGraph需要相同的迭代次数才能达到相同的精度但迭代速度更快。我们可以根据 得到 Fig. 21b GraphSAGE 模型的类似结论。我们没有对Reddit以外的数据集进行类似的实验因为这些数据集中的顶点特征是随机初始化的。 Related Work 相关工作 GNN 培训框架。像PyTorchMXNet [23] [25] 和TensorFlow [9] 这样的深度学习框架已经在学术界和工业界被广泛采用。但是这些框架没有提供 GNN 所需的足够图操作。因此近年来它推动了一些专门框架 [10] [11] [13] [43] [45] [46] [47] [48] 的诞生、它们都借用并扩展了传统的图形处理原语和顶点规划抽象到当前的深度学习框架中。例如NeuGraph [13] 通过Scatter-ApplyEdge-Gather-ApplyVertexSAGA开发图运算原语以提供高效便捷的编程模型。 全图与抽样训练。全图训练在每次前向-后向传播中训练具有完整图数据的图神经网络模型而采样训练仅在每次前向-后向传播中训练部分顶点和边。为了处理无法完全填充到 GPU 中的大图PBG [46] 和 NeuGraph [13] 将完整图拆分为块并迭代地将每个块及其顶点数据加载到 CPU 和 GPU 中分别进行全图计算。对于采样训练DGL [10] 在 CPU 共享内存中定位完整图形及其数据并且仅在每次前后传播开始时将所需的顶点和边缘数据加载到 GPU 内存中。对于大型图最近的工作 [19] 已经表明采样训练可以实现比具有相似最终模型性能的全图训练更快的收敛数倍。AliGraph是一个支持在CPU平台上进行基于采样的GNN训练的平台而不是探索GPU的潜力 [43] 。 缓存。缓存图数据有利于许多图处理任务 [43] [48] 。 [49] 预选 [49] 应用静态缓存策略来加速类似 BFS 的计算。AliGraph [43] 为分布式计算场景缓存顶点及其数据以避免训练器和远程存储之间的通信成本。但是正如我们在 中 Section 5.3 验证的那样它的缓存策略不适合基于邻居的采样特征。ROC [48] 以全图训练为目标并探索了一种有效的策略通过利用分区和缓存在 CPU 和 GPU 之间交换 GNN 模型的中间结果。我们与ROC不同因为处理中间结果不是基于抽样的GNN训练的主要关注点。 图形分区。分区图、 [8] 、 [20] [21] [50] [51] 在 [52] 分布式计算中被广泛采用。PowerGraph [8] 为幂律图设计了一种顶点切割分区算法。NeuGraph [13] 利用Kernighan-Lin [21] 将图划分为具有不同稀疏程度的块。 [47] 进一步提出了一种GNN特有的图分区算法以减少多台机器之间的通信开销。上面提到的所有分区算法都是为非GNN任务或全图GNN训练而设计的。我们的分区算法专为采样训练而设计并与缓存配合使用。 其他优化。Gorder [53] 设计了一种通用的图重新排序方法来加速图处理任务。Norder [49] 为类似BFS的任务提出了一种量身定制的重新排序技术。我们已经在 PaGraph 中实现了这些技术但发现分区质量或训练性能都没有显着改善。
Discussion and Future Work 讨论和今后的工作 虽然我们相信PaGraph可以使广泛的GNN模型和系统受益但在使其更加普遍和适用于更广泛的环境之前仍有一些开放的挑战需要解决。 数据加载和计算比率。缓存策略作为 PaGraph 的核心当数据加载阶段主导整个训练过程时效果很好。但是其相对比率是特定于模型的。除了GCN和GraphSAGE这两个具有代表性和成功的GNN模型被广泛采用之外我们还研究了其他模型如GATGIN [4] [54] 和diffpool [55] 。这里的初步结论是与看起来类似于GCN和GraphSAGE的GAT和GIN相比diffpool的计算量更大。因此预计PaGraph比其他四种模型受益更少的diffpool。然而GNN计算优化的出现 [56] 可以进一步强调数据加载和计算之间的不平衡并使PaGraph仍然是未来GNN模型的有效设计。 不同的采样模式和不断发展的图形。显然通过采样方法执行的图形遍历模式在确定良好的缓存效率方面起着关键作用。如果相应的采样方法不假设更有可能选择具有高出度的图形顶点则当前 PaGraph 实现的性能改进将受到限制。此外PaGraph 采用静态缓存和分区策略因此无法处理假设可训练或跨迭代更改的特征的采样方法例如控制变量 [19] 。最后尽管大多数现有工作都集中在静态图上但通过动态图训练GNN模型吸引了越来越多的兴趣 [57] 。 [58] 由于顶点出度和图偏度随着图的演变而迅速变化因此需要设计一种动态缓存和分区策略具有持续的缓存效率和适中的成本以及用于补充缓存的可调管道其性能受数据局部性和缓存图部分的限制。 以 GPU 为中心的方法。PaGraph 针对的数据加载效率问题与当前 CPU-GPU 协处理架构高度相关在 DNN 社区中广泛使用。最近已经有一些初步的努力来探索以GPU为中心的优化来消除此类问题例如 GPU采样 [59] 。这些方法可以为小型图形提供最高的性能加速其功能可以完全适合GPU内存。在这种情况下不仅可以消除繁琐的CPU到GPU数据加载阶段还可以利用GPU的高处理密度和内存带宽进行快速采样。然而对于较大的图形来说这仍然具有挑战性因为涉及 GPU 的 CPU 外数据访问和有限的 PCIe 带宽可能会抵消 GPU 采样的好处。幸运的是新的 GPU irect 存储技术 [60] 在快速 NVMe 存储和 GPU 内存之间提供了直接数据路径并通过实验演示了通过绕过 CPU 来提高的数据加载性能。因此值得在硬件创新的背景下考虑PaGraph的设计要点。
Conclusion 结论 为了加速GNN在大型图上的训练性能我们提出了PaGraph这是一种基于采样的通用训练方案它利用了GNN计算感知缓存和图分区的组合。我们在DGL和PyTorch上实现了PaGraph并使用两种广泛使用的采样方法在7个图数据集上使用2个代表性GNN模型对其进行评估。实验结果表明PaGraph完全隐藏了数据传输成本与DGL相比性能提升高达4.8×。通过预处理PaGraph甚至可以实现16.0×的性能提升。
ACKNOWLEDGMENTS 作者衷心感谢所有匿名审稿人的深刻反馈。这项工作部分得到了中国国家重点研发计划2018YFB1003204的支持部分得到了中国国家自然科学基金61 802 358和61 772 484的资助部分得到了中国科学技术大学双一流项目研究基金“YD2150002006的支持部分得到了华为和Microsoft的支持。
