Rubik: A Hierarchical Architecture for Efficient Graph Learning

Xiaobing Chen, Yuke Wang, Xinfeng Xie, Xing Hu, Abanti Basak, Ling Liang, Mingyu Yan, Lei Deng, Yufei Ding, Zidong Du, Yunji Chen, Yuan XiearXiv 2020 · arXiv

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:

  1. 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.
  2. 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.
Figure 2: The two-stage GCN computation process involving neighborhood aggregation and node feature updates.

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.
Figure 6: Rubik's strategy for exploiting graph-level data and computation reuse alongside node-level data reuse.

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

Abstract

Graph convolutional network (GCN) emerges as a promising direction to learn the inductive representation in graph data commonly used in widespread applications, such as E-commerce, social networks, and knowledge graphs. However, learning from graphs is non-trivial because of its mixed computation model involving both graph analytics and neural network computing. To this end, we decompose the GCN learning into two hierarchical paradigms: graph-level and node-level computing. Such a hierarchical paradigm facilitates the software and hardware accelerations for GCN learning. We propose a lightweight graph reordering methodology, incorporated with a GCN accelerator architecture that equips a customized cache design to fully utilize the graph-level data reuse. We also propose a mapping methodology aware of data reuse and task-level parallelism to handle various graphs inputs effectively. Results show that Rubik accelerator design improves energy efficiency by 26.3x to 1375.2x than GPU platforms across different datasets and GCN models.
BibTeX
@misc{chen2020rubik,
  author = {Xiaobing Chen and Yuke Wang and Xinfeng Xie and Xing Hu and Abanti Basak and Ling Liang and Mingyu Yan and Lei Deng and Yufei Ding and Zidong Du and Yunji Chen and Yuan Xie},
  title = {{Rubik: A Hierarchical Architecture for Efficient Graph Learning}},
  year = {2020},
  eprint = {2009.12495},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.12495},
}
Figure