I-GCN: A Graph Convolutional Network Accelerator with Runtime Locality Enhancement through Islandization

1 INTRODUCTION

• Real-world graphs are large, sparse, and irregular, making GCN acceleration difficult; PULL and PUSH approaches face poor locality in feature or result accesses, respectively.Offline restructuring can take seconds and is unsuitable for online processing of evolving or inductive graphs.Source: §1 · pp. 1–2
• I-GCN applies online hardware graph restructuring through islandization to improve data locality and skip redundant aggregation.The paper presents this as its first work, to the authors’ knowledge, to tackle GCN acceleration’s data-locality problem through online hardware restructuring.Source: §1 · p. 2
• Islandization locates high-degree hubs and groups nodes with strong internal connections and hub-mediated external connections into islands.The Island Locator finds hubs, explores their neighbors, and incrementally identifies islands at runtime.Source: §1 · p. 2
• Processing clustered islands constrains feature and result accesses to smaller working sets, improving reuse and reducing off-chip accesses while allowing shared-neighbor aggregation to be reused.The introduction describes these as the two benefits of islandization: improved on-chip locality and reduced redundant computation.Source: §1 · p. 2
• Experimental results show I-GCN speedups over PyG- and DGL-based CPUs, PyG- and DGL-based GPUs, and prior-art GCN accelerators of 9568× and 1243×, 368× and 453×, and 5.7×, respectively.I-GCN significantly reduces off-chip accesses and prunes 38% of aggregation operations.Source: §1 · p. 2

2.1 Graph Convolutional Networks

• GCN layers perform neighbor-feature aggregation followed by combination through a local multilayer perceptron; most GCN forward propagation can be expressed in the presented matrix form.The equation uses the graph adjacency matrix, layer input features, layer weights, and a nonlinear activation.Source: §2.1 · p. 3

2.2 Design Space Exploration

• Combination-first execution reuses a sparse-dense matrix multiplication kernel for both multiplications and requires less arithmetic, so I-GCN adopts that order.The alternative is aggregation-first execution.Source: §2.2.1 · p. 3

2.2.2 Aggregation Phase.

• PULL reuses the adjacency matrix and needs smaller partial-result buffers, but scattered nonzeros can cause random feature-matrix accesses and frequent fetches.PULL row-wise processes full feature vectors, whereas PULL inner-product fetches features by channel.Source: §2.2.2 · p. 3
• PUSH can fully reuse input features through broadcasting, but scattered updates to the result matrix can require frequent off-chip fetches; islandization clusters nonzeros at runtime to address these drawbacks and expose shared-neighbor aggregation for pruning.The section also notes that PULL-based combination is preferable because its weight matrix is normally smaller and more likely to fit on-chip.Source: §2.2.2 · p. 4, §2.2.3 · p. 4

3 ALGORITHMS AND ARCHITECTURES

• The section presents I-GCN’s overall workflow and hardware architecture.This is the section’s stated first topic.Source: §3 · p. 4
• The section introduces the Island Locator’s algorithm and corresponding architecture.The Island Locator is one of the two major components named in the section overview.Source: §3 · p. 4
• The section introduces the Island Consumer’s algorithm and corresponding architecture.The Island Consumer is the other major component named in the section overview.Source: §3 · p. 4

3.1 I-GCN Overview

• Islandization groups densely connected nodes into islands linked through hubs, enabling graph processing at island and hub granularity rather than node by node.Islands are formed by nodes with strong internal connections; hubs serve as points of contact between islands.Source: §3.1.1 · p. 4

3.1.1 I-GCN Workflow.

