GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA

技术摘要：GraphLeap

问题陈述
视觉图神经网络（ViGs）将图像表示为补丁（patch）令牌的图，利用动态的、特征驱动的邻域，在实现与 Vision Transformers（ViTs）相当的准确率的同时，具备更优的计算效率。然而，ViGs 的核心机制——即基于当前补丁特征在每一层重建$k$-近邻（$k$NN）图——造成了严重的性能瓶颈。这种动态图构建在 CPU 和 GPU 上消耗了 50–95% 的总推理时间，并且随补丁数量呈二次方（$O(N^2)$）扩展。关键在于，该过程强制了严格的顺序依赖：第$\ell$层的图必须完全构建完成后，该层的特征更新（卷积）才能开始。这种串行化阻碍了高效的并行化，并妨碍了实时部署。此外，现有的硬件加速器主要针对静态图或规则网格操作（CNNs/ViTs），未能支持动态图像图构建及完整 ViG 流水线所特有的挑战。

方法论：GraphLeap 重构
作者提出了GraphLeap，这是一种新颖的算法重构，旨在解耦跨层的图构建与特征更新，以打破顺序依赖。

• 单层前瞻（One-Layer Lookahead）： 与使用第$\ell$层的特征（必须等待上一层更新）来构建第$\ell$层的图不同，GraphLeap 使用当前层$\ell$的特征来构建第$\ell+1$层的图，同时利用由前一层特征（$\ell-1$）构建的图来执行第$\ell$层的特征更新。
• 算法转变： 在标准 ViG 中，$G^{(\ell)} = G(U^{(\ell)})$。在 GraphLeap 中，块$\ell$处的消息传递使用$\hat{G}^{(\ell)} = G(U^{(\ell-1)})$，而$U^{(\ell)}$则并发用于构建$\hat{G}^{(\ell+1)}$。
• 精度恢复： 作者承认，使用“陈旧”的图（来自前一层）可能会引入轻微的精度下降。然而，他们证明轻量级微调（30 个 epoch）足以恢复原始精度，通常能达到甚至超过基线 ViG 的性能。

系统架构：端到端 FPGA 加速器
基于 GraphLeap 算法，本文提出了首个用于视觉 GNN 的端到端 FPGA 加速器，该加速器在 AMD-Xilinx Alveo U280 上实现。该设计采用流式、层流水线架构，重叠了两个主要引擎：

1. 图构建引擎（GCE）： 一个高吞吐量引擎，用于计算膨胀$k$NN 图。它以瓦片（tiles）方式处理节点特征，使用处理单元（PE）网格进行成对距离计算，并维护最小堆以提取邻居。关键在于，它将邻居索引流式传输到下一阶段，而无需在片外内存中物化完整的边特征。
2. 特征更新引擎（FUE）： 该引擎消费流式图数据，并执行 ViG Grapher 和前馈网络（FFN）操作。它包括：
   • 收集模块（GM）： 通过交错银行（interleaved banking）和预取处理不规则的内存访问模式，以检索邻居特征。
   • 图卷积模块（GCM）： 使用脉动阵列实现最大相对聚合和线性变换，避免了节点特征与消息的显式拼接。
   • FFN 模块（FM）： 一个用于每节点更新的专业化 MLP 数据路径。

• 数据流策略： GCE 比 FUE 超前一层运行。这使得第$\ell+1$层的图构建可以与第$\ell$层的特征更新并行进行。该设计避免了$O(NK)$边特征的显式物化，仅在片上保留节点特征和小型行缓冲区。

主要贡献

1. GraphLeap 算法： 一种通用的重构方法，将动态图构建与图卷积解耦，实现了图构建与特征更新的并发执行。
2. 首个端到端 ViG 加速器： 开发了专为视觉 GNN 设计的流式、流水线 FPGA 架构，具备专用的$k$NN 图构建引擎和专用的特征更新引擎。
3. 流式$k$NN 构建： 一种用于膨胀$k$NN 图像图的高吞吐量硬件设计，其运行比特征更新超前一层，直接将邻居索引流式传输到计算流水线。
4. 高效特征更新流水线： 一个硬件引擎，利用共享的脉动 MLP 架构处理图卷积和 FFN 阶段，并通过流式缓冲区连接以处理混合的不规则和规则工作负载。

实验结果
作者在部署于 Alveo U280 FPGA 上的各向同性（Ti, S, B）和金字塔型（Py-Ti, Py-S, Py-M, Py-B）ViG 模型上评估了 GraphLeap。

• 加速比： 该方法在端到端推理中，相比 64 核 CPU 基线实现了高达95.7 倍的加速，相比 NVIDIA RTX A5000 GPU 基线实现了8.5 倍的加速。
• 延迟： 对于 224×224 分辨率的 ViG-B 模型，该加速器实现了 2.77 毫秒的端到端延迟。
• 与最先进（SOTA）的比较： 在类似的 FPGA 平台上，与最先进的 ViT 加速器（DRViT, UbiMoE）相比，GraphLeap 实现了3 倍的延迟降低，同时保持了相当的准确率。
• 准确率： 经过微调后，GraphLeap 模型的准确率恢复到原始 ViG Top-1 准确率 1.4% 以内（例如，ViG-Py-B 达到 82.34%）。

意义与主张
本文主张，GraphLeap 通过从根本上解决动态图构建的顺序瓶颈，证明了实时视觉 GNN 推理的可行性。作者认为，虽然算法重构在传统的 CPU/GPU 架构上仅带来适度的提升（1.03–1.23 倍），但当与能够利用由此产生的生产者 - 消费者流式关系的硬件协同设计时，它释放了巨大的性能潜力。这项工作激发了未来针对基于图的视觉模型的硬件 - 算法协同设计，表明将构建与卷积解耦可以在不牺牲 ViGs 自适应邻域优势的情况下，实现高效、低延迟的推理。