神经网络|文献阅读（03）Computing Graph Neural Networks: A Survey from Algorithms to Accelerators 卷积神经网络|深度学习

作者：SERGI ABADAL, AKSHAY JAIN, ROBERT GUIRADO, JORGE LóPEZ-ALONSO, and EDUARDALARCóN
目录
文章脉络：
缩写&&引用：
1 INTRODUCTION：
(1)本质：
(2)难点：
(3)目前所作的尝试：
（4）关于gnns算法及其应用的文献：
2.GNNs符号以及一般结构
2.1 Notation
2.2 General Structure
2.3 Computing GNN Inference
2.4 Computing GNN Training （计算机 gnn 训练）
3 THE EVOLUTION OF THE GNN FIELD（gnn领域的发展）
3.1 A General Perspective
3.2 An Algorithm Perspective（算法发展）
GNN algorithm classifications：算法分类。如下图所示：
Comprehensive frameworks（综合框架）
Programming models（编程模型）
4 THE REVOLUTION OF GNN ACCELERATION（GNN加速的革命）
4.1 软件框架和加速器
4.2硬件加速器
4.3 Discussion
5 . GNN ACCELERATION: THE VISION（GNN加速:视觉）
5.1 Software-Hardware Co-Design（软硬件合作设计）
5.2 Graph Awareness（图形感知）
5.3 Communication-Centric Design（以通信为中心的设计）
6 CONCLUSION

文章脉络：本文是关于图神经网络的一篇综述。内容主要包括：图神经网络的概念；图神经网络的发展以及演变；关于图神经网络的加速器部分；最后是关于图神经网络在加速器中的架构设计，重点在通信中的作用。文章的主要脉络如下图所示。

文章图片

缩写&&引用： GNNS:Graph Neural Networks 图神经网络
CCS:code compaser studio 集成开发环境
ML:machine learning 机器学习
MLP：多层感知机
RL:represent learning 表示学习
DL:deep learning 深度学习
DNNS:Deep Neural Networks 深度神经网络
CNNS:Convolutional Neural Networks卷积神经网络
RNNS:Recursive Neural Networks 循环神经网络
KG：知识图谱
WL：Weisfeiler-Lehman 图同构测试
DNN:深度神经网络
GCN:图卷积神经网络
GIN:图同构神经网络
Graph SAGE：图神经网络的一种算法。GS包含采样和聚合 (Sample and aggregate)，首先使用节点之间连接信息，对邻居进行采样，然后通过多层聚合函数不断地将相邻节点的信息融合在一起。
LSTM：长短期记忆网络
GAT：图注意力网络
Highway GCN：高速路GCN，它像高速路网络一样使用逐层门限。
GRN：图循环网络
GRU：循环神经网络
RELU：线性整流函数，是神经网络中常用的激活函数
SGC ：GCN的变体。通过消除 GCN 层间的非线性，将非线性的 GCN 转变为简单的线性模型，减小了模型复杂度，在很多任务上比 GCN 以及其他 GNN 模型更加高效。
commtNet：多智能体通讯网络
GGNN：门控图神经网络
GCMC：图卷积矩阵补全
PaddlePaddle：百度深度学习平台
GEMM：通用矩阵乘

1 INTRODUCTION：

In essence, GNNs adapt their structure to that of an input graph and, through an iterative process of aggregation of information across vertices, capture the complex dependences ofthe underlying system

(1)本质： gnns 将其结构调整为输入图的结构，并通过跨顶点的信息聚合的迭代过程，来获得底层系统的复杂依赖关系。

(i) support both dense and extremely sparse operations (ii) adapt the computation to the specific GNN algorithm variant and the structure of the graph at hand (iii) scale to very large graphs to realize its potential in certain applications.

(2)难点： gnns在目前来说还是比较新颖的，很多部分还未得到有效的利用，在gnns的计算方面主要有以下几个方面的挑战： (i)支持稠密和极其稀疏的操作
(ii)使计算适应特定的 gnn 算法变量和目前的图的结构
(iii)规模到非常大的图，以实现其在某些应用中的潜力。
(3)目前所作的尝试：

Even though advances in sparse/irregular tensor processing [ 34 ] and graph processing [ 63 ,154 ] may prove useful in accelerating GNNs, addressing their unique computing challengesrequires more specialized proposals. Some attempts have been done from a software perspective, i.e. adapting the GNN operations to better match the capabilities of CPUs or GPUs [ 106 ,144 ,155 ]; and from a hardware perspective, i.e. designing custom processors tailored to the demands of GNNs [ 7 ,53 ,103 ,164 ]. However, recent surveys and reviews[ 11 ,16 ,19 ,66 ,91 ,160 ,181 ,185 ] lack of comprehensive analysis of such advances.

