GraphAGILE: An FPGA-Based Overlay Accelerator for Low-Latency GNN Inference

Bingyi Zhang, Hanqing Zeng, Viktor K. Prasanna

TL;DR

GraphAGILE is a novel FPGA-based "overlay" accelerator that brings software-like programmability to the complex world of Graph Neural Network (GNN) inference. By using a domain-specific instruction set and an adaptive hardware kernel, it eliminates the need for time-consuming hardware reconfiguration, achieving up to 47x speedup over CPUs and 3.9x over GPUs while maintaining the flexibility to run diverse GNN models.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) are notoriously difficult to accelerate because they sit at the intersection of two different worlds: dense linear algebra (like standard deep learning) and sparse graph processing.

Current solutions face a "flexibility vs. performance" trade-off. General-purpose processors (CPUs/GPUs) struggle with the irregular memory access patterns of sparse graph operations. On the other hand, existing FPGA accelerators are often "hard-wired" for specific models or graph structures. If you want to change your model or your graph topology, you typically have to re-synthesize the hardware—a process that can take hours. This makes them impractical for cloud environments where multiple users might run different models on the same hardware.

Methods

The authors introduce GraphAGILE, which uses an overlay approach. Think of an overlay as a "soft" processor built on top of the FPGA's physical logic that can be programmed via instructions rather than hardware gates.

Key components include:

  • Adaptive Computation Kernel (ACK): This is the heart of the hardware. It’s a unified module that can reconfigure itself on-the-fly to execute three distinct types of math: General Matrix Multiplication (GEMM), Sparse-Dense Matrix Multiplication (SpDMM), and Sampled Dense-Dense Matrix Multiplication (SDDMM).
  • Domain-Specific ISA: A 128-bit instruction set that allows a compiler to manage data movement and computation without changing the underlying hardware.
  • The GraphAGILE Compiler: A specialized toolchain that performs four critical optimizations:
  • Computation Order Optimization: It mathematically determines if swapping the order of "Aggregation" and "Linear" layers will reduce total operations.
  • Layer Fusion: It merges adjacent layers to keep data on-chip, reducing expensive trips to external memory.
  • Partition-Centric Execution: It breaks large graphs into "shards" and "fibers" that fit perfectly into the FPGA's local memory.
  • Task Scheduling: It uses double/triple buffering to overlap data transfers with actual computation, ensuring the hardware is never sitting idle.

Datasets

The system was evaluated using seven widely recognized graph datasets:

  • Small/Medium: Citeseer, Cora, Pubmed.
  • Large-scale: Flickr, Reddit, Yelp, and Amazon-Products (the latter containing over 1.5 million vertices and 264 million edges).

The authors tested these across various GNN architectures, including GCN, GAT, GIN, GraphSAGE, SGC, and models from the GraphGym library.

Key Insights and Ideas

  • The "Aha" of Order: One of the most interesting findings is that the order of operations in a GNN layer isn't fixed. The authors proved (Theorems 1 & 2) that if the aggregation function is linear, you can swap it with the weight multiplication. Depending on the feature dimensions ($f_1$ vs $f_2$), this swap can drastically reduce the number of multiplications required.
  • Unified Hardware for Heterogeneous Math: Instead of having separate modules for sparse and dense math (which leads to idle hardware), the ACK uses a systolic array structure that can be repurposed for different kernels. This "chameleon" approach maximizes hardware utilization.
  • Eliminating Reconfiguration: By moving the "intelligence" into the ISA and compiler, GraphAGILE reduces the "deployment" time from hours (for hardware synthesis) to milliseconds (for software compilation).

Key Results

  • End-to-End Latency: GraphAGILE achieved up to 47.1× reduction in latency compared to high-end CPUs and 3.9× reduction compared to GPUs (Nvidia RTX3090).
  • Hardware Efficiency: Compared to other state-of-the-art FPGA accelerators (like AWB-GCN or BoostGCN), GraphAGILE showed up to a 2.9× speedup in hardware execution time.
  • Scalability: The system successfully handled the massive Amazon-Products graph, which requires 7.2 GB of storage, by efficiently partitioning it into on-chip buffers.

Limitations and Future Work

While GraphAGILE is a major step forward for inference, the authors note several areas for growth:

  • Training: The current architecture is optimized for inference. Future versions could extend the ISA to support the backpropagation required for GNN training.
  • Dynamic Sparsity: The current compiler uses static analysis. The authors suggest that a runtime system capable of "Just-In-Time" (JIT) compilation could better exploit data-dependent sparsity that changes during execution.
  • Multi-FPGA Scaling: For truly "planetary-scale" graphs that exceed the memory of a single Alveo board, the architecture would need to be extended to support inter-FPGA communication.

Summary updated

Abstract

This article presents GraphAGILE, a domain-specific FPGA-based overlay accelerator for graph neural network (GNN) inference. GraphAGILE consists of (1) a novel unified architecture design with an instruction set , and (2) a compiler built upon the instruction set that can quickly generate optimized code. Due to the proposed instruction set architecture (ISA) and the compiler, GraphAGILE does not require any FPGA reconfiguration when performing inference on various GNN models and input graphs. For the architecture design, we propose a novel hardware module named Adaptive Computation Kernel (ACK), that can execute various computation kernels of GNNs, including general matrix multiplication (GEMM), sparse-dense matrix multiplication (SpDMM), and sampled dense-dense matrix multiplication (SDDMM). The compiler takes the specifications of a GNN model and the graph meta data (e.g., the number of vertices and edges) as input, and generates a sequence of instructions for inference execution. We develop the following compiler optimizations to reduce inference latency: 1) computation order optimization that automatically reorders the computation graph to reduce the total computation complexity, 2) layer fusion that merges adjacent layers to reduce data communication volume, 3) data partitioning with a partition-centric execution scheme that partitions the input graph to fit the available on-chip memory of FPGA, 4) kernel mapping that automatically selects execution mode for ACK, and performs task scheduling to overlap computation with data communication and achieves dynamic load balance. We implement GraphAGILE on a state-of-the-art FPGA platform, Xilinx Alveo U250. GraphAGILE can execute widely used GNN models, including GCN, GAT, GIN, GraphSAGE, SGC and other GNN models supported by GraphGym. Experimental results show that GraphAGILE achieves up to $47.1\times$ ( $3.9\times$ ) reduction in end-to-end latency, including the latency of compilation and hardware execution, compared with the state-of-the-art implementations on CPU (GPU), and achieves up to $2.9\times$ reduction in hardware execution latency compared with the state-of-the-art FPGA accelerators.
BibTeX
@article{zhang2023graphagile,
  author = {Bingyi Zhang and Hanqing Zeng and Viktor K. Prasanna},
  title = {{GraphAGILE: An FPGA-Based Overlay Accelerator for Low-Latency GNN Inference}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2023},
  url = {https://openreview.net/forum?id=PrY5VwF8BT},
}

Loading related content...

Figure