PaperlayerView exact revision on arXiv

Source-linked AI summary

EnGN: A High-Throughput and Energy-Efficient Accelerator for Large Graph Neural Networks

Shengwen Liang, Ying Wang, Cheng Liu, Lei He, Huawei Li, Xiaowei Li

arXiv:1909.00155v3cs.DC

TL;DR

Large, sparse graph workloads make GNN processing costly on general-purpose hardware because of irregular computation and memory accesses. EnGN uses a unified accelerator with RER dataflow, graph tiling, adaptive scheduling, and hierarchical buffering to process diverse large-scale GNNs. Across reported comparisons, it achieves substantial speedup and energy-efficiency gains over CPU, GPU, and HyGCN.

  • Problem

    Large-scale sparse GNN workloads combine irregular graph processing with neural-network computation and create substantial memory and efficiency challenges for existing hardware.

  • Method

    EnGN unifies the three main GNN propagation stages with RER dataflow and PE arrays, graph tiling, adaptive scheduling, and a hierarchical on-chip memory system.

  • Results

    EnGN reports average speedups of 1802.9X over CPU, 19.75X over GPU, and 2.97X over HyGCN, with corresponding energy-efficiency gains of 1326.35X, 304.43X, and 6.2%.

  • Takeaways & Limitations

    EnGN provides a high-throughput, energy-efficient accelerator for processing large-scale GNNs with diverse architectures and graph characteristics.

  • Takeaways & Limitations

    HyGCN is described as targeting moderate-scale graphs and not accounting for large-graph features such as skewed degree distributions and limited on-chip buffering.

Abstract

from arXiv · show

Graph neural networks (GNNs) emerge as a powerful approach to process non-euclidean data structures and have been proved powerful in various application domains such as social networks and e-commerce. While such graph data maintained in real-world systems can be extremely large and sparse, thus employing GNNs to deal with them requires substantial computational and memory overhead, which induces considerable energy and resource cost on CPUs and GPUs. In this work, we present a specialized accelerator architecture, EnGN, to enable high-throughput and energy-efficient processing of large-scale GNNs. The proposed EnGN is designed to accelerate the three key stages of GNN propagation, which is abstracted as common computing patterns shared by typical GNNs. To support the key stages simultaneously, we propose the ring-edge-reduce(RER) dataflow that tames the poor locality of sparsely-and-randomly connected vertices, and the RER PE-array to practice RER dataflow. In addition, we utilize a graph tiling strategy to fit large graphs into EnGN and make good use of the hierarchical on-chip buffers through adaptive computation reordering and tile scheduling. Overall, EnGN achieves performance speedup by 1802.9X, 19.75X, and 2.97X and energy efficiency by 1326.35X, 304.43X, and 6.2X on average compared to CPU, GPU, and a state-of-the-art GCN accelerator HyGCN, respectively.

1 INTRODUCTION

EnGN addresses the inefficiency of applying GNNs to large, sparse graphs with a specialized accelerator that supports diverse propagation stages and improves locality. Its RER dataflow, graph tiling, adaptive scheduling, and hierarchical memory target irregular accesses, while evaluations report substantial gains over CPU, GPU, and HyGCN.

  • Motivation: Large, sparse GNN workloads combine irregular graph accesses with neural-network computation, limiting CPU and GPU efficiency and stressing memory resources.Real-world graphs can be extremely large, while sparse connectivity produces poor locality and substantial computational and memory overhead.
  • Architecture: EnGN abstracts typical GNNs into feature extraction, feature aggregation, and graph update stages to support diverse architectures beyond GCNs.The unified processing model is intended to support GCN, GRN, and other GNN architectures.
  • Architecture: RER dataflow and RER PE arrays simultaneously execute feature extraction, aggregation, and vertex updates while reducing random vertex and edge accesses.The ring-connected PEs allow vertex properties to flow between PE rows and support efficient update operations.
  • Architecture: Graph property-aware dataflow dynamically reorders GNN stages as vertex-property dimensions change, reducing computation cost and decoupling mapping from vertex dimension.This reordering addresses changing feature dimensions across GNN layers.
  • Memory and scheduling: Graph tiling partitions large graphs into on-chip-sized subgraphs, while row- or column-oriented scheduling reuses vertices and reduces off-chip memory overhead.The strategy seeks high data reusability and improved locality across tiles.
  • Memory and scheduling: A three-level memory hierarchy with a degree-aware vertex cache stores frequently accessed high-degree vertices to reduce memory access cost.On the Cora graph, a high-degree vertex can be accessed 100x more often than a low-degree vertex.
  • Evaluation: 1802.9X CPU speedup, 19.75X GPU speedup, and 2.97X HyGCN speedup are reported alongside 1326.35X, 304.43X, and 6.2X energy-efficiency gains, respectively.These are average comparisons reported for EnGN against the three baselines.