尽管稀疏/不规则张量处理和图形处理的进步可能证明在加速 gnns 方面是有用的，但是解决它们独特的计算挑战需要更加专业化的建议。
为了解决这一挑战，在软件以及硬件方面已经做了一些尝试。比如在软件方面使得gnns更好的匹配cpu以及gpu；硬件方面制定处理器来满足gnns。
（4）关于gnns算法及其应用的文献：

神经网络|文献阅读（03）Computing Graph Neural Networks: A Survey from Algorithms to Accelerators

文章图片

2.GNNs符号以及一般结构 2.1 Notation

文章图片

聚合函数和组合函数的符号的差异点：

文章图片

2.2 General Structure

文章图片

gnns的一般结构如上图所示，主要分为以下三个步骤：

(1)Pre-processing:this is an initial and optional step generally done offline that can transform the input feature vectors and graph structure representation through a precoding process. This may be used to sample the graph, to re-order the graph towards reducing the algorithm complexity and its processing, or to encode the feature vectors, among others[ 23 ,28 ,65 ,77 ,141 ,176 ,181 ].(2)Iterative updates:After the pre-processing, the feature vectors of each edge and vertex are updated via the aggregate–combine functions iteratively. To update the edges, attributes from the edge itself, the connected vertices, and the graph are aggregated into a single set andcombined to yield a new edge feature vector. Similarly, updating the vertices implies aggregating the feature vectors from neighboring vertices ( )andcombining themto obtain a new feature vector. Note that each step orlayer updates each edge and vertex with information coming from neighbours located at a single hop. Thus, the iterative process allows to gradually account for relations of increasingly distant nodes and edges. Additionally, in each successive layer, the graph may be coarsened by means of pooling [ 168 ] or the neighbourhood set changed by means of layer sampling [ 65 ].(3)Decoding or readout:if the graph has a global feature vector, it is updated once after the edge and node updates are completed. The final output is either an edge/node embedding, which is a low dimensional feature vector that represents edge- or node specific information, or a graph embedding summarizing the information about the entire output graph instead.

第一步：预处理：可以通过预编码过程转换输入特征向量和图形结构表示。可以用来采样图形，重新排序图形，来减少算法的复杂性和处理，或重新编码特征向量。
第二步：迭代更新：经过预处理后，通过聚合-组合函数迭代更新每条边和顶点的特征向量。更新边，要从边本身的属性，连接的顶点，图来聚合成一个单一的集合，并组合起来产生一个新的边特征向量。同样，对顶点的更新，聚合了相邻顶点的特征向量，并将它们合并为一个新的特征向量。
第三步：解码或读出: 如果图有全局特征向量，则在边和节点更新完成后更新一次。最终的输出要么是边/节点嵌入，这是一个表示边或节点特定信息的低维特征向量，要么是一个图，总结整个输出图的信息。
gnns结构的特性以及可优化部分：
最广泛使用的 gnn 算法有1-5个图层，过多的图层通常会导致特征过平滑、渐变消失或过拟合的问题。一些作品提出了缓解这些问题的技术，并能够使得深层 gnns多达100层，但这些建议仍处于初级阶段。
gnn结构中的聚合的大小取决于顶点和边的数量(从数千到数十亿) ，而组合的大小取决于特征向量的长度(从数十个特征到数万个特征)。边和顶点的聚合和组合函数是关键的设计决策，因为它们决定 gnn 的表达能力。
gnns的基本结构可以通过采样和池操作来补充，这些操作有助于降低 gnns的计算复杂性，以及/或者通过支持动态图来扩充。采样是指对每个节点的图或邻域集进行剪枝，用于限制或协调聚合过程中的资源和运行时间，而池化则是指从一层到下一层的图的粗化，从而减少聚合和组合中处理的节点数量。gnns结构为了增加对动态图的支持，动态图的结构和输入特征向量可能随着时间的推移而变化，通常使用递归单元来适应每个时间步的权重矩阵。
总而言之，我们可以把 gnns 理解为一个神经网络的集合，在图的连通性上运行。在每一层的范围内，我们有多达两个神经网络与可学习的权重，分别确定组合的边和顶点。在整个 gnn 的范围内，我们有一个具有可学权重的神经网络来决定全局更新。
2.3 Computing GNN Inference

文章图片