• The Island Locator forms islands in rounds, clustering adjacency-matrix non-zeros into hub-related L-shapes and island regions along the anti-diagonal.Each round identifies hubs using thresholds and searches their neighbors; the process continues until all non-zeros are clustered.Source: §3.1.1 · p. 4
• Island Consumer processes each island as a small, dense subgraph as soon as it forms, overlapping graph restructuring with graph processing.Processing elements need not wait for all islands in a round to be formed.Source: §3.1.1 · p. 4
• Island nodes connect only within their island and to its hubs, so their associated data are fetched from off-chip once per GraphCONV layer.Hub data may be reused across islands; even when too large for on-chip storage, the method still reduces off-chip data movement.Source: §3.1.1 · pp. 4–5
• Islandization exposes repeated aggregation among shared neighbors, which the Island Consumer can recognize and skip during island processing.The paper illustrates this with an island whose nodes have intensive internal links and shared neighbors.Source: §3.1.1 · p. 5

3.2 Island Locator

• Island Locator uses hub neighbors as starting points for TP-BFS searches to find islands, with hub detection, task generation, and search running as concurrent asynchronous tasks.The algorithm repeats in rounds, adjusting the hub threshold and synchronizing the tasks at each round's start.Source: §3.2.1 · p. 5

3.2.1 Algorithm.

• Hubs are identified by degree thresholds that decrease each round; detected hubs' neighbors are queued as TP-BFS starting points to increase search parallelism.The search tracks locally and globally visited nodes to avoid redundant exploration, and stops when an island is found or the maximum island size is exceeded.Source: §3.2.1 · p. 6

3.2.2 Architecture.

• The architecture distributes hub detection across FIFOs and assigns generated search tasks to idle TP-BFS engines.Each TP-BFS engine explores adjacency data and forwards a completed island to the Island Consumer; its FSM resets when the island-size limit is exceeded.Source: §3.2.2 · p. 7

3.3 Island Consumer

• For shared neighbors in a typical island, pre-aggregating feature vectors reduces the example's accumulation work from 16 × L to 10 × L operations.The Island Consumer forwards pre-aggregated vectors to target nodes instead of repeating shared-neighbor accumulation.Source: §3.3 · p. 7

3.3.1 Algorithm.

• After combination, the Island Consumer pre-aggregates every k nodes and scans the local adjacency bitmap, choosing connected-node accumulation or subtraction based on the scan window's non-zero count.It selects the option requiring fewer operations; k is customizable.Source: §3.3.1 · p. 8

3.3.2 Architecture.

• The architecture evaluates island and inter-hub tasks, writes complete island outputs, and combines partial hub outputs through a ring network and hub partial-result cache.Inter-hub tasks are generated from an edge map to include connections not contained in islands.Source: §3.3.2 · p. 8

4 EVALUATION

• I-GCN is evaluated on a Stratix 10 SX FPGA for latency, energy efficiency, off-chip data movement, and hardware resource utilization.The evaluated models are GCN, GraphSage, and GIN.Source: §4.1 · p. 9
• The evaluation covers Cora, Citeseer, Pubmed, Nell, and Reddit, using two-layer GCN and GraphSage models and three-layer GIN models.GCN and GraphSage results distinguish original algorithm configurations from HyGCN configurations.Source: §4.1 · p. 9
• Comparisons include prior GCN and SpMM accelerators, V100 and RTX8000 GPUs, and two Intel CPUs, with CPU and GPU results from PyTorch Geometric and DGL.The section also includes figures on pruning rates with redundancy removal and hardware consumption breakdown.Source: §4.1 · p. 9, Figure 10 · p. 9, Figure 11 · p. 9

4.2 Islandization Effect

• Across four real-world graphs, islandization clusters all non-zeros into anti-diagonal and L-shaped regions within several rounds.The effect is more pronounced on NELL, whose adjacency matrix is sparsest and graph has stronger component structures.Source: §4.2 · p. 9

4.3 Island-based Redundancy Removal

• 38% of aggregation operations are skipped by reusing shared-neighbor work, with no accuracy loss.Because aggregation accounts for 23% of operations on average in combination-first calculation, 9% of total operations can be eliminated and theoretical latency is lowered by 9%.Source: §4.3 · pp. 9–10

