Source-linked AI summary
Dual-Metric Partitioning with Adaptive Kernel Execution for Efficient GCN Acceleration
Lingling Zhang, Hang Zeng, Pengpeng Qiao, Zhiwei Zhang, Ye Yuan, Guoren Wang
TL;DR
GCN acceleration is challenged by irregular memory access, workload imbalance, and partitioning methods that overlook neighborhood connectivity. DualGCN combines degree with anonymous-random-walk density for connectivity-aware partitioning and adaptive sparse/dense execution. Across twelve real-world datasets, it reports average speedups of 2.53×, 3.8×, and 2.13× over cuSPARSE, GNNAdvisor, and ACCEL.
Problem
Existing GCN accelerators overlook neighborhood connectivity and multi-hop dependencies or use static resource strategies, limiting workload balancing and scalability.
Method
DualGCN combines node degree with anonymous-random-walk neighborhood density to partition graphs into sparse and dense regions and distribute GPU workloads adaptively.
Results
2.53×, 3.8×, and 2.13× average speedups are reported over cuSPARSE, GNNAdvisor, and ACCEL, respectively, across twelve real-world graph datasets.
Takeaways & Limitations
Jointly optimizing graph partitioning and GPU execution accelerates GCN computation across diverse graph structures and configurations.
Abstract
from arXiv · showhide
Graph Convolutional Networks (GCNs) are widely used for large graph-structured data, including social, citation, and e-commerce networks, but their deployment is constrained by irregular memory access and severe GPU workload imbalance. These challenges arise in two dimensions: width imbalance from power-law degree distributions and depth imbalance from heterogeneous neighborhood connectivity.We present DualGCN, a GPU acceleration framework addressing both dimensions through dual-metric graph partitioning and adaptive kernel execution. DualGCN combines node degree, reflecting aggregation width, with neighborhood density estimated by anonymous random walks, capturing multihop connectivity and access depth. This hybrid workload metric enables connectivity-aware partitioning of large graphs into sparse and dense regions while reducing workload imbalance from linear to logarithmic complexity. DualGCN then selects partition-specific execution strategies: sparse partitions use warp-level parallelism and coalesced memory access, whereas dense partitions exploit instruction-level parallelism to hide latency and improve GPU utilization. Experiments on twelve real-world graph datasets show that DualGCN consistently accelerates GCN computation, achieving average speedups of 2.53x, 3.8x, and 2.13x over cuSPARSE, GNNAdvisor, and ACCEL, respectively. These results demonstrate that jointly optimizing graph partitioning and kernel execution provides an effective solution for processing large-scale graph and socialnetwork workloads.
1 Introduction
GCN acceleration is constrained by irregular SpMM workloads, partitioning complexity, and GPU resource imbalance. DualGCN coordinates connectivity-aware partitioning with adaptive execution and reports substantial average speedups over three established baselines.
- SpMM consumes more than 80% of GCN training time, making it the primary target for accelerator optimization.
- Existing partitioning methods can require at least O(m^2/n) time and may overlook neighborhood interaction patterns and multi-hop aggregation dependencies.
- DualGCN coordinates graph partitioning with adaptive GPU execution to improve data locality, balance workloads, and increase GPU utilization.
- Anonymous-random-walk partitioning jointly considers connectivity and degree distributions to divide graphs into sparse and dense parts with linear-time complexity.
- 2.53×, 3.8×, and 2.13× average speedups are reported over cuSPARSE, GNNAdvisor, and ACCEL, respectively, across real-world graph datasets.
2 Background and Motivation
GCNs iteratively aggregate neighborhood information and transform features, but irregular SpMM access and heterogeneous connectivity create scalability and workload-balance challenges. These challenges motivate partitioning and execution strategies that account for both degree and neighborhood structure.
- 2.1 Graph Convolution Networks: GCN layers combine node features, aggregated neighbor features, and edge features to produce progressively broader neighborhood representations.
- 2.1 Graph Convolution Networks: SpMM often consumes over 80% of execution cycles because feature aggregation has highly irregular memory access patterns.
- 2.3 Motivation: Nodes with identical degrees can impose different two-layer workloads when one has dense connectivity and another has a star topology.
- 2.3 Motivation: Current GPU frameworks miss coordination among thread-, warp-, block-, and partition-level parallelism when mapping irregular graph workloads.
- 2.3 Motivation: Uniform memory strategies poorly fit partition characteristics: sparse regions suffer random access, whereas dense regions encounter bandwidth saturation.
- 2.3 Motivation: High-performance acceleration requires joint optimization of partitioning, workload allocation, and memory access based on graph characteristics.
3 DualGCN Framework
DualGCN combines connectivity-aware graph partitioning with specialized workload distribution for sparse and dense regions. Anonymous random walks provide a basis for capturing multi-hop structure beyond degree-based workload estimates.
- 3.1 Overview of DualGCN: DualGCN divides graph data into dense and sparse regions and applies specialized SpMM resource-management strategies to each region.
- 3.1 Overview of DualGCN: Sparse regions assign multiple rows to each GPU block, while dense regions subdivide a single row across warps.
- Theoretical Foundation: Anonymous Random Walk Analysis: Anonymous random walks quantify neighborhood-aggregation complexity beyond simple node-degree metrics by labeling nodes according to first occurrence order.
- Theoretical Foundation: Anonymous Random Walk Analysis: The distribution of unique nodes visited by length-d walks characterizes structural density within d-hop neighborhoods and bounds aggregation complexity.
- Theoretical Foundation: Anonymous Random Walk Analysis: Anonymous random walks capture multi-hop connectivity patterns that degree metrics miss, enabling more accurate workload prediction.
Dual-Metric Workload Characterization
DualGCN characterizes GCN workload using neighbor density and node degree, capturing aggregation depth and width as complementary graph properties.
- The dual-metric approach combines complementary graph properties to characterize GCN workload.
- Neighbor density captures computational depth by accounting for indirect connections that affect memory access patterns and cache efficiency.
- Node degree captures computational width by representing the immediate parallelization opportunity for neighbor aggregation.
The Dual-Metric Approach
The Dual-Metric Approach integrates degree and neighborhood density to partition workloads, reduce imbalance, and bound preprocessing and partitioning costs.
- The Dual-Metric Approach: The hybrid metric Hν = αNν + (1 − α)Dν combines neighborhood density for depth with node degree for width.Density is estimated through k anonymous random walks of length d, capturing local structure beyond immediate neighbors.
- The Dual-Metric Approach: Width imbalance arises from power-law degrees, while depth imbalance comes from heterogeneous neighborhood densities that create disparate memory access patterns.Dense neighborhoods can generate cache misses and bandwidth contention, which degree-only approaches do not capture.
- The Dual-Metric Approach: Theoretical workload imbalance decreases from O(∆) with naive partitioning to O(log ∆) with hybrid partitioning.The imbalance factor is defined as max_i W_i / avg_i W_i for block workloads W_i.
- The Dual-Metric Approach: Sorting nodes by hybrid metric and partitioning contiguous blocks bounds the maximum inter-block workload difference by O(∆log n/B).With B = Ω(∆) blocks, the resulting imbalance factor is O(log n) = O(log ∆).
- The Dual-Metric Approach: Preprocessing requires O(kd) parallel density computation, O(|V|) adaptive integration, and O(|V| log |V|) sorting and partitioning.Degree extraction from CSR row pointers takes O(1) time per vertex.
3.3 DualGCN Kernel Design and Implementation
DualGCN’s kernel uses the hybrid metric to classify nodes into sparse and dense processing paths with different parallel execution strategies.
- High-Hν blocks use dense processing with 4-way instruction-level parallelism, while low-Hν blocks use sparse processing.
Kernel Architecture Overview
The kernel distributes work across blocks, warps, and threads using the hybrid metric and its degree and density components.
- Block-level distribution follows variance-minimized partitioning to balance streaming multiprocessor computation.
- Warp allocation uses Dν, giving high-degree nodes multiple warps and allowing low-degree nodes to share warps.High-degree nodes receive ⌈row_nnz/32⌉ warps.
- Thread-level computation uses Nν, with dense neighborhoods utilizing instruction-level parallelism.
- The adaptive kernel dynamically selects sparse or dense execution modes using the hybrid metric H computed during partitioning.
Detailed Kernel Components
DualGCN selects sparse or dense processing per block, then applies workload-specific parallel execution to improve memory access, latency hiding, and kernel utilization.
- Processing Mode Selection: Each thread block selects a sparse or dense execution path using a workload threshold τ.The sparse path applies when H < τ, while the dense path applies when H ≥ τ.
- Processing Mode Selection: τ is empirically calibrated as the workload mean plus half its standard deviation.This separates irregular sparse computations from regular dense operations.
- Sparse Block Processing: Sparse processing assigns row subsets to warps and advances synchronously through feature chunks to achieve coalesced memory transactions.Features are processed in chunks of 32 elements, matching warp size and reducing divergent execution.
- Dense Block Processing with 4-Way ILP: Dense processing combines collaborative warp execution with 4-way instruction-level parallelism.Each thread processes four independent elements, overlapping memory operations with arithmetic to hide latency.
- Adaptive Execution: The dual-path architecture provides specialized treatment for sparse and dense patterns across diverse workload distributions.The design aims to maximize overall kernel performance by adapting execution to partition characteristics.
Memory Management Strategy
DualGCN combines adaptive memory-hierarchy use, coalesced access patterns, and shared-memory reductions to match sparse and dense kernel paths.
- Dense Block Processing: The dense algorithm outputs accumulated sums for four elements using a sparse values array, column indices, and dense matrix B.
- Overview: The kernel dynamically selects sparse and dense processing paths according to data characteristics.Its memory strategy targets bandwidth utilization and access-latency reduction through complementary techniques.
- Memory Hierarchy Utilization: Both paths use __ldg() for read-only data through L2 while allocating shared memory differently.The sparse path minimizes shared memory, whereas the dense path uses 512B-2KB for intermediate results.
- Coalesced Memory Access Pattern: Each thread accesses indices {i, i+Nt, i+2Nt, i+3Nt} to support coalescing and independent memory requests.The pattern also reduces shared-memory bank conflicts during reductions.
- Coalesced Memory Access Pattern: Consecutive threads access consecutive memory locations, achieving perfect coalescing.
4 Evaluation
DualGCN is evaluated on twelve graph datasets and across weight-matrix feature dimensions from 16 to 128, where it achieves substantial speedups over three GCN accelerators.
- Experimental Environment: The evaluation uses an NVIDIA GeForce RTX 3090 with CUDA 12.0 and twelve benchmark graph datasets.Sparse matrices are multiplied by dense weight matrices with 16 to 128 columns.
- Performance Evaluation: 2.53×, 3.8×, and 2.13× average speedups are achieved over cuSPARSE, GNNAdvisor, and ACCEL, respectively.Figure 5 reports faster execution across twelve datasets and feature dimensions from 16 to 128.
- Combined Evaluation: 1.48× to 6.4× speedups are achieved across all twelve datasets when the proposed partitioning is combined with DualGCN workload distribution.The results indicate independent and joint contributions from both components across feature dimensions.
5 Conclusion
DualGCN combines anonymous-random-walk graph partitioning with dual-path workload distribution to accelerate GPU-based GCN computation.
- Conclusion: DualGCN partitions graph data into sparse and dense components using anonymous random walks.
- Conclusion: Its dual-path workload distribution scheme coordinates GPU block and warp allocation with memory-access patterns.
- Conclusion: 2.53×, 3.8×, and 2.13× average speedups are reported over cuSPARSE, GNNAdvisor, and ACCEL, respectively.