边的聚合：取得边前一层本身的特征以及前一层顶点的特征得到当前层的聚合特征。
边的组合：将当前层计算得出的边的聚合特征作为输入得到当前层的组合函数。
点的聚合：同样地，取前一层的相邻顶点的聚合特征得到当前层的聚合特征。
点的组合：取当前层的聚合特征作为输入得到当前层的组合函数。
算法1应用条件：（1）不受节点和边的排列的影响；
（2）与输入的节点数量无关；
这代表函数可以并行的应用到同一层的所有点和边上；如果聚合函数是线性的，则组合函数和聚合函数的计算可以进行交换。在计算下一层前所有的边节点要计算完毕。

文章图片

表中对消息传递网络和一般的图神经网络进行了等价性比较，比如把层看作时间，聚合函数比作M（），组合函数看作U（）。
H(l)特征矩阵(l层)，A邻接矩阵，W(l)顶点组合权重矩阵。所以l+1层的特征矩阵为：

文章图片

2.4 Computing GNN Training （计算机 gnn 训练）

文章图片

Y为损失函数对权重的梯度，其中G为误差传播到第l层的特征矩阵

文章图片

先计算损失函数相对于权重的梯度，在计算每个顶点的特征向量偏导，最终更新每一层的权重。

文章图片

3 THE EVOLUTION OF THE GNN FIELD（gnn领域的发展）这一部分主要阐述：
1、gnn计算方面还处于早起上升阶段
2、gnns包含各种各样的算法。
3.1 A General Perspective gnns相关文献主题可分为四类：1数学2应用3计算4算法。
文献分类：gnn 建模、 gnn 应用、 gnn 复杂度、 gnn 算法、 gnn 加速器、 gnn hw/sw 需求和 gnn 数据流。
下表就可以看出各个分类相关论文的数量的百分比，可以看出只有一小部分事和gnn计算相关的，主要原因是因为gnn还在发展阶段，所以在计算方面并不深入。

文章图片

从下图得出的结论有：

文章图片

(i) The categories related to computing are small yet well-connected to the theoretical side of GNNs, corroborating
our earlier observation from Table 5.
(ii) The algorithms sub-field is large as many papers have appeared implementing multiple variants in the heteroge-
neous group of methods that GNN is. We review the evolution of GNN algorithms later in Section 3.2.
(iii) The applications sub-field is large but sparsely connected internally, which means that application papers are
generally not aware of other applications, unless reusing some specific common mechanism. This may be due to
the wide variety of application fields for GNNs, ranging from social networks to chemistry, computer networks,
or even material science as analyzed in previous sections.
(iv) The algorithm and application categories have a strong inter-connectivity, as each application paper shall at
least mention the algorithms used to implement the proposed system.
(v) The connection from application papers to computing papers is weak. This may be due to the relative immaturity
of the GNN computing field and this may change in upcoming years, especially if applications clearly benefiting
from specialized accelerators arise (akin to the appearance of CNN accelerators for computer vision).

1.计算类别很少但是和理论联系很紧密
2.算法的子域很大
3.应用方面的论文很多，但是之间的联系不是很紧密。主要原因是应用的范围很广
4.算法和应用之间的论文联系的很紧密。
5.应用和计算方面的联系少。
gnns在时间上的发展：
2005年，第一次开始关于gnns的相关工作，但之后gnn发展缓慢，主要原因由于缺少关键的应用以及cnn和rnn的普及度不高。
2016年，rnns和cnns发展成熟，gnn发展迎来大爆发，同时引入卷积神经网络，消息传递模型，量子化学应用。
2017年，开始gnn计算方面的研究。
基于以上分析，我们可以得出gnns加速器的设计、以及开发领域正在兴起。
3.2 An Algorithm Perspective（算法发展）本节主要是总结图核到现代GNNs算法的发展进程。
Pre-GNN techniques：图神经网络之前的技术。在gnns之前在低维空间进行浓缩信息来适应ml算法。例如：GKs算法，gks算法主要提取多个图层嵌入后，在进行比较分类（可以理解为测量图相似度的函数，主要学习图的拓扑结构在进行分类）。gks和gnns相比较，gks更容易训练，因为gks的超参数更少，这是由于在进行图嵌入的时候容易损失一些潜在的信息，这会限制gks的性能。gks需要进行手工设置特征映射，而gnns不需要设置，因为gnns保留了图固有结构。
GNN algorithm classifications：算法分类。如下图所示：

文章图片

