图神经网络加速器深度调研（中）

摘要

近年来，图神经网络（Graph Neural Networks,GNNs）因为具有对图结构数据进行建模和学习的能力，而引起了机器学习领域研究者的广泛关注。在化学、网络、社交媒体、知识表示等领域，由于数据本身具有复杂的联系，通常采用图（Graph）作为数据结构来表示这种关系。随着各种GNN算法变体的发展，给这类可以建模为图结构数据处理任务的领域，带来了突破性结果。但是，在目前的研究阶段，GNN的高效计算仍然是一个非常开放的问题。最主要的原因来自于GNN的计算图依赖于同时存在的输入复杂结构的图数据，计算密集的操作和稀疏访存的操作等复杂行为，使得传统的通用计算架构、并行计算架构，或者是定制的图处理架构在面对GNN任务时都遇到了一定的困难。为此，出现了一系列软件框架工作或硬件加速器设计工作，分别希望更加充分地利用现有并行计算器件的能力进行GNN的计算，或设计适应GNN计算任务特点的专用硬件达到更高的速度或能效。不过，目前的架构设计工作还是探索性的，针对GNN计算任务进行特定架构设计的目标、关键问题定义、通用技术等还不清晰，不同架构的比较也没有明确统一的标准。此外，从计算任务上来说，各种GNN算法变体之间的计算图差异较大，且新算法迭代很快，相同的算法用于不同的任务，计算负载特征也会有较大不同。所以，现有的加速器研究还不能满足要求。针对这样的情况，我们通过对GNN算法的调研，给出了GNN算法的统一建模框架，便于分析GNN计算的特点，指导加速器设计工作，也为下一步从GNN计算任务到构建特定硬件架构并部署的完整流程研究提供了桥梁；通过对现有GNN加速器的调研，我们指出了现有GNN加速器设计的优劣，总结了关建问题、一般设计方法，提出未来的发展趋势，指导加速器设计工作。
本系列文章笔者钟凯为清华大学电子工程系博士生；戴国浩为清华大学电子工程系助理研究员、博士后。该文工作得到清华大学和壁仞科技研究院联合研究项目的支持。

3
 GNN加速器分析

3.1 GNN加速器评价指标

一般来说，一个神经网络加速系统的设计应该考虑至少三个主要指标¹：模型准确率（ModelAccuracy）、吞吐量（Throughput）、能量效率（EnergyEfficiency），在有些场景下，延时（Latency）比吞吐量更关键，有时灵活性（Flexibility）也非常关键。GNN的加速器设计也需要从这些方面进行考察。

(1)准确率

在没有涉及到软硬件联合优化的情况下，模型准确率主要是个算法问题，重要的影响因素包括如何进行数据预处理、如何设计GNN结构并设置相应参数、如何选择训练策略等，不过这些因素不是加速器设计和评价的重点；在涉及到软硬件协同优化时，则需要考虑模型准确率，一般来说，通过类似于已经广泛应用于CNN的高效计算中的压缩²、量化³、设计低计算量网络结构⁴等技术，可以在吞吐量、能量效率和准确率指标间寻找合适的平衡，并有可能做到在达到同样准确率的前提下提高能量效率和吞吐量，这也将是之后GNN加速器乃至整个GNN计算系统的关键研究点。

(2)吞吐量

GNN计算加速器的吞吐量可以通过下列公式定义：

这一公式与通用的特定任务加速器吞吐效率衡量方式一致，一般从计算量角度定义，如对一个批次节点生成的Nodeflow进行GNN模型计算时需要的乘法和加法的次数。我们可以通过模型压缩、新模型设计等方法减少。则取决于加速器的片上计算单元数量和时钟频率。除了通过纯电路优化的方法来提高时钟频率，或通过增加设计方案的资源预算来增加电路并行度以外，还可以通过软硬件协同优化的方式进行优化。比如通过量化算法那将GNN计算中的数据位宽降低，从而简化硬件上对应计算单元的资源开销（甚至可以降低到一比特，从而将乘法简化为异或⁵）。这样可以增加计算单元密度，在同等电路面积功耗资源下，提高。优化过程最复杂的影响因素是，即所有计算单元是否每个周期都能有效工作，这一点在GNN这一具有随机稀疏计算模式的任务中尤其难以提高，同时也说明具有较大的优化空间。该因素会受到访存能力、架构设计、编译执行策略的影响，一般来说，通过较好的并行度设计、多模块的流水线设计、高效的存储排布和合理的数据通路，能够提高。同时，通过软硬件协同优化设计，如进行离线数据预处理、在线编译调度阶段进行任务执行顺序调整、对模型进行压缩量化减少访存压力和片上缓存需求等方式，都有望提高。

