Slice-and-Forge: Making Better Use of Caches for Graph Convolutional Network Accelerators

Mingi Yoo, Jaeyong Song, Hyeyoon Lee, Jounghoo Lee, Namhyung Kim, Youngsok Kim, Jinho Lee

Abstract

Graph convolutional networks (GCNs) are becoming increasingly popular as they can process a wide variety of data formats that prior deep neural networks cannot easily support. One key challenge in designing hardware accelerators for GCNs is the vast size and randomness in their data access patterns which greatly reduces the effectiveness of the limited on-chip cache. Aimed at improving the effectiveness of the cache by mitigating the irregular data accesses, prior studies often employ the vertex tiling techniques used in traditional graph processing applications. While being effective at enhancing the cache efficiency, those approaches are often sensitive to the tiling configurations where the optimal setting heavily depends on target input datasets. Furthermore, the existing solutions require manual tuning through trial-and-error or rely on sub-optimal analytical models. In this paper, we propose Slice-and-Forge (SnF), an efficient hardware accelerator for GCNs which greatly improves the effectiveness of the limited on-chip cache. SnF chooses a tiling strategy named feature slicing that splits the features into vertical slices and processes them in the outermost loop of the execution. This particular choice results in a repetition of the identical computational patterns over irregular graph data over multiple rounds. Taking advantage of such repetitions, SnF dynamically tunes its tile size. Our experimental results reveal that SnF can achieve 1.73x higher performance in geomean compared to prior work on multi-engine settings, and 1.46x higher performance in geomean on small scale settings, without the need for off-line analyses.

Introduction: The Memory Wall in GCNs

Graph Convolutional Networks (GCNs) are powerful for processing irregular data like social networks or molecular structures, but they present significant challenges for hardware design. Unlike traditional deep learning, where data access is predictable, GCNs involve an "Aggregation" phase—multiplying a massive, ultra-sparse graph by a dense feature matrix. This leads to two major bottlenecks:

  1. Irregular Memory Access: Hardware must constantly jump through memory to find neighbor data, rendering standard on-chip caches ineffective.
  2. The Tiling Dilemma: To improve cache efficiency, researchers use "vertex tiling" (breaking the graph into smaller chunks). However, the optimal tile size depends entirely on the specific graph and feature width. Currently, this requires manual tuning or sub-optimal static models.

The Slice-and-Forge (SnF) Approach

Slice-and-Forge (SnF) addresses these issues by reordering the computation to create repetitive, predictable data access patterns. It introduces two key innovations:

Feature Slicing Dataflow

Standard accelerators usually process one vertex and all its features at once. SnF flips this by splitting the feature matrix into vertical "slices" and placing the slice loop at the outermost level. This forces the accelerator to traverse the same irregular graph structure multiple times—once for each feature slice.

Automatic Tile Morphing

Because the graph traversal repeats across slices, SnF uses the first few rounds to "learn" the best configuration. A dedicated hardware Configuration Controller monitors cache miss rates and execution cycles in real-time to adjust tiling.

Figure 1: Comparison between conventional vertex tiling and SnF's automatic tile morphing via feature slicing.
  • Coarse Morphing: The system tries doubling or halving the number of tiles to find a global sweet spot.
  • Fine Morphing: It identifies specific "hot" (dense) regions of the graph and applies smaller, specialized tiles to maximize cache hits, while leaving sparser regions in larger tiles.

Experimental Evaluation

The authors evaluated SnF against seven large-scale real-world datasets, including social graphs (Pokec, YouTube) and citation networks (Microsoft Academic Graph).

Performance and Efficiency

SnF achieved a geomean speedup of 1.73× over prior state-of-the-art accelerators (like HyGCN and GCNAX) in multi-engine configurations. By significantly reducing expensive DRAM accesses, it also reduced energy consumption by up to 53% on dense datasets like Reddit.

Figure 3: Normalized speedup across different tiling configurations, showing how SnF (red circles) automatically identifies near-optimal tile sizes.

As shown in Figure 3, the optimal number of vertex tiles varies significantly between datasets (e.g., Pokec vs. Citation) and feature widths (|F|=32 vs. |F|=128). SnF's automatic morphing logic consistently reaches over 95% of the performance of an "ideal" manually-tuned configuration.

Discussion and Limitations

The core insight of SnF is that by slicing features, chaotic memory access becomes a predictable, repeating pattern that hardware can self-optimize. While there is a slight "warm-up" overhead during the initial slices as the hardware searches for the best configuration, the cache savings on the feature matrix far outweigh the cost of re-reading graph topology for wide feature vectors.

Future work may explore 2D tiling (arbitrary rectangles) to further optimize the search space, though current 1D morphing already provides substantial gains without excessive hardware complexity.

Summary updated

Abstract

Graph convolutional networks (GCNs) are becoming increasingly popular as they can process a wide variety of data formats that prior deep neural networks cannot easily support. One key challenge in designing hardware accelerators for GCNs is the vast size and randomness in their data access patterns which greatly reduces the effectiveness of the limited on-chip cache. Aimed at improving the effectiveness of the cache by mitigating the irregular data accesses, prior studies often employ the vertex tiling techniques used in traditional graph processing applications. While being effective at enhancing the cache efficiency, those approaches are often sensitive to the tiling configurations where the optimal setting heavily depends on target input datasets. Furthermore, the existing solutions require manual tuning through trial-and-error or rely on sub-optimal analytical models. In this paper, we propose Slice-and-Forge (SnF), an efficient hardware accelerator for GCNs which greatly improves the effectiveness of the limited on-chip cache. SnF chooses a tiling strategy named feature slicing that splits the features into vertical slices and processes them in the outermost loop of the execution. This particular choice results in a repetition of the identical computational patterns over irregular graph data over multiple rounds. Taking advantage of such repetitions, SnF dynamically tunes its tile size. Our experimental results reveal that SnF can achieve 1.73x higher performance in geomean compared to prior work on multi-engine settings, and 1.46x higher performance in geomean on small scale settings, without the need for off-line analyses.
BibTeX
@inproceedings{yoo2022slice,
  author = {Mingi Yoo and Jaeyong Song and Hyeyoon Lee and Jounghoo Lee and Namhyung Kim and Youngsok Kim and Jinho Lee},
  title = {{Slice-and-Forge: Making Better Use of Caches for Graph Convolutional Network Accelerators}},
  booktitle = {PACT},
  year = {2022},
  url = {https://openreview.net/forum?id=vsQMKFZybVN},
}
Figure