循环神经网络模型：使用循环单位作为组合函数（scarselli）；在不经过边变化的简单聚合上操作( commnet）; 使用门控循环单元作为更新函数来改善收敛性（门控图神经网络gg-nn）。
卷积神经网络：分为谱神经网络和空间神经网络。谱神经网络，基于谱图理论，利用特征值分解和滤波等图形信号处理技术，建立了基于谱的模型。但是谱神经网络的计算代价过大，这是由于它要考虑整个图的结构；空间神经网络，只需要对来自邻近顶点的特性进行卷积聚集。在计算上更加实惠、灵活和可伸缩。
时空神经网络：结合使用卷积的空间方法和循环的时间方法。（门控图卷积网络g-gcn）
基于空间的卷积 GNN 由于其灵活性和可扩展性，成为最受欢迎的模型。基本算法使用均值函数作为聚合，有时也会考虑相邻的程度，之后会出现许多变体。

一种简化操作就是采样，另一个简化操作是区分池（DiffPool ）的差异合用，它形成分层集群，以便后面的层在更粗糙的图上运行。

GraphSAGE （GraphSAGE是为了学习一种节点表示方法，即如何通过从一个顶点的局部邻居采样并聚合顶点特征，而不是为每个顶点训练单独的embedding（嵌入））在更新函数中结合了来自前几层的自节点特征信息，并开创了 GNN 中采样的概念，以降低聚合的计算成本。

FastGCN （将图卷积操作解释为的embedding函数在概率度量下的积分变换）也使用了采样思想并集成了其他策略来加速计算，例如使用蒙特卡罗采样评估积分公式。

图同构网络 (如果图G1,G2G1,G2顶点和边数量相同，且边（具有方向性，即有向图）的连接性相同，这两个图定义为同构GIN)证明了 gnn 获取最大表达能力所需的条件图的结构是模拟 WL检验。特殊性在于图形输出特征向量，该特征向量是通过拼接各层的读出向量获得的。

图注意力网络 (GAT) 多用于自然语言处理 (NLP)，以及受欢迎的转换方法。 GAT 通过具有可学习权重的节点之间的成对函数更新节点特征，这允许使用描述边缘效用的学习注意机制进行操作。

图自动编码器 (GAE) ：将图转换为编码，随后可以将其扩展以生成结构与原始图（即解码）接近的新图。这些技术在图域中的独特之处在于 GCN （图卷积神经网络）可用于在编码过程中生成低维向量。 GAE 也通常使用对抗技术进行训练，从而产生了图对抗网络，例如 NetRA 。
GNN 可以与强化学习相结合：产生新颖的图学习技术。例如，MolGAN 生成具有特定最终目标的分子图。MINERVA，其中强化学习有助于预测 KG 推理路径中的下一个节点。

Comprehensive frameworks（综合框架）

消息传递方案（最受欢迎的方案之一）其操作和描述适用于学习分子指纹的卷积网络、GCN 分类方法、用于学习关系和特征的交互式网络，或者还有不同风格的门控 GNN。
非局部神经网络（NLNN），旨在统一包括 GAT 在内的各种注意力方法。这些通常不包括边缘的特征或聚合，而是仅涉及节点之间的成对标量注意力权重。

应用于节点、边或完整图的更新函数被视为不同的块。这些块中的几个块的组合或重复产生了文献中发现的不同类型的 GNN。Chami提出一个编码器-解码器模型来表达不同的图嵌入、图正则化、图自动编码器和 GNN 技术。
Programming models（编程模型）
一些编程抽象被认为支持任何 GNN 中所有可能的操作，通常与聚合组合模型兼容。当聚合或组合操作不适合矩阵乘法符号而无法使用矩阵乘法符号时，这些模型很有用，或者因为邻接矩阵非常稀疏并建议使用其他表示方式例如压缩稀疏行或列。
大多数现代库都隐含地遵循了SAGA-NN模型，该模型的工作方法如下：

Scatter 通过节点的边发送节点的特征向量
ApplyEdge 与散点向量进行边合并。
Gather 允许每个顶点聚合来自其邻边的向量
ApplyVertex 在收集操作后执行顶点组合。

另一个提出的模型是 Gather-Reduce-Transform-Activate (GReTA) 模型。在这种模型中以上四个操作是用户定义的，可以修改以实现任何 GNN。

聚合Aggregation 是通过gather和reduce进行的，这使得每个顶点都可以从它们的邻居那里获取特征并将它们累积成一个单一的值。
然后通过转换和激活transform and activate执行组合Combination，这通常对聚合数据进行矩阵乘法和非线性激活。

最近，Wang 等人提出了 NeighborSelection-Aggregation-Update 模型，该模型为更传统的聚合更新 [150] 添加了一个灵活的邻居选择层。
4 THE REVOLUTION OF GNN ACCELERATION（GNN加速的革命） GNN加速器高速发展的同时也面临了很多方面的挑战：

(i) The existence of multiple GNN variants, which may include edge, vertex, and graph-wide updates
(ii) The existence of multiple GNN variants, which may include edge, vertex, and graph-wide updates
(iii) A unique combination of computing characteristics from deep learning and graph processing, leading to alternate execution patterns.
(iv) A wide pool of applications with not only different graph characteristics, but also different performance targets.

(i) 存在多个 GNN 变体（变体如表6所示），其中包括边、顶点和图范围的更新

文章图片

(ii) 计算对输入图特征的依赖性
(iii) 深度学习和图形处理的计算特性的独特组合，导致了不同的执行模式。
(iv) 大量的应用程序不仅具有不同的图形特征，而且具有不同的性能目标。
下面会分为硬件和软件两部分来讲解在面对GNN的这些挑战时做出的研究。
4.1 软件框架和加速器 DNN 库和图处理框架效率低下，原因是在GNN 的交替计算阶段。 DNN 库擅长加速顶点和边内的组合操作，但不擅长聚合。相反，图形处理库在遍历图形时在管理不规则的内存访问方面做得很好。但这些操作在 GNN 中并不是这样。为了弥补这一差距，最近的工作已经开始研究如何调整库以（i）提供易于编程的接口来实现多个 GNN 变体（ii）在广泛的 GPU 硬件中有效地处理各种潜在的稀疏 GNN 操作（iii ) 将计算扩展到大规模图形和多个 GPU。