2 GENERAL GNN PROCESSING MODEL

Typical GNNs differ in architecture and application but share a processing model built around feature extraction, neighbor aggregation, and update. EnGN expresses these stages as unified functions that iteratively process graph edges and vertex properties.

  • Representative GNN architectures: GCN extends convolution from regular images to graph data, using normalized adjacency, learned layer weights, and nonlinear activation.The formulation adds self-loops through ˜A = A + IN and uses ˜D for normalization.
  • Representative GNN architectures: GS-Pool aggregates neighbor properties by averaging and concatenates the result with the source vertex property during updating.This distinguishes GS-Pool from GCN-style propagation.
  • Representative GNN architectures: R-GCN extends GCN to graphs with multiple edge types by using relation-specific weights and normalized neighbor sets.The normalization constant is defined from the number of neighbors under each relation.
  • Representative GNN architectures: Gated-GCN processes source and destination vertex properties together, while GRN incorporates recurrent units such as GRUs into graph propagation.These architectures illustrate how the unified stages accommodate gated and recurrent operations.
  • Common GNN processing patterns: GNNs commonly extract compact vertex features, aggregate neighbor properties, and update the resulting features with learned parameters.These shared patterns motivate a unified processing model across diverse GNN architectures.
  • EnGN processing model: EnGN executes each layer by extracting temporary edge features, reducing them into destination properties, then applying an activation or learned update function.Its processing model represents graphs as G(V, E), iterates over edges, and updates vertex properties after aggregation.

3 MOTIVATION

GNN execution combines regular neural-network computation with irregular graph processing, creating workload imbalance and memory-access challenges for general-purpose processors and prior accelerators. EnGN is motivated by the need to address large, sparse graphs and unify these processing demands.

  • Workload characterization: GNN execution includes feature extraction, aggregation, and update stages whose time contributions vary across models and datasets.The aggregate stage involves irregular graph traversal and consumes a large portion of execution time for several workloads.
  • Workload characterization: The aggregate stage is an IO-bound workload involving irregular memory accesses over graph data.This behavior makes memory-access optimization important for high-performance GNN processing.
  • Workload characterization: GNN execution time increases with both input feature dimension and output feature dimension on the evaluated graph.The evaluation uses a synthetic graph with 0.25M vertices and 0.96M edges.
  • Hardware limitations: GPUs suffer workload imbalance, memory divergence, and branch divergence when processing large sparse graphs with irregular traversal and computation.These effects limit the ability of general-purpose processors to exploit their parallel processing resources.
  • Hardware limitations: HyGCN combines neural-network and graph-processing modules but primarily targets GCNs and does not support general GNN architectures efficiently.Its systolic array can have low resource utilization for GRN workloads with GRU or LSTM units.
  • Hardware limitations: HyGCN assumes moderate graph sizes, whereas realistic social-network and e-commerce graphs can be orders of magnitude larger.Large sparse graphs require graph partitioning and scheduling to address limited on-chip buffers and imbalanced partitions.
  • Hardware limitations: HyGCN buffers skewed graph vertices equally, potentially increasing data movement because high-degree vertices account for 50-85% of edges among analyzed datasets.Large feature dimensions further deteriorate its memory-access efficiency.
  • Hardware limitations: Separate neural-network and graph-processing modules require independent on-chip buffers and are difficult to use efficiently when stage workloads are imbalanced.This motivates a unified design that can reuse limited on-chip resources.

4 ENGN ARCHITECTURE