(3)能量效率

GNN计算加速器的能耗可以划分为计算能耗和访存能耗：

对于计算能耗，实际执行的计算量是重要因素，一方面可以通过模型压缩技术减少，另一方面值得注意的是可以通过整个计算系统来减少，包括能支持在Nodeflow上做GNN模型计算的加速器的架构设计。在最初的GNN计算实现中，GNN模型每次都在整个图数据上进行，其实造成了很多不必要的计算量，通过预处理阶段适当的Nodeflow提取，得到最小计算量的流图，对于减少计算量是必要的。此外，GNN中可能出现中间结果的复用，如前文介绍的GraphSage中的边消息提取结果，以及GAT中边消息提取的结果之一，其实都与无关而只取决于，在多个目标节点之间可以复用，可以通过较好的存储调度和数据通路的支持来避免重复计算。计算能耗的另一个影响因素为单次计算的平均能耗，这一点可以通过量化简化硬件计算单元实现，也受到基本功能电路IP性能的影响。

对于访存能耗，访存数量与架构设计和调度策略相关，在硬件资源预算限制下，设计足够大小的片上缓存、局部性较好的互联结构、高命中率的缓存策略非常重要。而单次访存的能耗，则可以通过量化减少数据位宽的方式进行减少。

对于相同的初始GNN计算任务，能量效率是能耗的反比，完成同样的任务能耗越低，则能量效率越高。一般通过模型压缩等方式减少了计算量与数据量从而降低能耗，也算作相比于原任务能量效率的提升，不过目前采用这样技术的加速器设计工作还没有出现。

3.2 典型工作介绍

图神经网络的计算模式比较独特，既有与传统深度学习一致的密集矩阵乘法计算，也有需要由图的连接关系决定的稀疏访存的计算，除了通过算法、系统的优化提高数据访问的效率，设计相应的图神经网络计算加速器架构也是提高图神经网络计算效率的重要方式。目前这类加速器架构设计并不多，大致可以分为两大类。一类是针对图神经网络的两种计算模式设计两种对应的硬件单元，并对它们之间的片上缓存和数据流进行优化，称之为双段式架构（TwoStage Architecture）；还有一类是用同样的硬件单元完成稀疏矩阵计算和稠密矩阵计算，称之为统一式架构（UniformArchitecture）。

(1)双段式架构

1）HyGCN

⁶这是一篇提出较早的双段式GNN推理加速器，其架构如图5所示，两大主要计算模块分别执行GNN中的聚合操作和组合操作。聚合部分由包含稀疏消除的访存控制器和多个单指令多数据（SingleInstruction MultipleData，SIMD）核构成，通过在硬件上实现采样和稀疏消除的单元，该架构可以动态地在稀疏矩阵上进行“滑动”和“收缩”，减少访存量，多个单指令多数据核可以灵活地配置，以较高的利用率进行聚合。组合部分是由可配置的多个脉动阵列（SystolicArray，SA）架构构成的矩阵乘法单元，多个阵列可以独立工作或协同工作。本工作实现了GNN计算的基本功能，设计了双阶段流水线，优化了访存开销，不过没有仔细考虑缓存中数据复用的设计和层次化的存储结构。

图5 HyGCN提出的双段式GNN加速器架构图

2）GraphACT

GraphACT⁷提出了一个主机CPU加FPGA加速器实现的GNN训练系统。主机部分除了执行softmax函数等结果和训练过程中loss函数的计算，还通过一个精心设计的匹配算法，对待计算GNN任务进行预处理，将需要计算的数据按照最有利于复用的方式排列好，传输到FPGA板卡上的内存中；FPGA部分则包含了两大硬件功能模块，分别进行向量计算和矩阵计算，以及相应的片上缓存。由于该工作用于训练场景，主机上的预处理能够与FPGA加速器的任务计算并行进行，所以效率较高，图6是该系统进行GNN训练任务的时序流程图。

图6 GraphACT系统进行GNN训练任务时的调度时序流程图

3）GRIP

