图神经网络加速器深度调研（下）
摘要
近年来，图神经网络（Graph Neural Networks,GNNs）因为具有对图结构数据进行建模和学习的能力，而引起了机器学习领域研究者的广泛关注。在化学、网络、社交媒体、知识表示等领域，由于数据本身具有复杂的联系，通常采用图（Graph）作为数据结构来表示这种关系。随着各种GNN算法变体的发展，给这类可以建模为图结构数据处理任务的领域，带来了突破性结果。但是，在目前的研究阶段，GNN的高效计算仍然是一个非常开放的问题。最主要的原因来自于GNN的计算图依赖于同时存在的输入复杂结构的图数据，计算密集的操作和稀疏访存的操作等复杂行为，使得传统的通用计算架构、并行计算架构，或者是定制的图处理架构在面对GNN任务时都遇到了一定的困难。为此，出现了一系列软件框架工作或硬件加速器设计工作，分别希望更加充分地利用现有并行计算器件的能力进行GNN的计算，或设计适应GNN计算任务特点的专用硬件达到更高的速度或能效。不过，目前的架构设计工作还是探索性的，针对GNN计算任务进行特定架构设计的目标、关键问题定义、通用技术等还不清晰，不同架构的比较也没有明确统一的标准。此外，从计算任务上来说，各种GNN算法变体之间的计算图差异较大，且新算法迭代很快，相同的算法用于不同的任务，计算负载特征也会有较大不同。所以，现有的加速器研究还不能满足要求。针对这样的情况，我们通过对GNN算法的调研，给出了GNN算法的统一建模框架，便于分析GNN计算的特点，指导加速器设计工作，也为下一步从GNN计算任务到构建特定硬件架构并部署的完整流程研究提供了桥梁；通过对现有GNN加速器的调研，我们指出了现有GNN加速器设计的优劣，总结了关建问题、一般设计方法，提出未来的发展趋势，指导加速器设计工作。本系列文章笔者钟凯为清华大学电子工程系博士生；戴国浩为清华大学电子工程系助理研究员、博士后。该文工作得到清华大学和壁仞科技研究院联合研究项目的支持。
关键技术点总结
通过对上述工作的对比分析，我们可以总结得出GNN加速器设计工作的一些关键技术点。首先就像上文中的两大类分类那样，基本的架构选择上存在双阶段式和统一式两种架构，他们各有优劣。其次是数据格式上，数据格式作为基本计算单位，对算法准确率和硬件性能有本质影响，目前这部分的研究还比较少。对于具体的加速器优化，最容易想到的是针对GNN稀疏连接关系的特性，优化访问片外内存的数据量。其次是片上的数据复用方案，尽可能减少计算单元空闲等待时间，也能减少片外访存量；具体计算流程上，GNN同样与CNN类似有多层循环，循环展开的顺序的不同选择也会影响数据缓存方式和计算性能。下面我们将对每一点进行更详细的介绍。
4.1 整体架构
正如上文中的分类，GNN加速器的整体架构可分为两大类，对应的是计算流程上如何处理信息聚合这类稀疏操作和信息提取特征变换这类稠密操作。双阶段是架构采用并行结构，设计两个固定比例的专门的单元分别进行这两类操作。采用这种模式的好处是单模块的专用性增强，效率更高，尤其是信息聚合这种稀疏操作，采用专用的计算阵列和片上内存访问逻辑，能够减少冲突和等待，提高硬件利用率；缺点首先是固定的模块比例，难以在所有网络任务上取得较高的硬件利用率，不可避免出现等待的情况，其次是需要设计相应的数据循环顺序、模块间缓存单元，从而确保两个重要的功能：前一个模块的部分输出结果能够作为后一个模块的输入、两个模块的执行先后顺序可以改变从而适应不同的网络结构。作为双阶段式代表工作的HyGCN对两个阶段的循环顺序和模块间缓存进行了设计，支持两个阶段的模块片上流水线，通过并行度灵活的任务映射，提出不同的流水线优化策略，但是该设计没有考虑到两个阶段不同的先后执行顺序，在支持GraphSage、GAT等先进行稠密计算的任务时存在一定困难。GRIP则考虑到这一点，设计了多个数据可以互相传递的片上缓存，支持不同的执行顺序，并且也通过权重分块等方式实现片上流水线。不同于双阶段式架构，统一式架构采用同样的硬件单元支持两种操作，优势之一是可以采用本地数据缓存，给每个PE设计本地缓存，前一个计算完成的信息提取阶段的计算输出可以直接用于后一个稀疏聚合操作，这种设计的主要缺点是通用处理阵列支持稀疏操作的效率通常不高，要么需要较为复杂的数据通路设计，比如AWB-GCN，要么采用逻辑比较简单但是效率难以保证的逻辑进行稀疏聚合，比如EnGN。双阶段式和统一式架构各有优劣，目前还没有两全其美的解决方案和定论，通过数据路径设计让两种模块内部的计算单元或存储能够动态调度和复用、基于FPGA等动态可重构平台面向不同任务进行自动化硬件设计与生成，是两种比较有潜力的方案。
4.2 数据格式
数据格式是加速器设计不能回避的关键问题，在经典的CNN加速器设计研究历程中，数据格式由浮点到定点，由高位宽到低位宽，并出现一系列研究量化算法的研究和一系列支持特殊量化方案的软硬件系统优化设计工作。目前，出现了一些研究GNN模型量化的研究，甚至达到了二值化的量化效果12，但是目前的GNN加速器设计还没有详细考虑到这一优化点进行优化，采用的数据格式普遍较为保守。上文中详细介绍的几篇工作具体采用数据格式情况如下表所示。可以发现大部分工作采用32位浮点或定点数据格式，但CNN计算任务的加速研究3普遍表明，经过软硬件协同优化，将数据格式转化为8位定点数普遍是没有问题的，在这一点上现有GNN加速工作仍有较多的探索空间。
各GNN加速器工作采用的数据格式
此外，CNN加速研究中还有一个很重要的技术称之为压缩，或是在原本稠密的CNN计算中寻找稀疏性，或是通过减少通道4、权重特征值分解（SVD）、傅里叶变换（FFT）5等方式，减少计算量。在GNN中，虽然邻接矩阵已经是稀疏的，且这给GNN加速工作带来了本质困难，但权重、特征向量的数据规模更大，原本就存在的稀疏性和冗余性还没有被发掘利用，通过类似于CNN中稀疏化、剪枝、压缩的方案，有希望进一步减小计算量。
4.3 访存优化
在GNN的加速器设计中，片外访存优化是很重要的一步，片外访存优化的目标是让访存总量小、单次访问数据量大。对于GNN计算任务，考虑单层进行分析，多个输出节点所需要的所有输入节点集合通常较大，很难全都存到片上，只能先缓存部分输出节点所需要的输入节点，在这个过程中，可以通过跳过暂时不用的输入节点数据，减少读取量，但是在节点特征长度不长的情况下，按稀疏的方式访存，单次访问数据量小，带宽不能被有效利用。现有的GNN加速器方案中，HyGCN明确提出了新颖的访存优化策略，即通过窗口滑动和收缩，尽可能减少片外访存量，同时又保证一定的连续性；但是这一方案的具体性能对数据特征的依赖程度很高，不同数据特征情况下这种优化策略的效果差距很大，而且该方案也没有考虑到不同的特征长度情况下的策略，如前所述，当节点特征长度较长时，以节点为粒度进行内存访问就可以达到访存量小、访存规则性高的效果，但节点特征长度较短时，则多个相邻节点的数据同时访问更好。
进行GNN加速器的访存优化，除了上述访存规模的优化外，还有两个关键技术，分别是预处理（数据重排序，Data Reordering）6和数据预取（Data Pre-Fetching）7。Two-Stage-GCN这篇工作就采用了稀疏化、节点重排序两种预处理算法，增加了计算图中的节点聚集性，减少了额外的数据访问，同时增加了数据访问的局部性，有利于复用。GraphACT也采用了复杂的数据匹配算法，找到最适合节点间数据重用的计算顺序，尽可能减少对片外内存数据的访问。采用预处理的方法好处明显，但是效果更好的预处理算法本身开销也很大，需要综合考虑整个计算任务的调度能否掩盖或平摊开销、整体得到优化。比如Two-Stage-GCN提出的场景是图结构不常变化而节点数据可能变化的场景，针对图结构进行的预处理能够多次复用，属于开销可以平摊的场景；GraphACT面向的则是训练场景，每个批次的计算和下个批次的预处理可以并行，属于开销可以掩盖的场景。数据预取则是更加常见的一种方案，可以说每个加速器设计都或多或少用到了数据预取的思想，其中HyGCN、EnGN明确提出数据预取的概念，并设计了相应的单元，其中EnGN作为统一式架构，数据预取单元还为提高聚合操作阶段的硬件利用效率起到了作用。GRIP的架构中虽然有名为“pre-fetch”的单元，但其执行的是片上数据的按输入节点粒度的读取，并非访存优化中的预取。从上述分析可以看到，数据重排和数据预取作为两种在传统图处理领域广泛研究并应用的优化访存瓶颈的技术，在GNN加速器的设计中研究的还比较基础，有较大的探索空间。
4.4 数据复用
数据复用一方面有助于减少加速器整体从片外访存的数据量，降低访存瓶颈的影响，另一方面使得片上计算单元数据供给充足，减少等待时间，提高效率。数据复用包含两个层面，空间复用和时间复用。空间复用是指同样的数据被不同计算单元需要，主要发生在网络权重上，以及采用与目标节点无关的边消息提取方式的网络结构中的边消息复用、任何类型的边消息提取过程中的输入节点特征复用。对于权重的复用，数据流动方式比较规则，利用广播数据通路就比较容易支持。对于边消息和节点特征的复用则比较复杂，除了通过设计加速器在聚合阶段输出节点上一定的并行度来实现输入数据的复用外，还需要相应的计算顺序调度策略和广播数据通路，一方面让能够复用的数据能够尽量同时使用完毕，减少单位缓存量，相当于增加了片上缓存能力，另一方面使数据通路在没有复用的稀疏情境下也能保持较好的效率不至于额外开销过大。时间复用是指当前计算单元使用或产生的数据，在之后的时刻被其他计算单元使用，最常见的情况有：聚合阶段的结果被变换阶段作为输入使用、聚合或变换阶段的部分结果需要继续累加、权重需要循环使用、当前输入节点会被下一批次的输出节点使用。这几种情况都与GNN计算的循环展开顺序有关，其中前两种的具体解决方案都是设计足够的片上缓存支持复用，缓存规模由计算并行度方案可以理论推导出；后两种由于数据规模可能较大，则不能保证完全片上复用，要设计相应的片外存储调度策略。目前的加速器设计工作中，针对通常的GNN场景进行了静态方案设计，但GNN的一大特点是计算流图由数据本身（邻接矩阵）决定，在大规模GNN任务计算中，输入到GNN加速器的任务通常是提取出来的Node flow，在这一过程中可以通过编译、调度等方式进行优化，GRIP提出了支持以Node flow为格式的输入数据，但没有设计相应的优化，在这方面的软硬件协同工作还很值得探索。
4.5 循环展开
循环展开不只是潜在的优化技术点，更是加速器设计无法回避的最基础的问题，目前被研究的较多，每篇工作都有自己的循环展开方案选择，EnGN、Two-Stage-GCN两篇工作更是对循环展开顺序进行了研究，正如上文所述，循环展开的顺序对片上缓存数量、片外访存数量的部分影响可以通过理论推导得出，这两篇文章正是基于这样的理论进行优化设计，Two-Stage-GCN的一大贡献点正是基于此设计了两种不同顺序的数据通路。不过具体的加速器循环展开顺序、并行度设计是耦合的，整体空间也比目前探究的要大，还需要完整的建模和设计分析工作。
启发与展望
通过对上述工作的详细介绍、关键优化技术点的分析，我们可以发现现有的GNN加速器工作完成了基本的GNN计算功能，发展出了双阶段式和统一式两种各有优劣的架构，但是普遍存在缺乏软硬件协同优化设计的问题，具体体现在如下方方面。
数据格式
目前的数据格式通常为32位浮点数或定点数，对于训练任务是否存在冗余还可以进一步探究，对于推理任务来说显然精度冗余较大，但如何浮点训练的得到的模型转化为低位宽定点模型，或者如何在训练阶段就考虑到量化误差进行专门的低位宽模型训练，还需要深入研究提出具体方案。同样，在硬件上如何支持相应的低位宽数据格式计算、保持精度的累加器、计算后量化等操作，需要根据量化方案选择进行协同设计。另一方面，通过稀疏化、分解等方式进行模型压缩，减少计算量的方案目前在GNN的加速工作中还没有较好的应用。
预处理、预取
预处理在前文的算法阶段分析中已经有所介绍，包含离线静态预处理、在线动态预处理等不同种类，在增加稀疏矩阵聚集性、减少片外访存、增加片上复用等多方面都有很大潜力，但预处理本身的开销必须被仔细考虑，具体效果必须面向具体任务得到实践的检验，现有加速器工作利用这一点的还比较少，对系统性能的比较也不清晰。预取和预处理一样是传统图计算加速的典型方法，实际应用中的大规模GNN计算系统同样具有多层次的存储单元，目前的加速器工作一方面只涉及到片外片内共两个层次，另一方面这两个层次之间的数据预取策略和缓存单元设计还不明确，在算法、硬件两方面对数据结构和层次都有很大的优化空间。
编译调度
CNN的加速器设计工作也经历了从固定状态机驱动的基本功能、配置驱动的多数据通路支持、协同编译器的指令集架构这样的发展历程。GNN加速器的研究，目前一方面还刚发展到配置驱动的多数据通路，还没有涉及到指令集，另一方面GNN的计算由于不规则性、数据驱动效应明显，可调度空间其实更大，所带来的收益也更多。在大规模GNN计算任务中，真正需要加速器执行的计算之前，还有计算图构建、采样、预处理环节，这当中可以根据实际场景进行简单或复杂的调度设计。针对GNN加速器的指令集、编译器、调度优化方案还是一片可以研究的新领域。
在本文编写期间，又出现了一些新的GNN加速器工作，比如DeepBurningGL8，BlockGNN9，本文没有详细分析对比，但也不会脱离上述算法分析框架、硬件关键优化技术点。总体来说，GNN计算任务有不同于CNN和传统图计算任务的特点，GNN专用加速器也有较大的设计空间，目前的工作完成了探索性的设计，但具体优化点还有很多没有被详细研究，尤其是软硬件协同优化的一系列方面，有希望带来较大的整体性能提升，但因为比较复杂，需要算法和硬件的同步设计而还没有被充分研究，这给之后的GNN加速器研究工作带来了很有希望和潜力的方向。
作者介绍
钟凯，2019年本科毕业于清华大学电子工程系，目前在清华大学电子工程系电路与系统研究所攻读博士学位，在汪玉教授和戴国浩博士后的指导下，主要从事神经网络的量化算法、硬件加速、基于FPGA的加速器开发等工作。 戴国浩，现清华大学电子工程系助理研究员、博士后，分别于2019年和2014年在清华大学电子工程系获得博士与学士学位。主要研究方向为大规模图计算、异构计算、存算一体、虚拟化等，曾获ASPDAC 2019最佳论文奖、DATE 2018最佳论文提名。
参考文献
往期推荐
壁仞科技研究院作为壁仞科技的前沿研究部门，旨在研究新型智能计算系统的关键技术，重点关注新型架构，先进编译技术和设计方法学，并将逐渐拓展研究方向，探索未来智能系统的各种可能。壁仞科技研究院秉持开放的原则，将积极投入各类产学研合作并参与开源社区的建设，为相关领域的技术进步做出自己的贡献。