大家读完觉得有帮助记得及时关注和点赞！！！
此文档相对来说有点深度，需要有些技术深度的人方可看明白，注意
抽象
图神经网络 （GNN） 最近因其在非欧几里得数据上的性能而受到关注。事实证明，使用自定义硬件架构对 GNN 特别有益，因为 GNN 的内存访问模式不规则，这是由图形的稀疏结构导致的。然而，现有的 FPGA 加速器受到其双缓冲机制的限制，这没有考虑到典型图形数据集中的不规则节点分布。为了解决这个问题，我们引入了 AMPLE （Accelerated Message Passing Logic Engine），这是一个利用新的事件驱动编程流程的 FPGA 加速器。我们开发了一种混合算术架构，使 GNN 推理能够在节点级粒度上进行量化。最后，实现数据和指令的预取器，以优化片外内存访问并最大限度地提高节点并行性。对引文和社交媒体图数据集的评估范围从2K 到700K 个节点的平均加速比243×和7.2×分别针对 CPU 和 GPU 的对应项。
1介绍
图形是捕获实体之间关系的强大表示形式，这些实体表示为节点，由边连接在一起。这种结构支持对各种复杂系统进行建模，包括社交网络（Alamsyah 等人，2021)、生物相互作用（Wu 等人，2021)和推荐系统（Wang 等人，2021).图神经网络 （GNN） 已成为一种处理图数据的变革性方法，旨在通过利用图中的互连从复杂的关系信息中学习（Kipf & Welling，2016;Veličković 等人，2017).
GNN 模型的推理可以分为两个主要的计算阶段，（1） 聚合和 （2） 转换 （Gilmer 等人，2017).在 Aggregation 阶段，排列不变函数（如 summation 或 mean）应用于节点邻居的特征嵌入。然后，此阶段的结果将用于 Transformation 阶段，该阶段由一个全连接层组成，用于为每个节点生成更新的特征嵌入。虽然转换阶段呈现出高度规则的计算模式，可以在 GPU 等并行化设备上有效加速，但由于典型图形数据的随机性和稀疏性，聚合阶段涉及许多不规则的内存访问。此外，聚合延迟是节点程度的函数，它遵循高度不均匀的分布。因此，一个高效设计的 GNN 加速器需要减轻 Aggregation 阶段的计算不规则性，同时利用 Transformation 阶段的规律性（Yan 等人，2020).
表 1：跨硬件平台的图形处理功能摘要。尽管 CPU 并行化是可能的，但与并行加速器相比，多线程 CPU 的内核数量有限。在 GPU 中可以进行事件驱动编程，但计算不遵循以节点为中心的流程。尽管在 GenGNN 中可以预取，但 Velocity 中节点的所有传入消息都需要存储在芯片上。最后，没有现有的加速器支持任意多精度计算。
| 硬件平台 | 并行 | 事件驱动编程 | 节点预取 | 多精度 |
| CPU （Intel Xeon） | ✗ | ✓ | ✗ | ✗ |
| 图形处理器 （RTX A6000） | ✓ | ✓ | ✗ | ✗ |
| 海基网（Yan 等人，2020) | ✓ | ✗ | ✗ | ✗ |
| GenGNN 系列（Abi-Karam 等人，2022) | ✓ | ✗ | ✓ | ✗ |
| 充足 | ✓ | ✓ | ✓ | ✓ |
尽管 CPU 内存系统是一种成熟且高度优化的技术，但图形数据的稀疏结构使传统的缓存系统效率降低，因为节点聚合会导致对非连续内存范围的大量访问。由于深度并行性，GPU 上的推理提供了更高的性能，但是，这些设备受到高延迟内存管理机制的限制。此外，不支持相位间流水线，这意味着聚合结果必须存储到片外内存中，然后才能重新获取用于转换阶段。最后，现代设备对低精度数值格式的计算的支持有限。
这些考虑激发了几个 GNN 加速器的设计。HyGCN 利用一组单指令多数据 （SIMD） 内核进行聚合，并利用脉动阵列进行节点转换（Yan 等人，2020).同时，GenGNN 被提议作为 GNN 加速的模型不可知框架，解决了 GNN 模型和定制加速器的开发速度之间的差距（Abi-Karam 等人，2022)通过 High-Level Synthesis 工具。表 1 总结了可用 GNN 硬件平台的特性。尽管先前提出的 GNN 加速器具有优势，但 （i） 由于节点度分布不均匀，部署在 HyGCN 中的双缓冲机制不太适合图计算。在这种范式下，低度节点必须等待高度节点才能继续计算，从而导致大量的流水线间隙。这凸显了对事件驱动编程流程的需求，其中节点被独立分配资源并调度到加速器上。 此外，（ii） 这两个加速器都不提供对模型量化的硬件支持。正如 Tailor 等人所观察到的。 （Tailor 等人，2020)，GNN 中量化的精度成本主要是由于聚合阶段，并且与节点的程度直接相关。因此，将低度节点转换为较低精度的格式，同时以高精度保留高度节点，可以降低内存成本和资源使用量，同时降低模型精度的成本。 最后，（iii） 现有的加速器需要对整个 input graph 的 node embeddings进行片上缓冲。因此，这些方法对大型图形 （>100knodes），其中嵌入不可能存储在芯片上，这凸显了以节点为中心的预取系统的需求，以便在加速器繁忙时隐藏内存访问延迟。
我们通过引入一种新颖的 GNN 加速器 AMPLE 来解决这些缺点，其贡献如下：
- •
我们展示了一种用于 GNN 加速的事件驱动编程模型，它使主机能够通过 memory-mapped registers异步编程节点。
- •
我们提出了一种架构，其特点是通过片上网络连接的多精度聚合核心的异构池，这些核子根据程度和精度动态分配给节点。
- •
我们在 2K 到 700K 节点的大规模图形数据集上评估 AMPLE，实现了平均243×和7.2×分别与 CPU 和 GPU 基准进行比较。
本文的正文结构如下。第 2 节介绍了 GNN 和神经网络量化的背景。第 3 节介绍了 AMPLE 加速器的架构，包括如何在电路级实现每个高级功能。最后，第 4 节解释了针对 CPU/GPU 基线的测试方法和实验结果。
2背景
2.1图形表示
A 图表G=(𝒱,ℰ)是一组节点/顶点𝒱和边缘ℰ.图层处的要素制图表达集l由 matrix 表示X(l)∈ℛN×D哪里N=|𝒱|是节点数，D是特征大小。元素e我,j=(v我,vj)存在于ℰ表示节点之间存在连接v我和vj，意思是节点vj包含在我的邻居们，𝒩我和v我包含在𝒩j.在无向图中，边元素e我,j对应于ej,我.图形中的连接可以使用N×N邻接矩阵，其中每个元素一个我,j表示节点之间的边我和j.
2.2图形神经网络 （GNN）
在 GNN 中，图形数据在多个层上进行转换，以在整个图形或单个节点/边缘上执行分类和/或回归任务。GNN 可以通过消息传递机制表示（Gilmer 等人，2017)，该法将节点更新规律概括如下。
可以看出，在一般情况下，每个节点都会聚合表示为任意函数的传入消息φ，这相当于在φ=𝐱jl.消息通过任意排列不变聚合函数进行聚合一个j∈𝒩(我)在邻域 of 的我和 Arbitrary 变换函数γ(𝐱我l,𝐦我l)哪里𝐦我l是聚合的结果（即𝐦我=一个j∈𝒩(我)φ(𝐱我l,𝐱jl,e我,jl)).
2.2.1图卷积网络 （GCN）
GCN 作为类似于计算机视觉领域卷积神经网络的解决方案出现（Kipf & Welling，2016).单个 GCN 层的单元节点更新定律如公式 2 所示。
2.2.2图同构网络 （GIN）
GIN 被提议作为一种模型，可以证明为两个图形生成不同的特征更新，这两个图形可以通过 Weisfeiler-Lehman 检验证明是非同构的（莱曼，2018)，从而最大限度地发挥其表征能力（Xu 等人，2018).更新定律由以下公式给出，其中ε是数值稳定性的小标量。
相同的聚合一个与 GCN 中的用法相同。与 GCN 相比，GIN 在聚合中不使用归一化因子（即φ=𝐱j），并在聚合后添加残差连接，这相当于图邻接矩阵中的自连接。
2.2.3GraphSAGE
GraphSAGE 被提议作为一种归纳框架，为看不见的节点和/或子图生成具有高表示能力的特征嵌入（Hamilton 等人，2017).
可以看出，消息传递函数φ被视为具有激活的全连接层σ在相邻的嵌入上𝐱j,一个取均值，变换γ(𝐱我,𝐦我)=W1𝐱我+W2𝐦我哪里W1,W2是线性投影矩阵。由W1可以看作是缩放的残差连接。
2.3神经网络量化
量化已被广泛探索为一种降低神经网络中模型复杂性和计算延迟的方法。量化感知训练 （QAT） 通过量化前向传递中的激活，利用后向传递中的直通估计器 （STE） 来估计不可微分的量化梯度，从而最大限度地减少低精度表示的精度损失。通常，激活按照公式 5 进行量化，其中qm我n,qm一个x形成所选的可表示值范围，s是要放置的缩放因子x到所需的范围内，z是零点（浮点等效于量化空间中的值 0），括号表示舍入运算。
这分钟和麦克斯函数已到位，以表明超出指定范围的任何值都采用限制的 Fixed-Point 值。在此之后，激活可以通过以下方式进行去量化x^=(xq−z)s哪里x^是原始浮点值的近似值。
2.3.1图神经网络的量化感知训练
Degree-Quant 由 Tailor 等人提出，是将量化感知训练应用于图神经网络的首批方法之一（Tailor 等人，2020).首先，Tailor 等人认为 GNN 推理的聚合阶段是量化误差的主要来源。这种效应在度数较高的节点中观察到得更严重，这可以直观地理解，因为聚合的绝对量级随着邻居的数量而增加。高度节点的预期聚合增长会影响qm一个x和qm我n值，由于聚合结果分布中存在这些异常值，因此会降低量化分辨率。
Degree-Quant 的作者通过在伯努利分布之后的每一层随机应用保护掩码来解决量化误差问题（Tailor 等人，2020).受保护节点以浮点方式运行，而非受保护节点以定点方式运行。节点的保护概率是其程度的函数，在可参数化的范围内插值[pm我n,pm一个x]，其中具有最小/最大相邻要素计数的图形节点被分配了极限概率。
3建筑
图 1：充足顶层图。数据包通过聚合引擎的 Network-on-Chip（以绿色显示）中的维度顺序路由传播，并沿对角线驱动到 Transformation Engine 的脉动阵列（以红色显示）中。虚线表示控制流接口，而实线表示单元之间的数据流。节点嵌入是通过 HBM 获取的，而指令则存储在 DRAM 中。
如图 1 所示，AMPLE 由以下功能单元组成，具有各自的功能。
- •
节点指令解码器 （NID）：与主机设备通信并驱动其他功能单元将工作安排到加速器上。
- •
预取器：获取层权重和相邻特征嵌入并存储到本地存储器（分别为权重库和特征库）中。
- •
聚合引擎 （AGE）：通过片上网络架构对节点的所有邻居执行排列不变聚合功能。
- •
Aggregation Buffer （ABF）：包含 AGE 生成的聚合特征嵌入的存储元素。
- •
特征转换引擎 （FTE）：通过在 Weight Bank 中的权重和聚合缓冲区中的聚合结果之间执行矩阵乘法来计算每个节点的更新特征嵌入。
3.1通过 Node Instruction Decoder 进行事件驱动编程
表 2：节点记分板在运行时的示例状态，其中节点块处于各种状态。邻接列表和更新的功能指针指示内存地址，分别从中获取相邻节点 ID 列表和写入更新的功能嵌入。precision 字段指示在运行时分配哪些算术核心。
| 槽 | 节点 ID | 精度 | 州 | 邻居 | 邻接列表指针 | 更新的功能指针 |
|---|---|---|---|---|---|---|
| 0 | 267 | 浮 | 转型 | 32 | 0x3BC90188 | 0x4FE8B774 |
| 1 | 268 | 浮 | 集合体 | 8 | 0xCAF5C03F | 0xE672109F |
| … | … | … | … | … | … | … |
| 63 | 330 | int4 | 预取 | 1 | 0x78E26A27 | 0xA4D89ED9 |
AMPLE 和主机之间的通信由节点指令解码器 （NID） 处理，它是一个由可配置数量的节点块组成的内存映射寄存器组。如表 2 所示，每个节点数都包含执行节点聚合和转换步骤所需的信息，并维护一个指示每个节点状态的状态机。算法 1 显示了主机如何卸载工作，主机与加速器同时运行。首先，NID 使用许多全局和分层参数进行编程，包括节点/特征计数和聚合函数。随后，主机对 nodeslots 进行编程并更新 mask 中的值一个v一个我l一个ble_nodeslots∈{0,1}n哪里n是 nodeslots 的数量。在对节点进行编程时，加速器会对先前编程的节点执行聚合和转换。这一个v一个我l一个ble_nodeslots然后，当计算完成时，Accelerator 将独立置低 mask。因此，加速器支持节点级、事件驱动的计算范式。请注意，1′和0′分别表示充满 1 和 0 的掩码。
对 nodelot 进行编程后，NID 会驱动 Prefetcher、AGE 和 FTE 执行计算，并在每个功能步骤后更新节点的内部状态机。不需要主机的进一步干预，并且在步骤 7 之后发送中断以指示 nodeslot 可以重用。应该注意的是，节点在 nodeslots 中的编程顺序并不意味着任何优先级或时间相关性。典型的图形数据集通常显示每个节点的执行时间差异很大，具体取决于相邻节点计数和数值精度。每当 nodeslot 完成计算时，主机都可以立即使用下一个节点对其进行重新编程。这种事件驱动的控制流要求主机与加速器同时运行，以监控其状态并在资源可用时推动进一步的工作。在 NID 中，并发运行的节点通过循环仲裁提供服务，以授予对聚合和转换引擎中共享资源的访问权限。
3.2混合精度算术
图 2：配置了三种受支持的精度的 AGE 的微架构。NID 请求驱动聚合管理器 （AGM），后者从 Feature Bank 接收获取的嵌入（参见图 1）。然后，这些将通过网络传输到聚合核心 （ACC）。然后，聚合结果由 Buffering Manager （BM） 缓冲。
AGE 和 FTE 中的计算单元是局部同质的，这意味着每个处理元素都支持单个数值精度。在聚合引擎中，这些被安排在由异构处理元素网格组成的片上网络 （NoC） 架构中，其中分配给每个精度的 PE 的比率可以根据应用要求在编译时进行配置。每个 PE 都耦合到负责通过网络传输数据包的路由器。每个数据包都由一个携带路由有效负载的 head flit、携带数据的任意数量的 body flit 和一个 tail flit 组成。由于不同精度的 PE 之间不需要通信，因此这些 PE 被放置在隔离的子网中，如图 2 所示，这有助于减少数据包拥塞。
如第 1 节所述，在计算节点度数变化较大的图时，通过双缓冲机制的静态流水线会导致流水线间隙，因为低度数节点必须等待高度节点释放资源。在 AGE 中，通过根据节点的特征计数和精度在每个聚合子网络内动态分配处理元素，可以缓解这种情况。因此，nodeslots 分配的资源独立于任何其他正在进行的工作负载，这些资源可以在完成后立即重用，从而形成事件驱动的编程模型。
3.3大图处理
图 3：Feature Bank 中的 Fetch Tags 在两个阶段的过程中发出并发内存访问请求;首先，相邻节点 ID 的列表存储在地址队列中，然后这些 ID 用作相邻特征嵌入的指针，这些嵌入存储在 Message Queue 中。
对大型图的推理由 Prefetcher 中的 Feature Bank 启用，其中包含 NID 中每个节点的名为 “Fetch Tag” 的存储元素。一个包含可参数化数量的 Fetch Tag 的组与 Alveo U280 卡上的每个 HBM bank 耦合，这意味着多达 32 个 Fetch Tag 可以并发访问内存资源，从而缓解与稀疏图形数据相关的固有内存受限性。在每个 Fetch Tag 组中，使用循环仲裁授予对 HBM 库的访问权限。
Feature Bank 通过其部分响应机制支持大型图形用例。对于程度高于 Fetch Tag 容量的节点，Fetch Tag 会填充 Message Queue，并直接解除阻塞 AGE 以开始聚合过程。聚合开始后，Fetch Tag 将重新启用并继续获取剩余的邻居，从而隐藏内存访问延迟。这种机制降低了每个 nodeslot 的存储要求，允许在 Feature Bank 中增加 Fetch Tag 的数量，即更深的节点并行性。
4实验结果
部署了三个基础 GNN 模型来评估具有不同架构的加速器，如表 3 所示。有关每个模型的更新规则，请参阅第 2 节。此外，还选择了 6 个图形数据集，前 3 个是小型引文网络，后 3 个是较大的社交媒体图形。表 4 显示了每个评估数据集的节点数和平均节点度数 - 后者充当图形稀疏度的指标，稀疏度和平均度数之间呈反比关系。
表 3：用于对加速器进行基准测试的 GNN 模型。残差连接表示在聚合或转换步骤之后添加节点的原始嵌入。
| 型 | 集合体 | 残余 | 正常化 |
|---|---|---|---|
| GCN 系列 | 和 | ✗ | 集合体 |
| 琴酒 | 和 | 集合体 | ✗ |
| GraphSAGE | 意味 着 | 转型 | 转型 |
表 4：用于基准测试的数据集。DQ ratio 显示 DegreeQuant 算法映射到浮点精度的节点比率，其余节点在 int8 中运行。
| 名字 | 节点 | 平均度数 | 特征 | DQ 比率 | |
|---|---|---|---|---|---|
| 铬 | 科拉 | 2,708 | 3.9 | 1,433 | 2.1 % |
| CS 系列 | 引用先知 | 3,327 | 2.7 | 3,703 | 2.7 % |
| 铅 | 公共医学 | 19,717 | 4.5 | 500 | 2.9 % |
| 佛罗里达州 | Flickr的 | 89,250 | 10.0 | 500 | 0.2 % |
| RD | Reddit 网站 | 232,965 | 99.6 | 602 | 2.7 % |
| 一岁 | 嗥 | 716,847 | 19.5 | 300 | 0.4 % |
图 4：与在 RTX A6000 GPU 和 AMPLE 模拟上获得的 Intel Xeon CPU 基线相比，推理加速。GPU 显示的平均加速比为29.8×,37.8×和26.7×分别跨 GCN、GIN 和 GraphSAGE 的所有数据集。AMPLE 的等效加速为361.3×,285.8×和81.7×. 表 5：使用单层 GCN 模型评估的数据集的推理时间。平均延迟报告超过 100 次迭代。
| CPU （Intel Xeon） | 图形处理器 （RTX A6000） | 充足的@200MHz | ||||||||
| 意味 着 | 吞吐量 | 意味 着 | 吞吐量 | 意味 着 | 吞吐量 | 延迟 | 延迟 | |||
| 延迟 [ms] | [节点/MS] | 延迟 [ms] | [节点/毫秒] | 延迟 [ms] | [节点/毫秒] | 增益 （CPU） | 增益 （GPU） | |||
| 科拉 | 244.4 | 11.1 | 7.2 | 376.3 | 0.246 | 11,022.0 | 994.8× | 29.3× | ||
| 引用先知 | 244.3 | 13.6 | 10.1 | 330.0 | 0.294 | 11,318.6 | 831.2× | 34.3× | ||
| 公共医学 | 362.4 | 54.4 | 4.8 | 4,099.5 | 1.617 | 12,193.2 | 224.1× | 3.0× | ||
| Flickr的 | 475.4 | 187.8 | 14.5 | 6,146.2 | 7.227 | 12,350.0 | 65.8× | 2.0× | ||
| Reddit 网站 | 953.3 | 244.4 | 171.0 | 1,362.0 | 24.6 | 9,463.6 | 38.7× | 6.9× | ||
| 嗥 | 760.8 | 942.2 | 110.9 | 6461.6 | 57.5 | 12,471.7 | 13.2× | 1.9× | ||
| 平均 | 506.8 | 242.2 | 53.1 | 3,129.3 | 15.2 | 11,469.9 | 361.1× | 12.9× | ||
4.1混合精度算术
DegreeQuant 算法用于为图形数据集中的每个节点分配精度，方法是根据节点的度数随机保护节点（参见第 2 节）。如表 4 所示，所有数据集的受保护节点比率均低于 3%，这表明加速器上的资源比例应分配给 float。然后按如下方式选择配置参数;给定两个节点组，对于 float 和 int8 节点，资源预算Rpm一个x,r（其中p∈[浮点型，int8]是数字格式，r∈[LUT、FF、BRAM、DSP]是资源类型）使用从 DegreeQuant 获取的比率分配给每个组。为 float 和 int8 合成了一个单算术变体，以及每个 nodeslot 的资源利用率Cpr是针对每个精度和资源类型估计的。最后，节点数Np对于每个精度的确定方式如等式 6 所示，其中括号表示向上舍入到最接近的整数。
由于定点内核的资源使用率较低，因此预计在受保护节点的比率较低时，资源可以分布在较多的节点块中。事实上，发现将单个 nodeslot 分配给 Floating-Point 通常足以满足任务精度的精度要求，同时最大限度地提高硬件节点并行性。
4.2性能分析
首先，每个模型在所有数据集的 Intel Xeon CPU 和 RTX A6000 GPU 上进行了基准测试，并随机初始化了节点特征和层权重。在每种情况下，平均延迟都是通过 100 次试验获得的，以考虑由于非确定性进程引起的运行时抖动。在每个预测步骤之前清空 GPU 缓存，以便延迟读数包括特征和权重的片外内存访问。GPU 预热时间不包括在内，这意味着推理时间是在驱动程序初始化完成后进行的。最后，使用 Vivado 23.1 工具流程为 Alveo U280 卡获得频率为 200MHz 的 Modelsim 19.2 仿真结果，从而获得 AGILE 上的推理延迟。如图 4 所示， AMPLE 导致与所有模型的 CPU/GPU 基线相比，平均推理时间有所改善。表 5 显示了获得的 GCN 延迟和节点吞吐量值。
5结论
这项工作介绍了 AMPLE，这是一种用于对大型图形进行 GNN 推理的 FPGA 加速器。引入了事件驱动的编程流程，并通过片上网络通信耦合动态资源分配机制，克服了节点度分布不均匀的图中与节点批处理相关的性能瓶颈。使用以节点为中心的数据预取器，我们减轻了对权重和激活的片上存储的要求，从而实现了对社交媒体图数据集的 GNN 加速。这些因素导致平均加速243×和7.2×与 CPU 和 GPU 基准相比。最后，我们提供了第一个加速节点粒度量化图的平台，展示了最佳资源映射，以较低的成本实现节点并行度的最大化，从而达到模型的准确性。