GReTA⁸和GRIP⁹是一个系列的前后两篇工作，分别对GNN的计算环节进行了抽象总结，并提出了双段式架构的GNN推理加速器。相比于HyGCN，GRIP设计的加速器架构强调了Nodeflow的概念：在GNN的推理任务中，通常不需要计算所有节点的输出，而是只计算少数节点，从少数输出节点通过图的连接关系反推出GNN各层的输入节点及其连接关系，构成的即最小计算量的一个子图。GRIP设计了相应的多个缓存以及对应的预取模块处理Nodeflow数据，通过交叉阵列的方式发送给多个并行执行多个节点的聚合任务的单元；节点特征变换部分则通过权重分块缓存进行加速，总体架构如图7所示。该工作通过组合各个中间缓存之间的数据流动，可以支持多种GNN变体，通过多个缓存和计算单元尽可能实现了数据的空间复用，不过交叉阵列还不够优化，也较少考虑数据的时间复用。

图7 GRIP的架构图

4）Two-Mode-GCN

¹⁰这是一篇基于FPGA的GNN加速器设计工作。这篇工作相比于之前研究的优势，一方面在于基于FPGA平台对加速器架构进行了实际检验，另一方面体现在其比较完备的计算流程考虑上。首先本文对预处理环节进行了研究，提出了稀疏化和重排序两种算法，分别用于减少邻边数量从而减少访存，以及提高片上数据复用能力。另一方面，本文提出的架构设计虽然也是比较常规的双阶段流水线设计，如图8所示，但在数据流上明确了乒乓缓存的设计，同时将激活模块独立出来，并设计了两种数据流动模式（Mode1和Mode2）。两种模式分别对应计算流程上的先计算聚合和先计算特征变换，这两种模式的详细设计使得该工作能支持一些GNN变体，也能根据每层输入输出特征维度的不同，选择合适的模式来增加数据复用量。不过，该工作也存在一些问题：预处理算法是对全局离线处理设计的，对采用动态提取Nodeflow的应用场景影响如何没有明确结论。两种计算模式其实在同一网络不同层之间想切换时存在困难，以及能够支持的GNN种类也不足。此外该设计默认采用了32位浮点数格式表示，应该有软硬件协同优化的空间，可以通过数据压缩或量化进一步提高加速器性能。

图8 Two-Mode-GCN提出的架构以及两种数据流模式示意图

（2）统一式架构

区别于双段式架构用不同的硬件单元执行图神经网络的不同部分，统一式架构采用一致的硬件单元完成稀疏和稠密两种计算。

1）EnGN

EnGN¹¹是统一式架构的一个典型代表，该工作提出了一个神经图处理单元（NeuralGraph ProcessingUnit，NGPU）来进行GNN中的稀疏矩阵或稠密矩阵乘法计算。具体来说，NGPU由一些彼此相连的处理单元（ProcessingElement，PE）二维阵列构成，每个PE包含乘累加计算单元、度感知的特征缓存、权重缓存，能够更好地利用数据时间复用特性。此外每一列的PE通过被称之为环边缩减（RingEdgeReduce，RER）的拓扑结构连接起来，EnGN正是通过这一数据通路进行稀疏矩阵操作，配合图数据的预处理，将需要聚合的特征数据通过几个周期的数据传递聚合起来。该工作的架构图如图9所示，其优点是度感知的缓存减少了访存数量，且二维阵列结构电路特性更好，不足之处是对GNN的聚合操作支持并不好，RER结构进行聚合存在额外开销。

图9 EnGN的架构图

2）AWB-GCN

AWB-GCN¹²也是一个采用统一式架构的GNN加速器，主要聚焦于稀疏矩阵乘法计算中负载不均衡的问题，提出了分布平滑、远程交换、特殊行重映射三种技术进行负载均衡，并在硬件上设计了相应的数据通路支持，从而提高结构统一的PE单元的利用率。由于GNN中稀疏矩阵乘法计算的稀疏矩阵由任务决定，各任务稀疏性不同，所以本文还提出了一个自动调优模块，通过当前周期执行情况，调整下一周期的部署策略，从而可以在同一数据集上多次运行GNN算法的情况下，自动调优使得硬件利用率提高。

3）GNNA

GNNA¹³提出的加速器架构比较特殊，顶层是由同一结构的模块构成的阵列，互相之间通过片上网络（NetworkonChip，NoC）连接，但模块内部采用了不同单元执行GNN算法的不同部分，其一个模块的内部结构如图10所示。通过配置NoC网络汇总计算模块和访存模块的不同比例，GNNA架构可以实现与GPU相同计算量、相同访存带宽、与CPU相同带宽等配置。通过将复杂的随机地址数据访问交给NoC，使得该工作顶层架构简单，模块内部也不用过多考虑访存的问题，但是NoC和交叉阵列的开销很大。