4.4 Hardware Consumption

• The Island Locator accounts for 34% of accelerator resources, while the Island Consumer accounts for the remaining 66%.The breakdown is for an I-GCN with 4K MAC units and 64 TP-BFS Engines; LUTs and Flip-Flops are normalized to ALMs.Source: §4.4 · p. 10

4.5 Comparison with Lightweight Reordering

• Reordering latency alone exceeds I-GCN’s end-to-end inference latency by more than 100× on Cora, Citeseer, and Pubmed.The comparison uses six baselines that run lightweight graph reordering on a 64-thread Xeon Gold 6226R CPU before AWB-GCN inference.Source: §4.5 · p. 10
• I-GCN clusters non-zeros into L-shaped regions and the anti-diagonal, while reordering baselines leave outlying non-zeros.Those outliers introduce overhead for special handling.Source: §4.5 · p. 10

4.6.1 Off-chip Data Movement.

• Figure 14(A) compares normalized off-chip accesses for I-GCN, AWB-GCN, HyGCN, and a PyG CPU using GCN-Algo and GCN-Hy.The counts assume the adjacency and input feature matrices start off-chip; they may be partly or fully on-chip when memory is not fully occupied.Source: §4.6.1 · p. 10

4.6.2 Latency.

• I-GCN averages 5.7× speedup over GNN accelerators HyGCN and AWB-GCN, and 16× over SIGMA.The cross-platform latency comparison includes CPU and GPU implementations using PyG and DGL.Source: §4.6.2 · p. 10
• I-GCN provides 9568× speedup over the PyG-based E5-2680-v3 CPU and 1243× over the DGL-based E5-2683-v3 CPU.It averages 368× over PyG-based RTX8000 and V100 GPUs and 453× over the DGL-based V100.Source: §4.6.2 · p. 10
• For a fair comparison with AWB-GCN, I-GCN uses 4096 floating-point MAC units at 330MHz and comparable FPGA ALM resources.HyGCN uses 4608 fixed-point MAC units at 1GHz.Source: §4.6.2 · p. 10

5 RELATED WORK

• Earlier GNN accelerators use specialized traversal, matrix, scheduling, and aggregation modules, hybrid aggregation/combination units, or workload autotuning; G-CoS searches for matched networks and accelerators.The related work also describes systems for training and preprocessing-based locality or redundancy optimizations.Source: §5 · pp. 10–11
• I-GCN performs hardware-only graph reordering, supports static and dynamic graphs and inductive and transductive models, and skips redundant operations among arbitrary numbers of shared neighbors at runtime.The paper contrasts this with prior work and frames I-GCN as addressing data locality through online restructuring.Source: §5 · p. 11
• Lightweight graph reordering can incur high overhead, while SlashBurn requires complex, frequent sorting and reconstruction and is not designed for parallelization.These costs make SlashBurn hardware-unfriendly for latency-constrained GNN acceleration.Source: §5 · p. 11
• HATS uses bounded-depth-first scheduling to detect coarse, large components, whereas I-GCN locates finer-grained components through hub nodes.HATS targets cache-hierarchy efficiency; I-GCN targets fast GNN inference through community identification and non-zero clustering.Source: §5 · p. 11
• General SpMM accelerators handle varied sparse matrices, while I-GCN exploits graph communities and avoids repeated computation for common neighbors.The paper argues that graph-specific features can benefit GCN processing, whereas general SpMM systems may perform better on general sparse matrices.Source: §5 · p. 11

• Experimental results show I-GCN provides speedups of 5549× over CPUs, 403× over GPUs, and 5.7× over prior-art GCN accelerators, respectively.Source: §6 · p. 11
• Islandization groups nodes with strong internal and weak external connections, enabling better on-chip reuse and easing off-chip bandwidth pressure.Source: §6 · p. 11
• Reusing aggregation for shared neighbors within an island reduces redundant computation.Source: §6 · p. 11