EnGN uses a unified processing architecture for feature extraction, aggregation, and update, with dataflows and memory mechanisms tailored to arbitrary vertex properties and sparse graph access. Its RER organization reorders edges and circulates vertex properties to improve PE utilization.

  • EnGN architecture: EnGN integrates feature extraction, aggregation, and update in a unified neural graph processing unit with a 128×16 PE array.The accelerator uses 32-bit fixed-point arithmetic and local PE register files for temporary results and inter-PE communication.
  • RER PE array: GPA dataflow decouples input vertex-property dimensions from hardware-array size, allowing continuous injection of arbitrary-dimension properties.The PE array assigns property dimensions by columns and vertices by rows.
  • RER PE array: Each PE-array row has a dedicated edge bank, while PEs in that row receive common edge-derived control signals to gather vertex properties.Broadcasting features within PE columns supports simultaneous aggregation but can otherwise increase hardware and power costs.
  • RER topology: Sparse graphs can leave many RER aggregation time slots idle because circulating vertex properties do not immediately match fetched edges.A 3×3 array requires repeated transfers to complete aggregation in the illustrated sparse-graph example.
  • RER topology: EnGN reorganizes edges in each edge bank so circulating vertex properties are used more often and aggregation idle time is reduced.The reordering changes which edges are fetched first to enable useful aggregation in earlier cycles.
  • Memory hierarchy: PE register files separate source and destination vertex values and add shadow groups for intermediate storage.SRC RF stores extracted source values, while DST RF stores destination features updated during aggregation and update.
  • Memory hierarchy: Graph tiling fits subgraphs into on-chip buffers, but vertex sets can still exceed PE register capacity and cause frequent long-latency result-bank accesses.EnGN therefore uses a degree-aware memory hierarchy to reduce result-bank overhead.

5 ENGN OPTIMIZATION

EnGN optimizes large-graph GNN processing by exploiting reorderable computation, graph tiling, and adaptive tile scheduling. These strategies reduce computation or external-memory traffic while accommodating graphs that exceed on-chip storage.

  • Observations of GNN computing: When aggregation uses sum, feature extraction and aggregation can be reordered without changing results, enabling lower-cost computation orders.This follows from matrix multiplication associativity.
  • Observations of GNN computing: The weight size is independent of input-graph size, while large input graphs dominate GNN memory accesses.This makes large-graph handling a central accelerator concern.
  • Dimension-aware stage reordering: Feature extraction requires N × F × H multiply-accumulate operations under either computation order.The differing total cost comes from the aggregate-related operations and changing property dimensions.
  • Dimension-aware stage reordering: DASR selects Eq. 6 when F exceeds H and Eq. 7 otherwise to reduce total computation.The strategy changes the instruction sequence according to input and output property dimensions.
  • Graph tiling and tile scheduling: EnGN tiles large graphs into vertex intervals and shards so processing fits within limited on-chip buffers.Tile-level processing batches vertices according to the PE-array row size.
  • Graph tiling and tile scheduling: Tile execution order affects data reuse and external-memory traffic, motivating adaptive scheduling based on F versus 2H.Column-major scheduling is preferred when F is smaller than 2H; otherwise row-major scheduling is preferred, with S-shaped reuse considered.

6 EVALUATION

The evaluation uses a cycle-accurate EnGN simulator and hardware-oriented implementation modeling. The setup includes HBM 2.0 memory characterization and synthesized accelerator configurations.

  • Experimental setup: EnGN performance is measured with a cycle-accurate simulator whose module timing is co-verified against synthesized RTL.The simulator also models HBM 2.0 accesses through Ramulator.
  • Experimental setup: HBM 2.0 is characterized at 256GB/s bandwidth in the simulator.This models the accelerator’s external-memory behavior during evaluation.
  • Experimental setup: EnGN is synthesized with Synopsys Design Compiler using a TSMC 14nm process.The configuration is reported alongside the system-configuration table.

EnGN