Name	Main Features	Evaluation
Name	Main Features	Algorithms	Datasets	Baselines
PyG	?建立在 PyTorch上，并被广泛使用 ?可提供多种示例代码。 ?使用分散-聚集内核+节点/边并行 ?在GPU中进行评估。与BigGraph[94]兼容，可缩放	GCN, GAT, SGC, GS, GIN, etc...	Cora, CiteSeer, PubMed, MUTAG, Proteins, Collab, IMDB, Reddit	DGL
DGL （Deep Graph Library）	?兼容TF、PyTorch和MXNet ?深入的文档和支持、教程。 ?采用矩阵乘法方法并利用 GPU 或 TPU 的专用内核。 ?为分布式计算增加了DistDGL[184]。 ?该库定义了三个函数：用于边缘聚合和更新的消息以及用于节点处聚合和组合的减少和更新	GCN, GAT, SGC, GS, GIN, R-GCN, GCMC	Reddit, OGB (Arxiv, Protein, Product, Citation, PPA), Movielens	PyG
NeuGraph	?多个图形处理器的实施和评估。 ?四个功能模型可以在边缘和节点处进行更新。该模型基于用于边聚合的 Scatter、用于边组合的 ApplyEdge、用于节点聚合的 Gather 和用于节点组合的 ApplyVertex 函数实现了一个编程模型 SAGA-NN。 ?优化分区、调度、流水线、传输。 ?基于 TF 构建，未开源。	GCN, CommNet, GG-NN	Pubmed, Blog, Reddit, Enwiki, Amazon	DGL, TF
AliGraph（AliGraph由阿里巴巴集团开发并以graph-learn的名义开源，是一个建立在TF之上的GNN框架）	? 针对大规模图形和分布式系统。 ? 强调分布式存储和分区 ? 仅适用于异构和动态 GNN，以及庞大的数据集（最多 483M 边，6.5B 边）。?建立在 TF 之上。	GS, six in-house algorithms	Amazon, Taobao	N/A
FlexGraph（阿里巴巴集团还领导了 FlexGraph的开发，这是一种用于 GNN 训练的分布式框架，其独特之处在于对邻域的灵活定义和分层聚合方案。）	? 使用NAU 编程模型进行灵活聚合。 ? 具有动态稀疏-密集逻辑的分层聚合。【神经网络\|文献阅读（03）Computing Graph Neural Networks: A Survey from Algorithms to Accelerators】? 支持分布式计算，1500核系统测试。	GCN, PinSage, MAGNN	Reddit, FB91, Twitter, IMDB	PyG, DGL, DistDGL, Euler
AGL	? 以可扩展性、容错性和完整性为目标。 ? 使用 MapReduce 进行扩展，在 32000 核系统中测试。 ? 该框架具有三个模块：一个用于创建可以并行处理的独立邻域，一个用于优化训练，一个用于图的切片和推理计算。	GCN, GS, GAT	Cora, PPI, UUG,	PyG, DGL
ROC	? 在FlexFlow [78] 之上实施。 ? 优化：动态分区、内存管理。 ? 通过NVLink 使用单个和多个GPU 进行评估。	GCN, GS, CommNet, GIN, FastGCN	Pubmed, PPI, Reddit, Amazon	TF, DGL, PyG, NeuGraph
GNNAdvisor	? 图形信息（度数、特征大小、社区）的独特运行时分析以指导 GPU 处理 ? 与单个 GPU 中的类似框架进行广泛比较	GCN, GIN	CiteSeer, Cora, Pubmed, PPI, Prot, Yeast, DD,twit, SW620H, amazon, artist	DGL, PyG, GunRock, NeuGraph
PCGCN	? 由节点度的幂律分布驱动。 ? 优化分区以生成密集矩阵。 ? 双执行模式取决于每个分区的稀疏性。 ? 建立在TF 之上，在单个GPU 中进行评估。	GCN	Pubmed, Blog, Youtube, C1000-9, MANN-a81, Reddit, synthetic (RMAT)	TF, DGL, PyG
HAG	? 通过融合节点去除聚合中的冗余和。 ? 运行时算法仅在预测有益时融合节点。 ? 对运算缩减的影响与硬件无关，但对执行速度的影响则无关。	GCN, GIN, SGC	BZR, PPI, Reddit, IMDB, COLLAB	N/A
FeatGraph	? 用于聚合和组合的优化 matmul 内核。 ? 用户定义的组合函数和优化。	GCN, GS, GAT	OGB (Proteins), Reedit, sythetic graphs	GunRock
G3	? 将图形处理框架和 GNN 结合在一起。 ? 通过 C/C++ 提供 API 以简化编程。 ? 使用 GunRock [154] 提供 GPU 运行时优化。	GCN, SGC	PubMed, Reddit	PyG, TF
GReTA	? 使用用户定义的函数（GReTA 由四个用户定义的函数组成：Gather 和 Reduce 描述聚合，Transform 和 Activate 描述组合。这些函数具有一定的灵活性以适应不同的 GNN 类型。）进行编程抽象，类似于 SAGA，针对加速器和任何 GNN 变体。 ? 基于ASIC 中的GRIP（见表8）进行评估。	GCN, GS, G-GCN, GIN	Youtube, Livejournal, Pokec, Reddit	N/A
Paddle Graph Learning (PGL)（由百度研究院开发，是一个基于 PaddlePaddle百度深度学习平台的图学习框架）	? 支持异构图中基于步行和消息传递的模型。 ? 集成一个支持许多 GNN 模型的模型库，以促进采用，以及对分布式计算的支持。

