转载请注明出处：小锋学长生活大爆炸[xfxuezhang.blog.csdn.net] 原文、视频与PPT：P3: Distributed Deep Graph Learning at Scale | USENIX
目录
摘要
1 Introduction
2 Background & Challenges
2.1 Graph Neural Networks
2.2 Distributed Training of GNNs
2.3 Challenges in Distributed GNN Training
2.3.1 Challenge #1: Communication Bottlenecks Due to Data Dependencies
2.3.2 Challenge #2: Ineffectiveness of Partitioning
2.3.3 Challenge #3: GPU Underutilization
3 P3: Pipelined Push-Pull
3.1 Independent Hash Partitioning Graph & Features
3.2 Push-Pull Parallelism
3.2.1 Computation Graph Generation
3.2.2 Computation Graph Execution
3.3 Pipelining
3.4 Caching
3.5 P3 API
4 Implementation
5 Evaluation
5.1 Overall Performance
5.2 Impact of Sampling
5.3 Impact of Partitioning Strategy
5.4 Impact of Layers
5.5 Impact of Features
5.6 Microbenchmarks
5.7 P3’s Scaling Characteristics
5.8 Accuracy
5.9 Comparison with ROC
5.10 P3 Shortcomings
6 Related Work
7 Conclusion
Acknowledgements
摘要
图神经网络(GNNs)近年来得到了极大的关注，并成为深度学习中发展最快的子领域之一。虽然已经提出了几种新的GNN架构，但现实世界图的规模——在许多情况下有数十亿个节点和边——在模型训练期间提出了挑战。在这篇论文中，我们提出了P3，一个专注于将GNN模型训练扩展到分布式环境中的大型真实图的系统。我们观察到训练gnn时的可伸缩性挑战与训练经典深度神经网络和分布式图处理时的可伸缩性挑战有本质的不同;通常使用的技术，例如图的智能划分，并不能产生预期的结果。基于此，P3提出了一种新的分布式GNN训练方法。我们的方法有效地消除了高通信和分区开销，并将其与基于并行的流水线推拉执行策略相结合，以实现快速模型训练。P3公开了一个简单的API，它捕获了许多不同的GNN体系结构的通用类。当进一步结合一个简单的缓存策略时，我们的评估表明P3能够比现有的最先进的分布式GNN框架的性能高出7倍。
1 Introduction
深度学习，以深度神经网络(DNNs)的形式，已经成为多个具有挑战性的应用领域的事实上的工具，如计算机视觉[27]，语音识别[28]和自然语言处理[18]，在这些领域他们产生了与人类专家[9]相当的结果。近年来，人们对图神经网络(GNNs)——运行在图结构数据上的神经网络——产生了浓厚的兴趣，这使其成为深度学习中增长最快的子领域之一。由于图在捕获输入元素之间丰富的关系信息方面的表达能力，gnn在许多重要领域取得了突破，包括推荐系统[51,66]、知识图[53]和药物发现[46,58]。
在GNN中，输入图中的节点与特征和标签相关联。gnn的典型任务包括节点分类(预测节点的类标签)[41]、链接预测(预测给定节点之间存在链接的可能性)[70]和图分类(图的预测类标签)[8]。为了完成这些任务，gnn将特征信息与图结构结合起来，学习节点的表示——低维向量嵌入。因此，学习这种深度编码是gnn的关键目标。目前存在几种新颖的GNN架构，包括GraphSAGE[24]、图卷积网络(GCNs)[17,41]和图注意网络(GA Ts)[59]。虽然每一种都有自己独特的优势，但它们在如何使用图结构来学习嵌入以及使用何种神经网络转换来聚合邻域信息方面存在根本差异[64]。
在高层次上，gnn通过结合迭代图传播和DNN操作(例如，矩阵乘法和卷积)来学习嵌入。图结构用于确定要传播什么，神经网络指导如何进行聚合。每个节点基于其邻域创建一个k-hop计算图，并使用它们的特征学习其嵌入。训练gnn和dnn之间的关键区别之一是数据样本之间的依赖关系: 传统的dnn训练彼此独立的样本(如图像)，而图的连接结构强加了依赖关系。此外，在图中与每个节点关联的大量密集特征(从100个到几千个[29,66,68])是很常见的。因此，由每个节点创建的k-hop计算图可能大得令人望而却步。邻域采样[24]等技术在一定程度上有所帮助，但根据图结构的不同，即使是采样的计算图和相关特征也可能无法容纳单个GPU的内存，这使得可伸缩性成为训练gnn的一个基本问题[71]。随着拥有数十亿节点和边的大型图在学术界和工业界[55]的流行，以分布式方式实现GNN训练是一个重要而富有挑战性的问题。
在本文中，我们提出了一个P3系统，它可以在大输入图上实现gnn的高效分布式训练。P3的动机来自三个关键的观察结果。首先，由于数据依赖性，我们发现在gnn的分布式训练中，大部分时间都花在了网络通信上，以生成具有特征的嵌入计算图。其次，我们注意到，依赖分布式图处理技术，如高级分区方案，虽然在图处理上下文中很有用，但对gnn没有好处，在许多情况下可能是有害的。最后，由于网络通信问题，我们观察到分布式GNN训练中的gpu没有得到充分利用，并且高达80%的时间被阻塞在通信上。因此，P3专注于可以减少甚至消除这些低效的技术，从而提高性能。
P3并不是解决GNN可伸缩性挑战的第一个。虽然有许多可供GNN训练的框架，但其中大多数专注于单机多gpu训练和有限的图形大小[20,45,47]。流行的开源框架，如深度图库(DGL)[1]已经包含了分布式训练的支持。但正如我们在本文中所展示的，由于网络通信频繁，它面临着许多挑战，表现出较差的性能。ROC[36]是一个最新的系统，它与P3有着相同的目标，但提出了一种截然不同的方法。ROC使用复杂的在线分区器、利用CPU和GPU的内存管理技术，并依赖高速互连(NVLink和InfiniBand)等硬件支持，广泛优化GNN训练。相比之下，P3只假设PCIe链路和以太网连接，不依赖于任何智能分区方案。在训练过程中，ROC要求特征在机器之间移动，而在P3中，特征从不跨网络传输。最后，我们的评估数据集比roc要大得多，这帮助我们发现了一些用较小的图可能会遗漏的挑战。
为了实现其目标，P3利用了gnn的一个关键特征: 与传统dnn的数据样本(如图像)小而模型参数大(例如Megatron[56]的数据样本为80亿，图灵nlg[7]的数据样本为170亿)不同，gnn的模型参数小但数据样本大，这是因为与每个节点的采样计算图相关的密集特征向量。因此，在现有的GNN框架中，这些特征向量的移动占网络流量的大部分。在P3中，我们完全避免了特征的移动，并建议将图结构和特征独立地分布在机器之间。为此，它只依赖于快速、计算简单且开销最小的随机散列分区器。此外，当与P3包含的其他技术相结合时，基于哈希的分区可以实现工作平衡和效率(§3.1)。
在嵌入计算中，P3采用了完全不同的方法。P3不是通过拉节点的邻域和相关特征来创建计算图，而是只拉图结构，它明显更小。然后提出了推拉并行，这是一种结合了层内模型并行和数据并行的执行计算图的新方法。P3从不跨网络移动特征，而是将计算密集层(第1层)中的计算图结构推给所有机器，然后使用层内模型并行执行第1层的操作。然后，它提取更小的部分激活，累积它们，并使用数据并行继续执行其余k−1层的操作(§3.2)。
由于分区策略和基于推拉并行的执行，P3能够使用简单的流水线技术，高效地重叠大部分计算和通信，从而有效地隐藏(已经很小的)通信延迟(§3.3)。此外，分区策略还使P3能够提出一种简单的缓存机制，如果内存允许进一步减少网络通信，可以在多台机器上贪婪地缓存图和/或特征分区(§3.4)。P3提出的技术是通用的，适用于几种最先进的GNN架构。P3还将所有这些优化封装在一个简单的P-TAGS API(partition, transform, apply, gather, scatter 和 sync)中，开发人员可以使用该API编写新的GNN架构，并从其技术中受益(§3.5)。
这些技术的结合使P3的性能比最先进的分布式GNN框架DGL[1]高出7倍。此外，P3能够支持更大的图，并且可以优雅地伸缩(§5)。
我们在本文中做出了以下贡献:
- 我们观察到应用分布式图处理技术进行缩放GNN模型训练的缺点(§2)。在此基础上，P3采用了一种全新的方法，只依赖于图和特征的随机哈希分区，从而有效地消除了分区的开销。(§3.1)
- P3提出了一种基于混合并行的执行策略，它将层内模型并行和数据并行结合起来，显著减少了网络通信，并为流水线计算和通信提供了很多机会。(§3.2)
- 我们展示了P3可以优雅地扩展到大型图，并获得了显著的性能优势(与DGL[1]相比可达7×，与ROC[36]相比可达2×)，这些优势随着输入大小的增加而增加。(§5)
2 Background & Challenges
我们首先简要介绍了gnn的背景知识，然后用gnn的分布式训练来激发挑战。
2.1 Graph Neural Networks
GNN是一种以图结构数据作为输入的神经网络。输入图包含节点(实体)、边(节点之间的关系)和所有节点的特征。gnn的基本操作是获取图中节点的表示形式。它们将节点映射到d维的嵌入空间，这样图中相似的节点(例如，通过邻近性)彼此嵌入得很近。为了获得这些嵌入，gnn将与节点相关的特征信息和使用从其邻域传播和转换的信息的图结构结合起来。在计算嵌入时，图结构表示传播的内容，并使用神经网络来确定传播的信息如何转换。从嵌入派生出的确切邻域是可配置的，通常gnn从节点[26]使用k(通常是2个或更多)跳。在每一跳转换信息的神经网络被称为GNN中的一层，因此2跳(k-hop)邻域转换为2 (k)层GNN(图1)。
理论上可得节点v在k层邻域聚合后的嵌入zv为h^k_v[24]，其中:
其中hiv为i层聚合后节点v的表示，Wi为i层(i≥1)所有节点共享的可训练权矩阵，h0v利用节点特征进行初始化。AGGREGA TE(k)(.)和COMBINE(k)(.)的选择对于如何定义层和计算嵌入非常关键。
2.2 Distributed Training of GNNs
现有的训练gnn的框架，如深度图库(DGL)[1]，通过将分布式图处理技术与DNN技术相结合，支持分布式训练，如图2所示。输入图和特征在集群中的机器之间进行分区。给定批处理大小(1)，通过将每个节点的k-hop邻域和相关特征(2)拉出，生成批处理中每个节点(通常称为训练样本)的计算图。这需要与集群中的其他机器进行通信。一旦构建了计算图，标准的DNN技术(如数据并行)被用来执行计算——创建小批并复制到GPU内存(4)，然后模型计算被触发(5)。
2.3 Challenges in Distributed GNN Training
为了使分布式GNN训练更有效，有几个挑战需要解决。
2.3.1 Challenge #1: Communication Bottlenecks Due to Data Dependencies
与训练数据彼此独立(如图像)的传统dnn不同，gnn以图结构的形式在训练输入之间施加依赖关系。因此，即使提供的批处理大小可能很小(例如1000)，由于k-hop邻域和相关特征，计算图样本可能会呈指数级增大。如此大的尺寸的一个主要原因不是图结构本身，而是特征，其大小通常在100到几千秒之间[29,41,66,68]。在由数十亿节点和边组成的真实图中[15,55]，2跳邻域可能比1跳邻域[43]大一个数量级。当结合这些特性时，得到的计算图很容易超过单个GPU的内存，甚至超过服务器的主存。解决这种邻域爆炸的常用技术是[24]采样。也就是说，我们不获取每一跳节点的所有邻居，而是只选择一个固定的数目。如图3所示，其中节点1的2跳计算图是通过在每一跳采样两个邻居生成的。然而，即使有了采样，基于使用的采样和GNN中的层数，计算图的大小也会大幅增长。由于这些邻域节点及其特征必须通过网络获得，因此gnn的分布式训练在网络通信中花费了很大一部分时间。
2.3.2 Challenge #2: Ineffectiveness of Partitioning
分区是一种在分布式图处理中实现可伸缩性的常用方法，现有的GNN框架利用流行的分区策略在机器间分布图和特性。然而，这种方法有两个缺点。
首先，许多分区方案在计算和/或内存开销方面产生成本。在表1中，我们展示了一个代表性GNN、GraphSAGE[24]上的分区时间、内存消耗和完成一个训练周期的时间，用于四种不同的分区方案:哈希[48]使用随机哈希对节点进行分区，METIS[38]是一种平衡的最小边切分区器，RandomV ertexCut[22]和GRID[23]是点切分区器，以及3D[69]，一种最近提出的用于机器学习工作负载的方案。我们看到，性能最好的分区方案(例如，切边)会产生很高的计算开销。计算速度较快的方案要么导致较高的内存开销(由于复制，例如，顶点切割)，要么导致性能下降。
其次，随着GNN层数的增加，分区的好处受到了严重限制。回想一下，gnn使用k-hop邻域来计算嵌入。虽然分区方案减少了通信，但它们只优化了第一跳的通信。因此，当层数增加时，所有分区方案都会失败。
2.3.3 Challenge #3: GPU Underutilization
现有的GNN框架利用DNN技术(如数据并行)来训练GNN模型。在数据并行执行中，每台机器操作一组不同的样本。然而，由于前面描述的数据依赖导致的通信瓶颈，我们观察到，在使用流行框架DGL的分布式GNN训练中，gpu仅被利用了约20%的时间。在很大一部分(≈80%)的时间里，gpu都在等待通信。最近的研究报告显示，数据复制是在单机多gpu设置[45]中训练gnn的主要瓶颈，但我们发现，在使用分布式多gpu设置训练gnn时，数据复制只占5%的时间。我们注意到[45]中提出的技术与我们的工作是正交的，如果应用到P3中可以受益。因此，由于网络通信的原因，gpu在分布式GNN训练中没有得到充分利用。可选的并行技术，例如模型并行不适用于gnn。这是因为对于每一层，除了数据依赖引起的通信外，它们还会引起层内通信，因此与数据并行相比，它们的性能甚至更差。
3 P3: Pipelined Push-Pull
P3提出了一种新的分布式GNN训练方法，将计算图的生成和执行减少到最小。为了实现这一点，P3包含了几种技术，我们将在本节详细介绍。
3.1 Independent Hash Partitioning Graph & Features
正如我们在§2中所示，由于GNN的特性，以智能方式对输入图进行划分并不会显著地有利于GNN架构。因此，在P3中，我们使用最简单的划分方案，主张对图及其特征进行独立的划分。
输入图中的节点使用随机散列分区器进行分区，边与它们的传入节点位于同一位置。这相当于许多分布式图处理框架中常用的1D分区方案[22,67]，计算简单。与其他方案(例如，2D分区)不同，该方案不需要任何预处理步骤(例如，创建本地id)，也不需要维护一个单独的路由表来查找节点所在的分区，它可以简单地动态计算。注意，图的这种划分只是为了确保P3能够支持大型图。在一些情况下，现实图的图结构(没有特征的节点和边)可以保存在现代服务器类机器的主内存中。在这些情况下，P3可以简单地在每台机器上复制整个图结构，从而进一步减少通信需求。
虽然图形结构可能适合内存，但输入特征却不能这样说。典型的gnn处理的输入图的特征向量大小从100到几千秒不等[29,41,66,68]。P3沿特征维度对输入特征进行分区。也就是说，如果特征的维数为F，那么P3将每个节点的F/N特征分配给N台机器集群中的每台机器。这与现有的针对机器学习任务的分区方案形成了对比，包括最近提出的3D分区方案[69]。图4显示了P3如何将一个简单的图与现有的流行分区方案进行比较。
正如我们将看到的，这种独立的、简单的图和特征划分使P3的许多技术成为可能。沿着特征维度分解输入是至关重要的，因为它使P3在计算嵌入时实现工作平衡; 由于基于哈希的分区器确保了层中的节点和特征在远离其嵌入计算节点的节点中均匀地分布在整个集群中。独立划分结构和特征的简单性也让P3在缓存机制中独立缓存结构和特征(§3.4)。
3.2 Push-Pull Parallelism
P3在对输入图和特征进行分区后，采用通用的、以小批为中心的GNN计算，类似于现有的GNN框架，它首先为节点生成计算图，然后执行它。我们用图5来详细解释这一点。
3.2.1 Computation Graph Generation
在每个小批的开始，其嵌入被计算的每个节点生成其计算图。为此，P3为节点拉取k-hop邻域。如果GNN架构支持基于采样的嵌入计算，P3抽取采样的k-hop邻域，否则抽取完整的k-hop邻域。注意，与现有的GNN框架不同的是，在这两种情况下特性都不会被提取。这大大减少了创建计算图所需的网络通信。如果整个图结构在每台机器上都可用，则这是一个本地操作，否则将导致最小的网络通信，因为图结构的权重非常轻。在这个过程结束时，P3在拥有该节点的机器上得到了小批中每个节点的k层计算图(例如，图5中的四个样本对应于小批中四个节点的计算图)。注意，现有的GNN框架除了提取结构之外还提取特征，因此在这些框架中，拥有节点的机器最终会获得计算图和嵌入计算所需的所有特征。
在现有gnn的情况下，现在每台机器都可以以数据并行的方式独立执行其获得的完整计算图，从第1层开始，在每个层边界调用全局梯度同步，如图后向传递中的图5a所示。然而，由于P3不移动特征，计算图不能以数据并行的方式执行。在这里，P3提出了一种混合并行方法，它结合了模型并行和数据并行，我们称之为推拉并行。传统的dnn由于资源利用不足和难以确定如何划分模型[49]，很少使用模型并行，P3充分利用它。由于gnn的特性，模型(嵌入计算图)很容易清晰地划分，因为边界(跃点)很清楚。此外，由于P3的分区策略，在我们的上下文中，模型并行不会受到资源利用不足的影响。
3.2.2 Computation Graph Execution
要开始执行，P3首先将第1层的计算图推到所有的机器，如图5b中的1所示。注意，第1层是最密集的计算，因为它需要来自第0层(具有最多的扇出)的输入特征，由于我们的分区方案，这些输入特征被均匀地分布在P3中。每台机器一旦获得计算图，就可以以模型并行的方式(1M层)启动第1层的正向传递。在这里，每台机器使用它拥有的输入特征的分区(2)计算第1M层的部分激活。由于集群中的所有gpu共同执行需要从最扇出输入的层，这避免了gpu的利用率不足。我们观察到，现有GNN框架(如DGL)中的gpu在网络上阻塞的时间为≈80%，而P3的阻塞时间为≈15%。一旦计算出部分激活，分配给哈希分区方案中每个节点的机器就会从所有其他机器中提取它们。接收部分激活的节点使用reduce操作(3)聚合它们。此时，P3切换到数据并行模式(1D层)。然后将聚合的部分激活传递给其余的1D层操作(如果有，例如，不能部分计算的非线性操作)，以获得第1层(4)的最终激活。计算以数据并行的方式进行，以获得向前传递结束的点(5)的嵌入。
向后传递的过程类似于现有GNN框架的数据并行方式，调用全局梯度同步，直到第1D(6)层。在1D层，P3将错误梯度推到集群(7)中的所有机器，并切换到模型并行。现在，每台机器都有误差梯度，在1M层局部(8)应用后向通过，后向通过阶段结束。
虽然以模型并行方式进行的部分激活计算似乎在一般意义上有效，但它们受限于可以从部分结果聚合的转换。但是，在某些GNN架构中(如GA T [59])， 1M层本身可能引入非线性变换。P3依赖于开发人员的输入来确定在模型并行执行期间需要全局同步的张量，以确保正确性(§3.5)。
乍一看，P3中的额外步骤，即需要在第1层中推入图结构，在向前传递期间聚合部分激活，以及向后传递中附加的梯度移动，可能看起来像是可能导致效率低下的开销，而不是像现有GNN框架中那样简单地沿着图结构拖动特征并在本地执行一切。然而，P3的方法可以显著节省网络通信。首先，P3完全不拉特征，这极大地减少了网络流量——通常GNN计算图中的2跳邻域比1跳邻域大一个数量级。其次，无论GNN中有多少层，只需要对第1层进行部分计算和聚合。最后，gnn中激活和梯度的大小很小(由于隐藏维度的数量较少)，因此传输它们比传输特征所需的开销要小得多。
为了说明这一点，我们使用了一个简单的实验，我们在4台机器上的开源OGB-Product[29]数据集上运行了一个代表性的GNN，一个2层GraphSAGE[24]。我们选择1000个标记节点来计算嵌入并使用邻域抽样(扇出:25,10)。节点与大小为100的特征向量相关联，有16个隐藏维度。在0层(2跳)有188339个节点，在1层(1跳)有24703个节点。将特征与图结构一起拖动将产生71.84 MB的网络流量。另一方面，激活矩阵的大小为输入×隐藏维数。P3只需要从其他3台机器转移部分激活，因此只需占用5 MB (3 × 24703 × 16)。因此，P3通过分布拥有最多特征的层的激活计算，可以大幅减少网络通信。
3.3 Pipelining
与现有GNN框架相比，P3基于推拉并行的GNN计算图的创建和执行虽然需要较少的网络通信，但需要更多的通信次数:P3需要推第1层的图结构，在前向传递中拉部分激活，最后在后向传递中推梯度。此外，由于P3侧重于分布式设置，因此CPU和GPU之间需要进行数据复制。因此，除非使用管道技术将它们重叠，否则在通信过程中计算会停止。注意，当前的GNN框架(例如DGL)已经重叠了计算和通信——当CPU忙于创建计算图时，GPU被用来执行已经准备好的小批处理。
在P3中，我们采用了一个简单的流水线机制，灵感来自于PipeDream的流水线并行[49]。由于我们在P3中采用了推拉并行的方法，即在第1层的模型和数据并行之间切换，P3需要在每个小批中执行四个阶段: 前向通中的模型并行相位，前向通中的数据并行相位，后向通中的数据并行相位，最后是后向通中的模型并行相位。这为我们提供了在阶段之间创建数据依赖之前安排3个小批计算的机会。因此，我们在两者之间重叠计算，如图6所示。如图所示，在正向通段中，小批3的数据并行阶段(记为3D)对正向通段中的模型并行阶段(3M)有数据依赖性。因此，当3M阶段开始通信时，我们从其他小批中安排两个向前和两个向后传递。这种2向前2向后的静态调度策略允许我们避免停顿。我们目前使用静态管道调度——尽管基于分析的方法来确定管道调度可能会带来好处，但我们将其推迟到未来的工作中。
Bounded Staleness 如前所述，使用流水线的主要挑战是引入了可以用管道延迟来描述的陈旧性:从读取权重以计算梯度到使用计算梯度更新权重之间经过的优化器步骤数。这种延迟受到任何时候流水线中的小批数量的限制，也存在于先前的工作中[49,52]。对于P3，这个延迟是固定的，并且绑定为3，导致表单的权重更新:
式中，wt为t优化器步骤后的权值，∇f为梯度函数，α为学习率，wt−3为前后传递时使用的权值。虽然无界的陈旧梯度更新会对网络的统计效率产生负面影响，阻止收敛并产生精度较低的模型，但有界延迟可以使P3在与数据并行相同的epoch数内达到目标精度。
Memory Overhead 虽然P3的峰值内存占用与数据并行性相当，但存储的权重可能会导致额外的内存开销。目前，GNN模型通常只包含几层小型DNN模型，因此即使有权重存储，开销也相对较小。然而，随着未来GNN模型变得更大更复杂，这种情况可能会改变。P3的内存开销可以通过利用旨在减少训练DNN模型的内存占用的先验工作进一步减少[33,34]。
3.4 Caching
P3对图结构和特性的独立分区允许使用一个简单的缓存方案，可以减少已经最小的通信开销。这是基于观察到的，根据图和特征的大小，图或特征可能容纳比可用的机器更少的机器。默认情况下，特性和图是在所有可用的机器上进行分区而不复制的。然而，当主机内存可用时，P3使用一种简单的贪婪方法，通过使用用户定义的设置在多台机器上缓存图和/或特征的分区，来利用所有可用的空闲内存。在其当前状态下，我们只是进行缓存，尝试将输入放入最少数量的机器中，并在其他机器上创建分区的副本(缓存)。我们假设均质机器，这通常是DNN/GNN训练[35]中的标准。我们相信有机会设计一个更好的缓存方案，并计划在未来探索它。
3.5 P3 API
P3将其独立分区策略、流水线推拉并行和缓存封装在一个简单的API中，开发人员可以使用它来加速新的GNN架构。该API如表2所示，由以下六个函数组成:
- partition：是一个用户提供的复合函数，它独立地跨机器划分图形拓扑和输入特征。这一步对于平衡负载和减少通信至关重要。
- scatter： 使用在每条边上定义的用户提供的消息函数，通过将边缘表示与源顶点和目标顶点的表示相结合来生成消息。
- gather：使用定义在每个顶点上的用户提供的交换和关联函数(例如和、平均值)，通过聚合传入的消息来计算邻域表示。
- transform：是一个用户提供的复合函数，定义在每个顶点上，通过应用零个或多个元素的神经网络操作s4(例如add)来生成部分表示，然后对顶点特征和聚合邻域表示进行最多一次非元素的神经网络操作(例如卷积)。
- sync：使用用户提供的算术操作在网络上累积部分表示(由transform API生成)。
- apply：是一个定义在每个顶点上的用户提供的复合函数，通过对顶点特征和输入表示应用零个或多个元素智能和非元素智能的神经网络操作来生成表示。
清单1概述了如何在P3中实现GraphSAGE[24]。使用我们的API，开发人员编写了正向函数-函数，从输入张量生成输出张量。生成的计算图(见§3.2.1)和在前一层中计算的表示(或如果第一层正在接受训练，则按特征维度划分的输入顶点特征)是正向函数的输入。对于GNN模型中的每一层，每个顶点首先通过在传入源顶点表示(参见scatter_udf)上应用elementwise mean(参见gather_udf)来聚合其邻域的表示。接下来，顶点的当前表示和聚合邻域表示通过一个完全连接的层提供，对元素进行求和(参见transform)，并通过非线性函数ReLU(参见apply)，该函数生成下一层使用的表示。如果这是最后一层，生成的表示将用作下游任务的顶点嵌入。
在训练第一层时，输入表示将沿着收缩(特征)维度进行划分，并均匀地分布在各个机器上，这将导致输出表示由需要同步的非元素操作符生成。值得注意的是，在不需要同步的情况下仍然可以应用基于元素的操作。因为transform为分区输入表示提供了一个完全连接层，作为非元素操作符，它的输出表示必须在应用其他下游操作符之前进行同步。Sync通过网络累积部分表示，并生成可由apply使用的输出表示。除第一层以外的所有层的输入表示都是按批维划分的，因此相应的输出表示不需要同步;因此，除了第一层，其他所有层都不需要同步。
4 Implementation
P3是在深度图库(DGL)[1]上实现的，[1]是一个流行的用于训练GNN模型的开源框架。P3使用DGL作为图传播引擎进行采样，使用消息传递原语和其他图相关操作进行邻域聚合，使用PyTorch作为神经网络执行运行时。我们以多种方式扩展DGL，以支持P3的基于流水线推拉的分布式GNN训练。首先，我们用一种支持独立划分图结构和特征的策略替换了DGL中的依赖图划分策略(特征与顶点和边共存)。我们重用DGL的k-hop图采样服务:对于每个小批，通过远程过程调用(RPC)向本地和远程采样器发出采样请求。这些采样器访问本地存储的图分区，并将采样的图拓扑和特征返回给训练器。与DGL不同，P3中的采样服务只返回采样后的图拓扑，不需要传输输入特征。其次，P3中的训练器使用流水线数据和模型并行性执行GNN模型。每个小批都被分配了一个唯一的标识符，并放在一个工作队列中。训练器过程从队列的前端选取小批样本及其相关数据，并应用神经网络操作。P3使用2正向，2向后的静态调度策略(§3.3)调度3个并发小批，以重叠通信和计算。在将小批的训练模式从模型切换到数据并行之前，必须同步部分激活。为此，我们扩展了DGL的KVStore来存储训练器计算的部分激活。KVStore使用RPC调用来协调跨机器的部分激活的移动，一旦同步，将累积的激活复制到设备内存中，并在工作队列中放置一个指向相关缓冲区的指针，与训练器进程共享。PyTorch的DistributedDataParallel模块在用于权重更新之前用于同步权重。
5 Evaluation
我们在几个真实的图上评估P3，并将其与DGL和ROC进行比较，这两个最先进的GNN框架支持分布式训练。总体而言，我们的结果表明:
- 与DGL相比，P3能够提高最高7×的性能，最高2.2×的ROC;它的好处随着图表的大小而增加。
- 我们发现P3可以实现与机器数量的优美伸缩，并且它与已知训练任务的已发布的精度结果相匹配。
- 我们的缓存和流水线技术提高了多达1.7×的性能，随着缓存机会的增加，收益也在增加。
实验设置: 我们所有的实验都是在一个有4个节点的GPU集群上进行的，每个节点都有一个12核Intel Xeon E5-2690v4 CPU, 441 GB RAM和4个NVIDIA Tesla P100 16gb GPU。同一节点上的图形处理器通过共享PCIe互连，节点间通过10gbps以太网接口互连。所有服务器都运行64位Ubuntu 16.04，附带CUDA库v10.2、DGL v0.5和PyTorch v1.6.0。
数据集与比较: 我们在表3中列出了我们在实验中使用的五个图表。前两个是来自OGB资源库[29]-OGB-Products[29](亚马逊产品联合采购网络)和OGB- papers[29](微软学术图[57]索引的论文之间的引用网络)的最大图表，在这里我们可以确保P3在各种任务中的正确性并验证与最佳报告结果[4]相比的准确性。后三种方法分别是uk -2006-05[10,11]、。uk域的快照、UK-Union[10,11]、相同的12个月时间感知图以及模拟社交网络的合成图Facebook[19]，它们被用来评估P3的可伸缩性。我们之所以选择这些，是因为缺乏专门用于GNN任务的如此大规模的开源数据集。这两个OGB图包含特性。对于剩下的三个，我们生成随机特征，确保标记节点的比例与我们在OGB数据集中观察到的保持一致。这些数据集代表了最近GNN研究评估中使用的一些最大的开源图表5。我们对DGL[1,61]和ROC[36]进行了比较，这是两种性能最好的支持分布式训练的开源GNN框架——据我们所知——在我们进行评估时。然而，由于在撰写本文时ROC所施加的限制，特别是它只支持全批训练和GCN实现的可用性，我们仅在可行的情况下与ROC进行比较，并在其余的实验中使用DGL。虽然DGL使用METIS分区器作为默认值，但我们将其更改为在所有计算中使用哈希分区，除非指定。这有两个原因。首先，哈希是唯一可以处理数据集中所有五个图而不会耗尽内存的分区器。其次，METIS会产生大量的计算开销，常常超过总训练时间(见§2)。
模型与度量: 我们使用四种不同的GNN模型:SGCN[63]、GCN[17,41]、GraphSAGE[24]和GA T[59]，按模型复杂性的递增顺序。这些模型代表了能够支持所有GNN任务的最先进的体系结构(§2)。除非另有说明，我们对所有任务使用标准的2层GNN模型。我们对所有GNN架构启用采样(除非另有说明)，因为它代表了我们的比较系统的最佳情况，也是扩展的标准方法之一。根据最近的文献[24]，我们采用的抽样方法是(25,10)邻域抽样，其中我们为节点的第一跳选择最多25个邻域，然后为这25个中的每一个选择最多10个邻域。GraphSAGE和GCN都使用32的隐藏大小。对于GA T模型，我们使用8个注意头。在我们所有的实验中，小批量尺寸都设置为1000。我们在适合输入的地方混合使用节点分类和链接预测任务。图分类任务通常是在一组小图上完成的，因此我们不包括这个任务。我们报告平均历元时间，这是在整个图上执行一次遍历所花费的时间，除非另有说明。我们注意到，要实现合理的准确性，训练任务需要数个100甚至1000个epoch。在评估模型所获得的精度的实验中，我们报告了达到最佳报告精度所需的总时间(在可用的地方)。对于评估不同配置(例如，特性)影响的实验，我们在大小(OGB-Paper)方面选择包数据集中的中间部分，在复杂性(GraphSAGE)方面选择GNN。
5.1 Overall Performance
我们首先展示总体结果。在这里，我们比较DGL和P3在每个epoch time。对于P3，我们禁用缓存(§3.4)，以便它使用与DGL相同的内存量进行公平的比较。注意，启用缓存只对P3有好处，我们将在本节后面介绍缓存的好处。我们在所有的图上训练所有的模型，并报告每个epoch的平均时间。结果如表4所示。
我们看到P3的性能全面优于DGL，加速范围从2.08×到5.43×。随着输入图大小的增加，好处也会增加。为了深入探究为什么P3能够获得如此优越的性能，我们将epoch time分解为它的组成部分:嵌入计算图创建时间(表示为DAG)、数据复制时间和计算时间(向前通过时间、向后通过时间和更新时间的总和)(§2)。显然，P3的独立分区策略和混合并行性显著减少了生成计算图的时间，从而占据了epoch time的主导地位。我们看到P3的数据复制和计算时间略有增加，因为推动图结构的需求，以及推动激活所需的额外CUDA调用相关的开销(§3)。我们提醒读者，在这个实验中P3的缓存/复制是禁用的，启用它将减少数据复制时间。然而，P3积极的流水线能够将正向传递的额外开销保持在最低水平。我们还注意到，随着模型复杂性的增加，计算图创建阶段在整个历元时间中的主导地位降低，因为向前和向后传递变得更加密集。
5.2 Impact of Sampling
在最后一个实验中，我们启用了主动采样，这是现有gnn用于实现可伸缩性和负载平衡的一种常见策略。然而，抽样会影响任务的准确性，而要达到最佳的准确性，需要确定周期的数量。此外，一些GNN架构可能不支持采样，或者需要更多的采样(与我们使用的(25,10)设置相比)。为了评估当底层任务不支持采样时P3的执行情况，我们通过禁用采样来重复这个实验。其他一切都保持不变。图7显示了结果。
如果没有抽样，我们注意到在我们的集群中无法训练最大的图(UKUnion和Facebook)。这是因为在DGL的情况下，计算图会耗尽内存，解决它的唯一方法是启用采样。此外，对于更复杂的模型(GA T)， DGL很难在所有数据集上进行训练。因此，我们不报告这两个大图和GAT的结果。尽管如此，我们注意到，与抽样情况相比，P3的效益有所提高，速度提高范围从6.45×到7.69×。这清楚地表明了跨网络只拖动图结构的好处。
5.3 Impact of Partitioning Strategy
在这里，我们研究了不同的划分策略如何影响训练时间。DGL默认只支持边切分区(使用METIS[38])，因此我们实现了四种不同的分区方案:hash(与P3使用的分区器相同)，RandomV ertexCut[22,23]和GRID[12,22]是点切分区器，3D(是[69]中提出的三维分区器)。我们用不同策略的划分训练DGL中的GraphSAGE模型，并与P3及其随机哈希分区器进行比较。我们在图8a中报告了平均epoch时间。
我们注意到P3的随机哈希分区优于所有方案，甚至是DGL (METIS)中最好的策略，P3的加速范围从1.7×(针对METIS)到3.85×(针对随机哈希)。RandomV ertexCut、GRID和3D分区器对于较大的图形会耗尽内存。唯一适用于Facebook图的分区方案是随机散列分区器，因此我们在这个实验中省略了它。人们可能很容易认为智能分区器(而不是散列分区器)可以使DGL受益。然而，由于两个原因，这是不正确的。首先，分区产生如图8b所示的预处理时间。我们看到METIS占用的时间最多，开销常常超过总培训时间。它也不能支持大型图。其他策略可能看起来合理，但图8c证明并非如此。该图显示了各种分区策略使用的内存。可以看出，顶点切割方案(RandomVertexCut, GRID, 3D)需要复制数据，因此需要大量的内存开销。相比之下，P3的独立分区策略不仅在内存和epoch时间方面优于DGL (METIS)中性能最好的策略，而且几乎不需要预处理成本
5.4 Impact of Layers
在这个实验中，我们评估了GNN中层数的影响。为此，我们选择GraphSAGE并创建模型的三个不同变体，每个变体具有不同数量的层，从2到4。然后使用DGL和P3训练模型。在这个实验中启用了采样，因为DGL即使在没有它的情况下，也无法在小的图上训练更深的模型(更多的层)。结果如图9所示。我们发现P3的收益随着层数的增加而增加，比DGL高出了6.07×。这是因为随着网络变得更深，计算图也会变大。此外，我们看到，随着网络变得更深入，与随机哈希分区相比，智能分区策略(METIS)的好处开始减少。这是因为现有的分区方案为第一跳邻域进行了优化。P3不受这两者的影响，因为它对图和特征的独立划分以及执行GNN时的混合并行性。
5.5 Impact of Features
为了评估特征大小对训练性能的影响，我们将OGB-Paper数据集的节点特征数量从16变化到512。由于数据集最初有128个特征，我们要么修剪它们，要么复制它们，以获得所需的特征数量。我们使用带有采样的GraphSAGE模型进行训练，并在图10中报告了平均epoch时间。
我们清楚地看到了P3基于混合并行执行的好处。DGL的性能随着特性数量的增加而下降。这是意料之中的，因为要创建计算图，DGL需要拉取特征，而特征越多，就会招致更多的网络流量。相比之下，由于P3只需要使用网络来获得激活，因此其性能的退化最小——epoch时间只有当特性的数量增加到32倍时才会翻倍。P3的收益比DGL高出4.77×。
5.6 Microbenchmarks
缓存的影响: 在这个实验中，我们评估了P3缓存的好处(§3.4)。如表4所示，我们使用GraphSAGE对四个图数据集进行训练，但在内存允许的情况下，将图的分区和特性缓存到多台机器上。有趣的是，对于某些图表来说，它可以在多个机器上复制结构(如UKUnion)，但不能在功能上复制，反之亦然(如Facebook)。这表明，独立划分结构和特性使得缓存成为可能，而这在其他情况下是不可能的(例如，DGL不能利用我们的缓存机制)。在这里，P3能够实现高达1.7倍的性能，并且随着缓存机会的增加，性能的提高也会增加。此外，缓存将P3相对于DGL的训练速度从3.6×(表4)扩展到5.23×(图)。
流水线的影响: 这里我们在P3(§3.3)中评估了流水线的好处。为此，我们使用P3在四个不同的数据集上训练GraphSAGE两次;首先启用管道，然后禁用它。图11显示管道有效地将大部分通信与计算重叠，P3能够多获得30-50%的收益。
GPU利用率: 图12描述了在DGL和P3的5秒窗口内，在OGB-Product数据集上训练GraphSAGE模型时GPU利用率的峰值。这里，使用nvidia-smi[3]实用程序每50毫秒测量一次GPU利用率。我们观察到DGL和P3的峰值GPU利用率是相似的(≈28%)。这是由于GNN模型的性质，它们执行稀疏计算，无法在所有核上利用峰值硬件效率6。然而，我们看到，在这个实验期间，DGL能够使GPU保持忙碌状态——让众多GPU核心中的至少一个保持活动状态——只有约20%的时间。剩下的≈80%，GPU资源被网络阻塞，利用率降为零。另一方面，P3能够保持GPU的繁忙度≈85%的时间。因此，它能够在5秒钟的时间内完成4个阶段的训练，而DGL只需要1个阶段。
5.7 P3’s Scaling Characteristics
在这里，我们评估了P3的强缩放特性。我们再次选择OGB-Paper数据集并在其上训练GraphSAGE模型。为了理解缩放特性，我们通过改变P3和DGL使用的gpu的数量来改变机器的数量。我们在图13中报告平均吞吐量(每秒处理的样本数量)。
P3表现出近似线性的缩放特征;当机器数量(也就是gpu数量)翻倍时，它的吞吐量就会翻倍。相比之下，DGL的吞吐量随着机器数量的增加几乎保持不变。这主要是因为DGL中的GPU资源受到网络数据移动的限制，而P3通过提出的技术可以有效地消除这种开销。随着机器数量的持续增长，我们预计P3将表现出更不理想的伸缩性。在P3中，每台机器都需要从所有其他机器中获取激活，这与机器数量成线性增长，导致数据移动增加，这可能会对性能产生不利影响。这是模型并行的一个基本问题，因此现有的缓解技术直接适用于P3。
5.8 Accuracy
在这里，我们评估我们的P3方法的正确性。为此，我们用采样训练GraphSAGE模型，但这次是在OBG-product图(我们数据集中最小的图)上。该图报告的最佳准确性约为78.2%，使用约50个周期[4]。由于缺乏发表的大型图的准确性结果，我们无法在数据集中对大型图重复这个实验。我们在这个数据集上同时运行DGL和P3，直到我们获得相同的精度。我们在图14中显示了结果。我们注意到，股票DGL和P3都实现了相同的迭代精度，在51次迭代结束时，它们都实现了大约76.2%的精度。P3能够在61.65秒内完成这个训练，而DGL在使用输入的随机散列分区时需要236.37秒，在使用METIS分区器时需要96.3秒。而METIS划分图的时间为35.09秒，总训练时间为126.39秒。这个实验表明，P3不仅能够复制与DGL相同的精度，从而确保其正确性，而且即使对于最小的图，它也能够比DGL更快地完成训练。
5.9 Comparison with ROC
接下来我们将与ROC进行比较。由于ROC不支持采样，我们在所有系统上关闭采样。在评估时，ROC只支持全批训练，并且只有GCN的实现可用，因此我们将其作为本次实验的默认值。我们在OGB-Paper和UK-2006-05图上运行了50次2层GCN。ROC使用在线分区器，该分区器在GNN执行期间依赖图的移动部分。因此，我们跳过最初的几个epoch，以允许ROC完成其数据移动，并测量之后的平均epoch时间。实验结果如图16所示。
ROC由于其高度优化的图形引擎，能够比DGL更快地处理这两个输入图形。然而，P3能够超越ROC，完成epoch高达2.2倍的速度。我们还注意到P3的好处随着输入图的大小而增加。这是由于P3和ROC在设计上的根本差异。虽然ROC的在线分区器能够基于访问模式获得高级分区，但在训练GNN模型时，它仍然依赖于移动特征。随着图大小的增加，这将导致更多的特征在网络中传输。相比之下，P3的设计试图将瓶颈层的计算分散到整个集群中，并完全避免特征移动。此外，随着层数的增加，ROC(和DGL)将需要以指数形式移动更多的特征，从而导致网络开销的增加。
在阅读这一结果的同时，我们希望提醒读者一些注意事项。我们的评估使用10 Gbps以太网互连，这有利于导致较少数据移动的技术。因此，由于ROC(和DGL)的特征移动而引起的一些观察到的网络开销可以通过使用更快的互连(如InfiniBand)最小化。此外，与ROC不同，P3和DGL需要训练数据(图拓扑、特征、模型参数和激活)来适应设备内存，如果不这样做，就会在训练过程中导致内存不足错误。另一方面，ROC只要求训练数据适合DRAM，并利用基于成本的内存管理器在设备内存和DRAM之间有选择地移动张量，这可能会影响性能。
5.10 P3 Shortcomings
最后，我们介绍了P3没有带来好处的情况。回想一下，P3所做的基本假设是gnn中的隐藏维度通常更小，这导致激活明显小于特征。当这个假设被违反时，P3开始失去它的好处，甚至可能导致性能损失。
为了说明这一点，我们在这个实验中评估了隐藏维度的影响。我们在OGBProduct数据集上训练GraphSAGE，并将特性的数量固定为100。对于不同数量的隐藏维度，我们记录DGL和P3在启用和不启用采样时的平均历元时间。图15显示了结果。正如我们所料，随着隐藏维度(从而增加激活的大小)数量的增加，P3的好处会减少。一旦隐藏维度大小接近特征大小，P3就会严格地比DGL差。我们注意到，由于模型并行性，P3还会产生额外的开销，因此确切的过渡点取决于图的特征。动态地确定P3是否在给定的场景中提供好处，并进行适当的切换，这是我们计划的未来工作的一部分。
6 Related Work
Graph Processing Systems 已有文献提出了几种提供迭代消息传递抽象的大规模图处理系统，以有效利用cpu[12,21 - 23,31,32,48,50]和gpu[39,62]。这些系统已经被证明能够扩展到巨大的图，以万亿条边为数量级[15]。然而，这些主要集中在图分析和挖掘，缺乏对GNN训练至关重要的功能的支持，如自动区分和数据流编程。
Deep Learning Frameworks 如PyTorch [5]， TensorFlow[6]和MXNet[2]通常使用数据并行[44]和模型并行[14,16]来加速并行和分布式DNN训练。为了进一步扩展，最近的一些研究提出将数据和/或模型并行与流水线、操作级分区和激活压缩结合起来[30,42,49,54]。GPipe[30]和PipeDream[49]旨在缓解模型并行的低gpu利用率问题。两者都允许跨工作者划分模型，允许所有工作者并发地处理不同的输入，确保更好的资源利用。GPipe维护一个权重版本，但需要定期的管道刷新以一致地更新权重，从而限制了总体吞吐量。PipeDream保持多个权重版本以确保一致性，从而以额外的内存开销为代价避免周期性刷新。之前的工作[37,60]甚至展示了如何使用引导随机搜索自动找到一个设置的快速并行化策略。
GNN Frameworks 受训练GNN模型日益流行的驱动，一些专门框架[1,20,36,45,47,65,68]和加速器[40]被提出。它们可以被分为两大类:一类是用神经网络操作扩展现有图处理系统的系统[36,65,68]，另一类是扩展现有基于张量的深度学习框架以支持图传播操作的系统[1,20,45,47]。两者都使用图分区作为在单台机器或多台机器上的多个cpu和/或gpu之间伸缩GNN训练的手段。有些框架，如AliGraph[65]和AGL[68]，只支持使用CPU进行训练，而另一些框架[1,20,36,45,47]则支持在gpu上执行训练，并使用CPU内存来保存图形分区和在gpu之间交换数据。
PyTorch-Geometric[20]和DGL[1]用消息传递接口包装了现有的深度学习框架。他们专注于设计一个面向图形的界面来进行改进GNN可编程性，并借鉴了传统图处理系统和DNN框架的优化原理。然而，正如我们所展示的，它们未能有效地利用gnn工作负载的独特环境和
ROC[36]是一个最新的分布式多gpu GNN训练系统，它与P3有着相同的目标，但提出了一种截然不同的方法。它探索了使用线性回归模型作为一个复杂的在线分区器，这是与GNN训练工作量共同学习的。与P3不同的是，尽管有复杂的分区器，ROC仍然必须在网络上移动图结构和特征，正如我们所展示的那样，这会导致较高的开销。
PaGraph[45]和NeuGraph[47]是用于训练gnn的单机多gpu框架。PaGraph报告称数据拷贝是一个主要的瓶颈，并专注于通过缓存最常访问的顶点的特性来减少CPU和GPU之间的数据移动。另一方面，NeuGraph使用分区和流调度程序来更好地重叠数据复制和计算。然而，在分布式多gpu设置中，我们观察到网络通信是一个主要的瓶颈，它占训练时间的很大一部分，高达80%，而数据复制时间只占5%。我们注意到，在PaGraph和NeuGraph中提出的技术与我们的工作是垂直的，如果应用，只能使P3受益。
除了上述系统端优化以缓解可伸缩性瓶颈外，还提出了基于节点的[24]、基于层的[72]和基于子图的[13]采样技术。它们与P3正交并兼容。
7 Conclusion
在本文中，我们研究了分布式GNN训练中的可伸缩性问题及其处理大型输入图的能力。我们发现，网络通信占了培训时间的很大一部分，由于这个原因，gpu的利用率严重不足。我们提出了P3，一个用于分布式GNN训练的系统，它通过采用一种全新的方法克服了可伸缩性的挑战。P3实际上消除了对图的任何智能分区，并提出对输入图和特征进行独立分区。然后，它通过采用一种新颖的管道推拉执行策略，结合了层内模型并行和数据并行，并使用简单的缓存机制进一步减少了开销，从而完全避免了在网络上通信(通常是巨大的)特性。P3在一个简单的API中为最终用户公开了它的优化。在我们的评估中，P3的性能明显优于现有的最先进的GNN框架，最高可达7倍。
Acknowledgements
We thank our shepherd, Chuanxiong Guo, all the anonymousOSDI reviewers and Ramachandran Ramjee for the invaluablefeedback that improved this work. We also thank the contributors and maintainers of PyTorch and DGL frameworks.
