RTGA (Redundancy-free Accelerator for High-Performance Temporal Graph Neural Network Inference) is an innovative hardware accelerator designed specifically for high-performance temporal graph neural network (TGNN) inference. As graph data dynamically evolves in many practical applications, traditional TGNN inference methods face issues of redundant computation and frequent external memory access, leading to performance degradation and increased energy consumption. To address these challenges, RTGA introduces a temporal tree structure and redundancy-aware execution method, aiming to effectively eliminate unnecessary computations and memory accesses. In its design, RTGA optimizes the neighbor sampling process by constructing a temporal tree, ensuring that the same subgraph is not recomputed. The architecture also leverages on-chip caching technology to enhance data locality, reducing reliance on external memory and consequently lowering latency and energy consumption. Experimental results show that RTGA significantly outperforms existing state-of-the-art solutions in TGNN inference performance, achieving an average speedup of 473.2 times and reducing energy consumption by 542.8 times compared to software solutions such as TGN and TGL.
This result, “RTGA: A Redundancy-free Accelerator for High-Performance Temporal Graph Neural Network Inference” has been published in the Design Automation Conference (DAC) 2024. DAC is one of the most authoritative international academic conferences in the field of computer system architecture and compilation, and it is also a Class A conference recommended by the China Computer Federation (CCF).
-
Paper link: https://dl.acm.org/doi/10.1145/3649329.3656241
Background and Motivation
In many real-world applications, graph structures are often dynamically changing, with vertices and edges undergoing additions, deletions, and attribute updates over time. This dynamic characteristic makes temporal graph neural networks (TGNNs) an important new research direction, as they can capture and model these complex temporal dependencies. However, existing TGNN inference solutions generally face significant issues of redundant computation and frequent external memory accesses.
Specifically, current methods typically handle the temporal neighbors of each target vertex independently, leading to the same subgraphs being resampled and computed, which increases computational burden and memory bandwidth pressure. This not only reduces inference efficiency but also results in significant increases in energy consumption. Additionally, since the features of graph vertices and edges are often too large to be effectively stored in on-chip memory, the resulting frequent external memory accesses further exacerbate latency and energy consumption.
To address these challenges, we propose a redundancy-aware execution method combined with a temporal tree structure to optimize the TGNN inference process. By deeply analyzing data access patterns and computational characteristics, we found that highly connected vertices, particularly those interacting at early timestamps, have a significantly higher probability of being sampled compared to other directed vertices. Therefore, caching the features and memory of these frequently accessed vertices in on-chip memory will help reduce the costly external memory communication issues.
Based on these findings, we designed RTGA, a redundancy-free hardware accelerator specifically built for efficient TGNN inference. RTGA utilizes a temporal tree structure to guide the redundancy-aware execution method, ensuring optimal computation and data locality, thereby achieving significantly improved TGNN inference performance. Through this design innovation, we hope to effectively reduce computational redundancy and energy consumption in the TGNN inference process, promoting advancements in related fields.
Design and Implementation
Redundancy-Aware Execution Method Based on Temporal Trees
To improve the efficiency of TGNN inference, we propose a redundancy-aware execution method based on temporal trees. Given a temporal graph G={๐ฟ(๐ก1), ๐ฟ(๐ก2), โฆ, ๐ฟ(๐ก)}, ๐ฟ(๐ก)={vi, vj, eij, t}. For a given target vertex v and a batch of temporal ordered graph updates U={(๐1, ๐ก1), (๐2, ๐ก2), โฆ, (๐๐, ๐ก๐)}.
A temporal tree ๐๐๐ฃ is defined as follows: the root vertex is the target vertex v. The child vertices and edge labels, each child vertex u in ๐๐๐ฃ corresponds to a vertex v that interacts with v via an edge ๐๐ฃ๐ข at timestamp ๐กโ๐, represented as u. Each edge in ๐๐๐ฃ is labeled by the timestamp t, indicating the temporal information of the graph.
Temporal tree structure: For each temporal ordered update (๐๐, ๐ก๐) related to v, the corresponding child vertex uti is connected to v in ๐๐๐ฃ. Mathematically, ๐๐๐ฃ can be represented as a set of triples {(๐ข, ๐ฃ, ๐ก1), (๐ข, ๐ฃ, ๐ก2), โฆ, (๐ข, ๐ฃ, ๐ก๐)}, where each triple corresponds to an edge in the tree with its respective timestamp.
Redundancy-free processing: Utilizing the temporal tree ๐๐๐ฃ in TGNN inference involves a simplified process, where the tree structure guides the sampling and updating phases. The key idea is to process target vertices in descending order of the maximum timestamp, ensuring that each relevant interaction edge is sampled only once. Specifically, for each target vertex, we traverse its temporal neighbors and sample based on the temporal tree. The sampled neighbors are then marked as visited to avoid redundancy. If the next target vertex appears in the list of already sampled neighbor vertices, it is treated as a new root vertex to traverse its temporal neighbors and sample only the unvisited temporal neighbors. This process is repeated until all target vertices are processed.
RTGA: A Redundancy-Free Accelerator for High-Performance Temporal Graph Neural Network Inference
We propose RTGA, designed for efficient temporal graph neural network inference. This architecture aims to effectively support the proposed redundancy-aware execution method and uses temporal trees to reduce unnecessary computations and off-chip communications for TGNN inference. Specifically, RTGA includes several key hardware units, namely the Temporal Tree Construction Unit (TTCU), parallel samplers, a scheduler, processors with Temporal Arithmetic Units (TAUs), a Temporal Aggregator, a control unit, and several on-chip buffers.
TTCU. TTCU constructs temporal trees in real-time for each target vertex. Specifically, TTCU includes a Graph Update Batch Scheduler (GUBS) responsible for receiving incoming batches of graph updates and efficiently distributing them to available construction units (cu). These cus can independently construct temporal trees for specific target vertices; Parallel Sampler. can efficiently perform parallel temporal neighbor sampling for multiple target vertices, utilizing the temporal trees constructed by TTCU to identify the most relevant neighbors for each target vertex; Scheduler and Processor. The scheduler efficiently distributes the sampled edge data among TAUs to ensure optimal load balancing and maximum resource utilization. The processor contains multiple TAUs for generating messages between sampled edges of target vertices; Temporal Aggregator. contains message aggregation units, vertex memory aggregation units, and activation units.
RTGA loads temporal graph data from off-chip HBM into on-chip memory. TTCU rapidly constructs the temporal tree for each target vertex by dynamically traversing the temporal graph structure, with the temporal trees stored in a temporal tree table, which uses triples to record temporal tree information. The parallel sampler selects the most relevant subgraphs for processing based on data in the temporal tree table. The scheduler is then responsible for assigning the sampled edges to processors and generating the corresponding vertex messages. The processor is equipped with multiple TAUs to generate a message for each sampled edge and record the edge features between source and target vertices in private registers (PR) to enhance data locality. The generated messages are then passed to the temporal aggregator, where the message aggregation unit is responsible for aggregating messages from various vertices to obtain the aggregated results of temporal neighbors. The vertex memory aggregation unit updates the vertex memory state with the latest information, while the activation unit applies activation functions to the aggregated data. Finally, the processed data is moved to the output buffer, where it is stored and prepared for retrieval.
Redundancy-Aware Parallel Sampling
To reduce latency in the temporal tree construction and graph sampling during graph updates, four phases are employed: graph updates, incremental tree construction, temporal tree updates, and redundancy-aware sampling. In the graph update phase, TTCU quickly ingests incoming graph updates using a high-bandwidth memory interface and efficient data parsing modules, recording them in tables. In the incremental tree construction phase, TTCU retrieves them and uses multiple cus to incrementally construct and update the temporal tree in parallel. Each cu operates independently, focusing on different parts of the graph to ensure effective processing of updates without unnecessary delays. After constructing the temporal tree, the temporal tree update phase uses high-speed interconnects and efficient synchronization primitives to transfer the updated tree structure and related data to the parallel sampler. In the redundancy-aware sampling phase, multiple sampling units are utilized for efficient, redundancy-free neighborhood sampling. Each sampling unit is equipped with a tree traversal engine that implements finite state machines (FSMs) and address generation units (responsible for generating memory addresses to read and write tree vertices and edges) to identify relevant neighbors for each target vertex.
Temporal-Aware Data Caching
RTGA places particular emphasis on vertex strategy caching, especially for those vertices with smaller timestamps and larger degrees. The temporal-aware data caching strategy effectively identifies and prioritizes these key vertices for enhanced caching through hardware implementation. Specifically, when requesting features and vertex memory of vertex ๐ฃ, TADC first checks whether there is available space in the vertex memory and feature memory buffers. If the buffers are not full, the features and vertex memory of ๐ฃ are cached directly in the vertex memory and feature memory, respectively. Conversely, if the buffers are full, priorities are calculated based on their temporal and structural significance in the graph. After calculating priorities, the priority of ๐ฃ is compared with the priorities of currently residing vertices in the vertex memory and feature memory. If the priority of ๐ฃ is higher than that of the lowest priority vertex in the buffer, the low-priority vertex is replaced by ๐ฃ. This ensures that the most temporally and structurally important vertices are retained in the cache.
Figure 1 RTGA System Architecture
Experimental Evaluation
Figure 2 Comparison of Execution Times Among Different Solutions
Figure 3 Comparison of Off-Chip Memory Communication Counts Among Different Solutions
Figure 4 Comparison of Energy Consumption Among Different Solutions
To verify the effectiveness of RTGA in temporal graph neural network inference, we conducted comprehensive experimental evaluations on the Xilinx Alveo U280 FPGA. The experiments mainly included performance analysis, energy consumption evaluation, and comparisons with existing solutions. Below are the detailed experimental settings and results.
We compared the experimental results of the current state-of-the-art temporal graph neural network inference software solutions (TGN, TGL) and hardware solutions (BlockGNN, FlowGNN) across different datasets. Compared to TGL, BlockGNN, and FlowGNN, RTGA’s performance improvement ranges from 413.2 to 627.9 times (average 473.2 times), 62.5 to 103.9 times (average 87.4 times), 7.4 to 11.9 times (average 8.2 times), and 5.2 to 9.3 times (average 6.9 times), respectively. Our CADC strategy contributed 6.1%-9.4% to the performance improvement of RTGA. As shown in Figure 3, the communication counts of TGN, TGL, BlockGNN, and FlowGNN are on average 29.5 times, 17.4 times, 9.2 times, and 7.2 times higher than RTGA, respectively. RTGA’s energy-saving effect is 414.2x to 862.5x (average 542.8x) and 92.5x to 114.9x (average 102.2x) higher than TGN and TGL, respectively. Compared to BlockGNN and FlowGNN, RTGA’s energy-saving effect improved by an average of 9.4 times and 8.3 times.
For detailed content, please refer to
Hui Yu, Yu Zhang, Andong Tan, Chenze Lu, Jin Zhao, Xiaofei Liao, Hai Jin, and Haikun Liu. RTGA: A Redundancy-free Accelerator for High-Performance Temporal Graph Neural Network Inference. In Proceedings of the 61st ACM/IEEE Design Automation Conference, June 2024.