最后补充一个Tripathy et al。在本文中，作者比较了在多个GPU集群中划分和分配GNN的多种并行化算法，即1D、1.5D、2D和3D算法，并对这些设置的GPU间通信和内存需求之间的权衡进行了建模分析和训练。该模型采用一个大型邻接矩阵，并根据算法将其分解为固定数量的进程。然后，对有效操作的数量和结果进行分析，以便在gpu之间进行沟通。它们在PyG上的实现显示出很有希望的可伸缩性，并指定1.5-D算法作为一种有希望的、平衡的替代方法，尽管最佳算法取决于输入图的特征。
4.2硬件加速器

Name	Main Features	Evaluation
Name	Main Features	Algorithms	Datasets	Baselines
EnGN	?统一的架构，密集的硬件，单一的数据流，可推广到许多GNN变体。 ?通过 Ring-Edge Reduction(RER)聚合。 ?优化:边缘排序，度感知的顶点缓存，调度。	GCN, GS, GG-NN, GRN, R-GCN	Cora, PubMed, Nell, Reddit, Enwiki, Amazon, synthetic (RMAT), AIFB, MUTAG, BGS, AM	CPU-DGL, GPU-DGL, CPU-PyG, GPU-PyG, HyGCN
HyGCN（HyGCN由独立的用于聚合和组合阶段的专用引擎组成，外加一个协调这两个函数流水线执行的控制机制）	?混合架构，具有单独的聚合/组合阶段。 ?通过阶段间协调器实现两个函数流水线执行。 ?消除稀疏的窗口滑动/收缩方法（聚合阶段）。 ?专注于GCNs，不清楚如何泛化(没有边缘更新)。	GCN, GSC, GIN, DiffPool	IMDB, Cora, CiteSeer, COLLAB, PubMed, Reddit	CPU-PyG, GPU-PyG
AWB-GCN	? 通过三种负载平衡技术适应不同的 GNN 工作负载，根据每个分区的稀疏性进行选择。 ? 先处理组合，减少聚合操作次数。 ? 聚合和组合的细粒度流水线。 ? 专注于 GCN	GCN	Cora, CiteSeer, PubMed, Reddit, Nell	CPU-PyG, GPU-PyG, FPGA, HyGCN
GRIP	? 使用 GReTA 抽象 [84]，可推广到任何 GNN。 ? 使用类似于 HyGCN 的技术实际实现。	GCN, GIN, G-GCN, GS	Youtube, Livejournal, Pokec, Reddit	CPU-TF, GPU-TF, TPU, HyGCN
Auten et al.	? 平铺架构，可通过片上网络进行横向扩展。 ? 与HyGCN 类似，专业性较低但更易于概括。 ? 为卷积 GNN 提出了一种模块化架构	GCN, MPNN, GAT, PGNN	Cora, CiteSeer, DBLP, PubMed, QM9_1000	CPU, GPU	加速器的基本单元是由聚合器模块（AGG）、DNN加速器模块（DNA）、DNN队列（DNQ）和图形PE（GPE）组成的一个tile，它们都连接到一个片上路由器.DNA是用于密集乘法的数组，AGG是边缘控制加速器，DNQ是引擎间的缓冲区，GPE控制执行。
Zhang et al	? 离线软件加速（去冗余+节点重新排序）和FPGA硬件加速的结合。 ? 优化：双缓冲、节点+特征并行、双流水线模式，取决于矩阵乘法的顺序。	GCN	Flickr, Reddit, Yelp	CPU-TF, GPU-TF, CPU-C++, GPU-C++
Rubik	? 分层和统一的 PE 阵列设计 ? 包括小缓存以消除冗余聚合 ? 在软件中添加图形重新排序以提高缓存利用率	GIN, GS	Collab, BZR, IMDB, DD, CiteSeer, Reddit	Eyeriss-like, GPU-PyG	提出了一种分层的PE阵列设计，其中每个PE包含许多MAC单元（媒体存取控制），以及为它们提供信息的指令和数据队列。
GCNAX	? 具有可重构循环排序和融合的架构。 ? 选择是在离线设计空间探索之后做出的。 ? 使用外积来减轻零的不平衡存在。	GCN	Cora, CiteSeer, Pubmed, Nell, Reddit	HyGCN, AWB-GCN, SpArch	GCNAX比HyGCN和AWB-GCN分别快10倍和2倍，效率更高
GraphACT	? 仅评估训练和内存占用的加速器。 ? CPU+FPGA。优化依赖于负载平衡、调度、批处理、冗余聚合操作的去除。	GCN	PPI, Reddit, Yelp	CPU, GPU