图10 GNNA提出的通过NoC连接的计算模块内部结构

未完待续。。。

作者介绍

钟凯，2019年本科毕业于清华大学电子工程系，目前在清华大学电子工程系电路与系统研究所攻读博士学位，在汪玉教授和戴国浩博士后的指导下，主要从事神经网络的量化算法、硬件加速、基于FPGA的加速器开发等工作。 戴国浩，现清华大学电子工程系助理研究员、博士后，分别于2019年和2014年在清华大学电子工程系获得博士与学士学位。主要研究方向为大规模图计算、异构计算、存算一体、虚拟化等，曾获ASPDAC 2019最佳论文奖、DATE 2018最佳论文提名。

参考文献

1、 Guo, Kaiyuan, et al. “[DL] A Survey of FPGA Based Neural Network Accelerator.” ACM Transactions on Reconfigurable Technology and Systems, vol. 9, no. 4, p. 22.

2、 Han, Song, et al. “Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding.” ArXiv:1510.00149 [Cs], Feb. 2016. arXiv.org, http://arxiv.org/abs/1510.00149.

3、 Jacob, Benoit, et al. “Quantization and Training of Neural Networks for Efficient Integer-Arithmetic-Only Inference.” Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018, pp. 2704–13.

4、 Tan, Mingxing, and Quoc V. Le. “EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks.” ArXiv:1905.11946 [Cs, Stat], Sept. 2020. arXiv.org, http://arxiv.org/abs/1905.11946.

5、 Bahri, Mehdi, et al. “Binary Graph Neural Networks.” ArXiv:2012.15823 [Cs], Dec. 2020. arXiv.org, http://arxiv.org/abs/2012.15823.

6、 Yan, Mingyu, et al. “HyGCN: A GCN Accelerator with Hybrid Architecture.” 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), IEEE, 2020, pp. 15–29. DOI.org (Crossref), doi:10.1109/HPCA47549.2020.00012.

7、 Zeng, Hanqing, and Viktor Prasanna. “GraphACT: Accelerating GCN Training on CPU-FPGA Heterogeneous Platforms.” The 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Feb. 2020, pp. 255–65. arXiv.org, doi:10.1145/3373087.3375312.

8、 Kevin, Kiningham, et al. “GReTA: Hardware Optimized Graph Processing for GNNs.” Proceedings of the Second SysML Conference, ACM, 2017, pp. 1–5. DOI.org (Crossref), doi:10.1145/3079856.3080246.

9、 Kiningham, Kevin, et al. “GRIP: A Graph Neural Network Accelerator Architecture.” ArXiv:2007.13828 [Cs], July 2020. arXiv.org, http://arxiv.org/abs/2007.13828.

10、 Zhang, B., et al. “Hardware Acceleration of Large Scale GCN Inference.” 2020 IEEE 31st International Conference on Application-Specific Systems, Architectures and Processors (ASAP), 2020, pp. 61–68. IEEE Xplore, doi:10.1109/ASAP49362.2020.00019.

11、 Liang, Shengwen, et al. “EnGN: A High-Throughput and Energy-Efficient Accelerator for Large Graph Neural Networks.” ArXiv:1909.00155 [Cs], Apr. 2020. arXiv.org, http://arxiv.org/abs/1909.00155.

12、 Geng, Tong, et al. “AWB-GCN: A Graph Convolutional Network Accelerator with Runtime Workload Rebalancing.” ArXiv:1908.10834 [Cs], Apr. 2020. arXiv.org, http://arxiv.org/abs/1908.10834.

13、 Auten, A., et al. “Hardware Acceleration of Graph Neural Networks.” 2020 57th ACM/IEEE Design Automation Conference (DAC), 2020, pp. 1–6. IEEE Xplore, doi:10.1109/DAC18072.2020.9218751.

     往期推荐

关于壁仞科技研究院

壁仞科技研究院作为壁仞科技的前沿研究部门，旨在研究新型智能计算系统的关键技术，重点关注新型架构，先进编译技术和设计方法学，并将逐渐拓展研究方向，探索未来智能系统的各种可能。壁仞科技研究院秉持开放的原则，将积极投入各类产学研合作并参与开源社区的建设，为相关领域的技术进步做出自己的贡献。

扫码关注我们