EnGN is evaluated as a specialized accelerator for diverse GNN models and datasets, with optimizations targeting throughput, memory use, PE utilization, and scheduling. It substantially outperforms CPU, GPU, and HyGCN baselines, while performance depends on feature dimensions, model structure, buffer pressure, and graph scale.

  • Evaluation setup: EnGN is compared with CPU-DGL, CPU-PyG, GPU-DGL, GPU-PyG, and HyGCN across GNN models and datasets.GPU-PyG is omitted on large datasets because it runs out of memory.
  • Performance: 1802.9X and 5108.4X average performance speedups are achieved over CPU-DGL and CPU-PyG, respectively.EnGN outperforms CPU across software frameworks, datasets, and GNN models.
  • Performance: 14.41X, 8.35X, and 3.33X speedups are achieved over GPU-DGL, GPU-PyG, and HyGCN on small datasets, while large-dataset speedups are 19.75X and 2.61X over GPU-DGL and HyGCN.The reported comparisons distinguish small and large graph datasets.
  • Throughput and energy: 3265.87 GOP/s average throughput reaches 79.7% of EnGN’s 4096 GOP/s peak and exceeds GPU-DGL, GPU-PyG, and HyGCN by 7.66X, 3.09X, and 2.34X.CPU-DGL and CPU-PyG reach only 29.29 GOP/s and 31.95 GOP/s, respectively.
  • Throughput and energy: EnGN’s average energy efficiency is 1326.35X higher than CPU-DGL and 213.61X higher than GPU-DGL on small datasets.The evaluation uses measured or estimated power for CPU, GPU, HyGCN, and EnGN.
  • Optimization evaluation: Edge reorganization improves performance by 5.4X on average, while dimension-aware stage reordering improves performance by 1.047X over FAU and 2.297X over AFU.The reordering strategy is especially effective on Reddit, where the output dimension increases at the final layer.
  • Optimization evaluation: EnGN’s PE utilization is independent of input vertex-property dimension because its dataflow decouples that dimension from the computing array.GPU utilization falls below 50% when the vertex-property dimension is smaller than 512.
  • Scalability analysis: EnGN scales across GNN models and datasets, but large graphs expose an aggregate-stage bottleneck and 32 × 32 arrays can be underutilized.The 32 × 32 array has more columns than the first-layer output dimension of 16.

7 RELATED WORK

Prior work provides CPU, distributed, GPU, DNN, and graph-processing systems, but these approaches do not fully support GNN computation. The cited literature motivates specialized accelerators that combine graph propagation with neural-network processing.

  • GNN software frameworks: Existing graph frameworks target traditional graph algorithms and generally lack support for GNN computation, inference, or training.NeuGraph, PyTorch Geometric, and DGL support GNN-related processing but run on power-hungry CPUs and GPUs.
  • DNN accelerators: DNN accelerators such as Diannao and EIE are designed for CNNs or RNNs and lack the graph propagation model required by GNNs.Their dataflow and compression techniques therefore do not directly address graph neural-network execution.
  • Graph accelerators: Traditional graph accelerators such as Graphicionado target graph analytics and lack the computation abstraction required by neural graph processing.This leaves a gap between graph-specific hardware and GNN workloads.

8 CONCLUSIONS

EnGN is a high-throughput, energy-efficient accelerator for large graph neural networks that combines RER processing with graph tiling and hierarchical memory support. It substantially improves performance and energy efficiency over CPUs, GPUs, and HyGCN.

  • 8 CONCLUSIONS: EnGN uses ring-edge-reduce dataflow and RER PE-arrays to process GNN feature extraction, aggregation, and update stages simultaneously.The architecture addresses arbitrary dimension changes in GNN algorithms.
  • 8 CONCLUSIONS: Graph tiling, adaptive scheduling, and a three-level memory hierarchy enable EnGN to process large graphs efficiently.These techniques cooperate to fit large graphs and use on-chip buffers effectively.
  • 8 CONCLUSIONS: 2.97X speedup and 6.2X lower energy consumption are achieved versus the state-of-the-art GCN accelerator HyGCN.The comparison reports average results for EnGN relative to HyGCN.
  • 8 CONCLUSIONS: 1802.9X and 19.75X performance gains are achieved over CPUs and GPUs on average, respectively.EnGN also achieves 1326.35X and 304.43X energy efficiency over CPUs and GPUs, respectively.
Loading 1909.00155v3…