文章图片

4.3 Discussion

第一个结论：目前存在的问题是缺乏通用的baseline以及有代表性的算法、datasets和设计目标的gnn的基准测试套件。为了弥补这一差距，提出的措施有OGB、GNNmark等用来提供有代表性的图形和gnn的项目，以及在硬件加速器方面比较各个架构的数据流，并对包含多个操作指令的数据流进行分类。
- 第二个结论：在gnn中不同的应用需要不同的设计方法。
  - 第三个结论：目前在加速方面比较突出的两个挑战分别是对动态图的支持和如何通过协同设计策略来解决gnn加速问题。其中动态图的支持仅在AliGraph中进行了评估，并且动态图的学习意味着要在每个时间步中处理GNN以及要随着图的发展来更新权重和矩阵；协同设计主要要考虑软硬件的任务分配问题即在考虑开销的基础上哪一部分分配给硬件，哪一部分分配给软件，其中硬件方面的挑战是，要根据众多的图类型和GNN变体(包括池化、采样或跳过连接等技术)，在性能和泛化之间找到合适的平衡。
  - 5 . GNN ACCELERATION: THE VISION（GNN加速:视觉）
  - 基于以上GNN加速方面的工作可得出结论：要么为特定的GNN变体提供一个极其有效的加速方案，要么为多种类型的GNN提供较低效率的通用或足够灵活的加速方案。因此，GNN加速的关键挑战是提供一个框架，既能最大化性能和效率，又能保持一定程度的灵活性，以适应不同的图大小、特征和GNN算法。
  - 在本节中，我们的目标是利用对现有加速工作的分析来假设未来GNN加速器应该具有的主要特征。特别是，我们设想的架构方法应由(i)软件-硬件合作设计、(ii)图形感知和(iii)以通信为中心的设计（可重构互连）组成。如下图所示：
  - 文章图片
    
    5.1 Software-Hardware Co-Design（软硬件合作设计）
  - 控制数据平面模型，一般来说，控制平面将完全在软件中实现，提供灵活性，数据平面将在提供效率的定制硬件中实现。虽然在概念上是分开的（见上图），但两个平面的操作将紧密耦合。
    - 控制平面通过拥有完整GNN结构和输入图的全局视图来管理加速器的动作。控制平面负责指示在数据平面中运行的数据流。方法是
    - (i)将GNN计算划分为可管理的计算段
    - (ii)将不同的顶点和边映射到数据平面的硬件资源
    - (iii)执行不同的调度以平衡工作负载，最大化流水线，等等。
    - (iv)驱动预处理(可能离线)步骤，如去除冗余操作或检测某些图形。
      - 数据平面由按照执行GNN的控制平面指令工作的处理和内存元素组成。正如我们在4.2节中看到的，我们可以采用许多策略来构建数据平面，例如，统一的、阶段性的、模块化的、同质化的、异构的，等等。其中的MAERI架构很有用，它是由一个同构的pe阵列和一个专门的内存层次结构通过一个轻量级可配置的互连结构组合在一起。该体系结构可以根据控制平面的命令对数据流进行调整，从而可以服务于一个算法或不同算法的多个执行阶段。
      - 5.2 Graph Awareness（图形感知）
      - 图的大小等方面，特征向量的相对大小、图的聚类因子或其平均度与加速 GNN非常相关。事实上，GNAdvisor 试图明确地利用这些信息来提高 GPU 的性能，而其它架构则根据图的特征来确定操作顺序或 PE 的映射。其他表征工作表明，循环排序或数据流设计决策对性能的影响肯定取决于输入图。
        这导致了我们设想的架构的第二个支柱：图形意识。如果 GNN 依赖于输入图，那么最大化性能需要了解该图的主要特征。应使用离线或在线方法从图中提取有用信息，控制平面将利用这些信息。因此，这将影响诸如图分区之类的方面，例如根据度数分布；不同聚合-组合阶段的排序和流水线操作，可能因层和图而异；或调度过程以最小化分区间通信。其中一个很好的例子是community detection，其有效的实现或预测了在运行时将图划分为密集连接的图元，这与高效池化、冗余消除和优化调度相关。同样，最大限度地减少提供图形感知的技术开销至关重要，要么通过启发式、重用先前分析，要么仅在可以提前完成预处理或其收益最大化的某些场合中使用。
      - 5.3 Communication-Centric Design（以通信为中心的设计）
      - 鉴于对输入图的依赖性和许多算法变体，GNN 带来了额外的挑战，即没有单一的最佳数据流。
      - 在 PE 之间使用可重新配置的互连结构来使硬件适应底层图形连接，或者换句话说，适应可能在层、分区或图形之间变化的最佳数据流。
      - 6 CONCLUSION
      - 最近 GNN 的研究呈爆炸式增长。正如我们在对当前最先进技术的分析中所看到的，大多数工作都集中在算法及其应用上，从而使 GNN 计算的主题变得不那么受欢迎。然而，我们预计 GNN 的软件和硬件支持领域将快速增长。
        研究更有效的 GNN 计算方法可能增加的原因：首先，该领域趋于成熟，更多的理论算法驱动研究让位于最面向应用的开发。这种趋势的一个明显例子是统一基准测试等方面的努力的出现。其次，GNN 是多个领域中许多颠覆性应用的关键，因此创造了一个明确的应用拉动，推动了对更好处理的需求。第三，GNN 提出了多种独特的挑战，例如算法变体的多样性、它们对图特征的依赖，或者它们在某些应用中的大规模。这使得 GNN 处理领域在可预见的未来不太可能饱和，因此不仅需要深入讨论与 GNN 处理相关的挑战，还需要深入讨论解决这些问题的可能方法。
        最后，我们强调了软件框架的日益流行以及最近出现的 GNN 硬件加速器。在软件方面，诸如 DGL 或 NeuGraph 之类的库旨在加速并为广泛使用的框架（如 TF 或 PyTorch）添加功能，所作的贡献是通过图分析或预编码加速 GNN，以及大规模系统中的计算分布，这是大型推荐系统非常需要的。在硬件方面，我们没有观察到明确的架构趋势，现有的提案正在讨论硬件架构是特定还是适用于多个 GNN 变体，以及统一架构或更分层的平铺组织。基于这一观察，我们设想未来的加速器将采用软硬件协同设计方法来最大化性能，将图形感知作为有利可图的优化机会，并通过可重新配置的互连解决工作负载的可变性。