Graph Convolutional Networks (GCNs) have become indispensable for processing structured data in domains ranging from social network analysis to bioinformatics. However, their unique computational profile presents a significant challenge for traditional hardware. Rubik introduces a specialized hierarchical architecture designed to accelerate GCNs by decoupling and optimizing their distinct processing phases.
The GCN Hardware Challenge
GCNs are notoriously difficult to accelerate because they "entangle" two fundamentally different types of computation. As shown in the standard GCN workflow, the process consists of two primary stages:
- Graph-level Computing (Aggregation): This stage involves traversing irregular graph structures to collect information from neighboring nodes. It is inherently memory-bound, characterized by irregular access patterns and poor data reuse.
- Node-level Computing (Update): This stage uses dense matrix multiplications to update node features. It is compute-bound and closely resembles traditional deep learning workloads.
Existing hardware typically excels at only one of these. Neural Network (NN) accelerators struggle with the irregular memory "jumps" required for graph traversal, while traditional graph accelerators often lack the massive computational throughput needed for high-dimensional neural network layers.
Rubik's Hierarchical Approach
Rubik addresses this mismatch by treating these two paradigms as a hierarchy rather than a single entangled process. The architecture is built on several key innovations:
- LSH-based Graph Reordering: Rubik uses Locality-Sensitive Hashing (LSH) to reorder input graphs. By grouping nodes that share common neighbors, the system reduces the "reuse distance," ensuring that data loaded into the cache is utilized by multiple target nodes in quick succession.
- Hierarchical Architecture and Mapping: The Rubik chip consists of an array of Processing Elements (PEs) connected by a 2D-mesh Network-on-Chip (NoC). It employs a two-tier mapping strategy: at the graph level, clusters of related nodes are assigned to specific PEs to maximize local data reuse; at the node level, dense matrix operations are tiled within PE MAC arrays for maximum efficiency.
- Computation Reuse: A standout feature is the Shared Node Set Exploration. If multiple target nodes share the same neighbors, Rubik calculates the partial sum of those neighbors once and reuses it, significantly reducing redundant arithmetic operations.
Evaluation and Results
The authors evaluated Rubik using standard benchmarks (COLLAB, BZR, IMDB-BINARY, DD, REDDIT) and a high-dimensional synthetic dataset (CITESEER-S) designed to stress-test feature processing capabilities.
Key findings include:
- Energy Efficiency: Rubik is 26.3x to 1375.2x more energy-efficient than an NVIDIA Quadro P6000 GPU.
- Memory Optimization: Specialized caching and reordering eliminate up to 69% of off-chip memory accesses for models like GraphSage.
- Performance Gains: Compared to general-purpose NN accelerators like Eyeriss, Rubik provides speedups ranging from 1.3x to 14.16x.
Future Directions
While Rubik offers a massive leap in efficiency, the current design assumes a static graph structure. Future work may involve extending LSH for "on-line" reordering to support dynamic graphs (e.g., real-time social media feeds) and integrating hardware support for more complex stochastic neighbor sampling strategies used in models like PinSage.
Summary updated