arXiv CS open access

Dual-Metric Partitioning with Adaptive Kernel Execution for Efficient GCN Acceleration

2026 · arxiv_cs

arXiv CS · Papers · 2026

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Dual-Metric Partitioning with Adaptive Kernel Execution for Eﬃcient GCN Acceleration Lingling Zhang1 , Hang Zeng1 , Pengpeng Qiao2⋆ , Zhiwei Zhang3 , Ye Yuan3 , and Guoren Wang3 1

arXiv:2609.01983v1 [cs.DB] 2 Sep 2026

Capital Normal University, Beijing, China {7089,2251002056}@cnu.edu.cn 2 Institute of Science Tokyo, Tokyo, Japan peng2qiao@gmail.com 3 Beijing Institute of Technology, Beijing, China {zwzhang,yuan-ye}@bit.edu.cn, wanggrbit@126.com

Abstract. 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, reﬂecting 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-speciﬁc 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.53×, 3.8×, and 2.13× over cuSPARSE, GNNAdvisor, and ACCEL, respectively. These results demonstrate that jointly optimizing graph partitioning and kernel execution provides an eﬀective solution for processing large-scale graph and socialnetwork workloads. Keywords: Graph convolutional networks · GPU acceleration · graph partitioning · sparse–dense matrix multiplication

Introduction

Graph Convolution Networks (GCNs) represent an extension of deep learning techniques to the domain of graph-structured data, enabling the processing and ⋆

Corresponding author.

L. Zhang et al.

analysis of relational information [15, 10]. GCNs excel in applications such as node classiﬁcation, recommendation systems, and traﬃc forecasting, demonstrating their versatility and eﬀectiveness in processing interconnected data. The deployment of GCNs in these applications imposes strict constraints on latency and throughput [14, 4]. Consequently, GPU platforms have become the predominant choice for designing and accelerating GCN training, owing to their ability to meet these performance demands. Building on this trend, GCN accelerators on GPUs have attracted signiﬁcant attention by focusing on GPU designs that are adaptable to graph processing. Conventional GCN accelerators execute two alternating phases [14]: an aggregation phase, in which a sparse and irregular adjacency matrix A is multiplied by a dense node feature matrix X through sparse–dense matrix multiplication (SpMM), and an update phase, which performs neural-network operations, primarily multiplication with a small dense weight matrix W. Because SpMM accounts for more than 80% of GCN training time [14, 13], most GCN accelerators focus on optimizing this operation. Existing approaches improve GCN computation through algorithmic techniques [13, 9], architecture-level optimizations [2], or combinations of both [4, 19, 16]. Algorithmic approaches reorganize or partition graph data using techniques such as runtime community detection and graph partitioning to improve workload balance and data locality under powerlaw degree distributions [13, 16]. Architecture-level approaches manage thread blocks, warps, and shared memory to mitigate workload imbalance caused by irregular graph structures [19, 9]. State-of-the-art GCN accelerators face algorithmic and architectural challenges that limit scalability and eﬃciency. Graph-partitioning frameworks based on clustering coeﬃcients or community detection incur prohibitive time com2 plexity of at least O( mn ) [6, 1], where m and n denote edge and vertex counts, respectively. To reduce this complexity, existing frameworks rely solely on node degree information from the adjacency matrix’s power-law distribution [13, 16], overlooking neighbor interaction patterns and multi-hop aggregation dependencies that aﬀect computational performance and eﬃciency. Similarly, architecturelevel frameworks employ simpliﬁed GPU resource management using static warp assignments based only on adjacency-matrix row sparsity [2], failing to adapt to runtime workload variations or jointly optimize feature-matrix dimensions and nonzero-element distributions for dynamic workload balancing and resource utilization [16, 9]. To address these challenges, we propose DualGCN, a hybrid algorithmic– architectural design that coordinates graph partitioning with adaptive GPU execution. Algorithmically, DualGCN analyzes graph connectivity patterns to partition workloads into sparse and dense regions. Architecturally, it employs an adaptive dual-path strategy that assigns blocks and warps according to feature dimensionality and nonzero-element distribution. This integrated design improves data locality, balances workloads, and increases overall GPU utilization across diverse graph structures. Our system makes the following contributions:

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

• Connectivity-aware Data Partitioning: We propose a data partitioning scheme based on anonymous random walks to eﬃciently detect and analyze neighborhood connectivity patterns. By jointly considering node connectivity and degree distributions, our method can divide the graph data into sparse and dense parts and achieve balanced partitioning with linear time complexity, signiﬁcantly improving data locality during GCN computations. • Dynamic Resource Management: We develop a dual-path workload distribution strategy that adaptively allocates blocks and warps based on workload characteristics. This DualGCN strategy achieves superior load balance and memory access eﬃciency across diverse graph structures, developed into a kernel algorithm. The kernel manages GPU resources according to the workload distribution associated with the data partitions, eﬃciently exploiting parallelism when executing the SpMM computations in GCN models. • Comprehensive Evaluation: Through extensive experiments on realworld graph datasets, we demonstrate that DualGCN outperforms the state-ofthe-art methods, such as cuSPARSE [8], GNNAdvisor [13], and ACCEL [16] by factors of 2.53×, 3.8×, and 2.13×, on average. The results validate the eﬀectiveness of our joint algorithm-architecture optimization approach in accelerating GCN computations while maintaining balanced resource utilization.

Background and Motivation

2.1

Graph Convolution Networks

Graph Convolution Networks (GCNs) process graph-structured data through iterative neighborhood aggregation and feature transformation. For graph G = (V, E) with |V | nodes and |E| edges, where each node has an F -dimensional feature vector, GCNs compute node embeddings to capture both local structure and node features. As shown in Figure 1, each GCN layer transforms (k+1) ) by combining: (i) the node’s feanode v’s embedding at layer k + 1 (hv tures from layer k; (ii) aggregated features from neighboring nodes N (v); and (iii) edge features evu connecting node )v to neighbor u. The computation is: ( (k+1)

(k)

= f hv , {(hu , evu ) | u ∈ N (v)} , where f is a learnable update func-

tion, typically a neural network. Through multiple layers (Figure 1), GCNs progressively capture wider neighborhood information, learning representations that reﬂect both local connectivity and global graph properties. GCN variants like GraphSAGE [5] and Graph Isomorphism Network (GIN) [17] employ diﬀerent aggregation functions but follow the same forward propagation model as standard GCNs. The feature aggregation phase, implemented as Sparse-Dense Matrix-Matrix Multiplication (SpMM), dominates GCN computation time—often consuming over 80% of execution cycles due to its highly irregular memory access patterns. This computational bottleneck severely limits GCN scalability and real-time deployment. Since SpMM is fundamental to all GCN architectures and represents the primary performance barrier, accelerating its execution is essential for practical GCN applications.

L. Zhang et al.

Node embedding

1 4 2 3 2 3 4 7 5 6 5 6 7

GCN layer 2 3 4

3 6

...

GCN-layer-1

Neighbor aggregation ReLU

...

GCN-layer-N Node Update

Softmax

Fig. 1. An Example of GCN General Computation Flow.

2.2

Related Work

Graph Partitioning Approaches. Recent GCN acceleration frameworks have explored graph partitioning to improve data locality and workload balance. GNNAdvisor [13] pioneered community-based partitioning combined with weight matrix dimensions for warp-level workload distribution, though it underperforms NVIDIA’s cuSPARSE [8]. GROW [6] introduced row-wise product acceleration with clustered caching for high-degree nodes, but its O(|V |2 ) partitioning complexity limits scalability. Moreover, their static partitioning criteria cannot capture heterogeneous neighborhood structures, causing suboptimal workload assignments across graph topologies and feature dimensions under rapidly changing real-world workloads. These methods demonstrate that while partitioning improves locality, computational overhead and imbalanced partitions remain signiﬁcant challenges for large-scale graphs. GPU Resource Management. Several frameworks optimize GPU resource allocation to address workload imbalance. MergePath [12] evenly distributes nonzero elements across threads but requires hardware-speciﬁc parameter tuning. GCoD [19], ACCEL [16], and MaxK-GNN [9] employ degree-based partitioning with optimized block and warp management, achieving better load balancing than static approaches. However, these methods still struggle with power-law degree distributions, where a few high-degree nodes create severe workload skew despite sophisticated scheduling strategies. Memory Optimization. MEGA [20] targets memory eﬃciency through degree-aware quantization, adaptive-package storage formats, and CondenseEdge scheduling for optimized access patterns. While these techniques reduce memory bandwidth requirements and improve cache utilization, they introduce training overhead and require complex mixed-precision hardware support. This trade-oﬀ between memory eﬃciency and computational complexity highlights the need for solutions that jointly optimize memory access and computational workload without excessive overhead.

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

2.3

Motivation

The limitations of existing GCN accelerators reveal three interdependent performance bottlenecks: data partitioning, workload allocation, and memory access patterns. Data Partitioning Challenges. Graph adjacency matrices exhibit powerlaw degree distributions and heterogeneous connectivity patterns [3, 18]. Traditional schemes consider only node degrees, overlooking connectivity. Figure 2 illustrates—nodes ’1’ and ’a’ have identical degrees but diﬀerent neighborhood structures. In a two-layer GCN, node ’1’ aggregates from a dense neighborhood while node ’a’ processes a star topology, creating imbalance despite equal degrees. Eﬀective partitioning must capture both degree distribution and connectivity patterns.

L0 L1 L2 2 2 1 3 3 6 4 4 1 2 5 5 5 3 4 6 6 (a) Node 1 and its GCN model

L0 L1 L2 b b c c a f d d a e b e e c d f f (b) Node a and its GCN model

Fig. 2. Two-layer GCN computation: (a) Node 1 with dense connectivity requires complex aggregation, (b) Node a with star topology requires simpler computation.

Workload Allocation Ineﬃciencies. GPUs oﬀer multiple parallelism levels— threads, warps, and blocks—with data parallelism across partitions. Current frameworks optimize these independently, missing coordination opportunities. The challenge is mapping irregular graph workloads to regular GPU execution patterns while maintaining load balance. Memory Access Ineﬃciencies. Existing methods apply uniform memory strategies regardless of partition characteristics [16, 9]. Sparse partitions suﬀer random access while dense partitions encounter bandwidth saturation. Adaptive strategies tailored to partition density could signiﬁcantly improve throughput. These factors form a coupled optimization space—partitioning aﬀects workload distribution, determining optimal memory patterns. High-performance GCN acceleration requires joint optimization across all dimensions, motivating our integrated approach that coordinates partitioning, workload allocation, and memory access based on graph characteristics.

L. Zhang et al.

DualGCN Framework

3.1

Overview of DualGCN

DualGCN (Graph Convolution Network Accelerator) is a framework built on two core components: data partitioning and workload distribution. The data partitioning component strategically divides graph data across GPU blocks to achieve balanced computational loads, segmenting the graph into dense and sparse regions based on node connectivity. The workload distribution component then optimizes how this partitioned data is processed, implementing specialized resource management strategies for SpMM computations. In sparse regions, each GPU block processes multiple rows using its assigned warps, while in dense regions, each block handles a single row that is further subdivided and assigned to warps - all coordinated with eﬃcient memory management. Figure 3 illustrates an overview of the DualGCN architecture for optimized SpMM operations. It demonstrates how the multiplication between a sparse matrix (Figure 3(a)) and a dense matrix (Figure 3(b)) is executed through a dual-path workload assignment strategy (Figure 3(c)). In this scheme, computational blocks are dynamically allocated: each block processes either multiple sparse rows or a single dense row, depending on the input matrix’s density characteristics.

Data partition

Workload distribution Warp1 Block

...

Warpk rowj row1 Warp1

...

... ... ...

... ...

rowj

...

Block Dense parts

row1

...

Memory

Sparse parts

Warpk

row

... ... ...

(a) Sparse matrix (b) Dense matrix (c)Dual-path Workload assignment Fig. 3. An Example of DualGCN Architecture.

3.2

Adaptive Data Partitioning

Motivation and Key Contribution: Existing graph partitioning schemes for GCN acceleration typically rely on simple heuristics (e.g., node degree alone) that fail to capture the complex computational patterns in neighborhood aggregation. We present a theoretically-grounded adaptive partitioning scheme that jointly optimizes for both structural complexity and computational load balancing, enabling eﬃcient dynamic resource allocation with provable performance bounds.

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

Theoretical Foundation: Anonymous Random Walk Analysis We employ anonymous random walks to quantify the computational complexity of neighborhood aggregation beyond simple degree metrics. An anonymous random walk iteratively traverses a graph from a node to random neighbors, labeling each node by its ﬁrst occurrence order in the sequence. Theorem 1 Let S = (ν, d) be the set of anonymous random walks after d steps, starting from node ν. Let Pd be the distribution ∑d of the number of unique nodes on the paths of these random walks. The sum i=1 iPi characterizes the structural density of the subgraph induced by all nodes µ such that dist(ν, µ) ≤ d, and provides a tighter bound on aggregation complexity than degree-based metrics alone. The proof follows from [7]. Key insight: Theorem 1 reveals that anonymous random walks capture multi-hop connectivity patterns critical for GCN computation that simple degree metrics miss, enabling more accurate workload prediction. Dual-Metric Workload Characterization We introduce a novel dual-metric approach that combines complementary graph properties: 1. Neighbor Density (Nν ): We deﬁne the neighbor density of node ν as ∑d Nν = i=1 iPi from Theorem 1. This metric captures the computational depth of neighborhood aggregation, accounting for indirect connections that impact memory access patterns and cache eﬃciency. Unlike degree-only metrics, neighbor density predicts the actual number of unique feature vectors accessed during multi-layer GCN propagation. 2. Node Degree (Dν ): While graphs typically follow power-law degree distributions [11], degree alone provides an incomplete picture. We use degree to capture computational width—the immediate parallelization opportunity for neighbor aggregation. The Dual-Metric Approach Approach Overview. We propose a dual-metric approach combining complementary measures to capture GCN workload characteristics. Our hybrid metric Hν = αNν + (1 − α)Dν integrates node degree Dν (width) with neighborhood density Nν (depth), where α is a weighting parameter. The degree metric Dν corresponds to neighbors requiring aggregation, while density Nν is computed through k anonymous random walks of length d to capture local structure beyond immediate neighbors. This enables accurate workload prediction by considering both operation quantity (degree) and memory access complexity (density). Algorithmic Strengths and Performance Guarantees. Our dual-metric approach addresses both workload imbalance dimensions simultaneously. Width imbalance from power-law degree distributions causes high-degree nodes to require

L. Zhang et al.

more parallel threads. Depth imbalance stems from varying neighborhood densities creating disparate memory access patterns—dense neighborhoods generate cache misses and bandwidth contention. Degree-only approaches miss this depth dimension, resulting in suboptimal distribution among nodes with similar degrees but diﬀerent neighborhood characteristics. Our partitioning minimizes ∑B Var({H ν : ν ∈ Blocki }) across B blocks, achieving theoretical bounds: i=1 workload imbalance reduces from O(∆) in naive partitioning to O(log ∆), where i Wi ∆ is maximum degree and imbalance is max avgi Wi for block workloads Wi (Theorem 2). Theorem 2 For a graph with maximum degree ∆ and our hybrid partitioning, the workload imbalance factor is bounded by O(log ∆) compared to O(∆) for naive i Wi partitioning, where workload imbalance is deﬁned as max avgi Wi for block workloads Wi . Proof Sketch. The proof establishes that naive (random) partitioning achieves O(∆) imbalance because high-degree nodes with workload Θ(∆) can randomly cluster in certain blocks—with some blocks receiving multiple high-degree nodes while others receive none, creating imbalance proportional to the maximum degree ∆. In contrast, our hybrid metric approach ﬁrst sorts all nodes by their combined degree-density score Hν , creating a smoothly increasing sequence where adjacent nodes have similar workloads. After sorting nodes by Hν , we have the sequence ∑n H1 ≤ H2 ≤ ... ≤ Hn . The key insight is that the total workload mass i=1 Hi = O(n · average degree) = O(n) in sparse graphs. For power-law graphs, only O(n/∆) nodes have degree ≥ ∆/2, so the workload distribution is not uniform. The steepest increase occurs where high-degree nodes appear in the sorted order. Even in the worst case where all high-degree nodes appear consecutively, the total increase over a range of ℓ = n/ log n positions is at most O(∆) ∆ log n O(∆). Therefore, the average gap per position is O(∆) = n/ ). ℓ log n = O( n When we partition this sorted sequence into B contiguous blocks, each block contains nodes with similar hybrid metric values, ensuring the maximum difference between blocks is bounded by O(n/B) × O(∆ log n/n) = O(∆ log n/B). Since the average block workload is Ω(n/B) and we choose B = Ω(∆) blocks for GPU execution, the imbalance factor becomes max/avg = O(log n) = O(log ∆), achieving logarithmic rather than linear scaling with the maximum degree. Time Complexity and Overhead Analysis. The preprocessing phase consists of four steps with well-deﬁned complexity bounds. Parallel density computation requires O(kd) time with O(|V |) processors for computing Nν across all vertices. Degree extraction from CSR row pointers takes O(1) per vertex. The adaptive integration phase, which dynamically adjusts α based on variance analysis (defaulting to 0.5), requires O(|V |) time. Finally, sorting and partitioning nodes requires O(|V | log |V |) time. The total preprocessing complexity of O(|V |(kd + log |V |)) with constants k, d = O(1) is amortized over T training epochs, yielding only |V | ) overhead per iteration. O( kd+log T

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

3.3

DualGCN Kernel Design and Implementation

Kernel Architecture Overview Our kernel leverages dual-metric partitioning for execution. The hybrid metric Hν classiﬁes nodes by degree (width) and neighborhood density (depth). High Hν blocks use dense processing with 4-way ILP; low Hν blocks use sparse processing. The architecture employs three parallelism levels. Block-level distribution follows variance-minimized partitioning for balanced SM computation. Warp-level processing assigns resources by Dν values—high-degree nodes receive multiple warps (⌈row_nnz/32⌉), low-degree nodes share warps. Thread-level computation uses Nν values, with dense neighborhoods utilizing ILP. Three principles guide execution. First, adaptive execution selects paths by partition’s Hν . Second, memory optimization matches partition characteristics— sparse uses L2 cache via __ldg(), dense allocates 512B-2KB shared memory. Third, hardware utilization follows metrics: Dν determines warps, Nν inﬂuences registers and ILP. This creates metric-aware resource allocation throughout execution. Detailed Kernel Components Our adaptive kernel architecture employs a dual-path strategy that dynamically selects sparse or dense execution modes based on workload characteristics. The mechanism uses the hybrid metric H computed during data partitioning to optimize resource utilization for each thread block. Processing Mode Selection. Upon kernel invocation, each thread block determines its execution path through the following decision criterion: { Sparse Path if H < τ Processing Mode = (1) Dense Path if H ≥ τ where the threshold τ (ProBound) is empirically calibrated as τ = µH + 0.5σH , representing the mean plus half the standard deviation of the workload distribution. This threshold eﬀectively separates irregular, sparse computations from regular, dense operations, enabling specialized optimizations for each pattern. Sparse Block Processing. Sparse partitions exhibit irregular memory access patterns and load imbalance, necessitating a specialized processing strategy. We address these challenges through a warp-feature association mechanism that prioritizes memory coalescing while maintaining computational eﬃciency. In this approach, we establish a three-tier hierarchy: (1) each warp is assigned a subset of matrix rows, (2) warps process their assigned rows for one feature at a time, and (3) all warps within a block synchronously advance through the same feature range. This synchronization ensures that threads within a warp access contiguous memory regions, achieving coalesced memory transactions. Features are processed in chunks of 32 elements, aligning with the warp size to eliminate divergent execution paths.

L. Zhang et al.

Figure 4(a) illustrates this workload distribution strategy. The left panel shows the initial assignment of data elements to three warps (warp1 , warp2 , warp3 ), with each warp managing three rows across three features (F1 , F2 , F3 ). The right panel demonstrates the feature-level parallelization phase, where rows undergo weighted aggregation with feature-speciﬁc weights (wf ), color-coded to distinguish diﬀerent computational operations.

wf1,3

wf2,1 wf2,2 wf2,3 row2,1 row2,2 row2,3 wf3,2 wf3,3 row3,1 wf3,1 row3,2 row3,3

... ... ... ... ... ... ... ... ...

(a) Warp distributions for sparse data

Dense row Warp0 Warp2 Warp11

NZ0 NZ1

NZ12 NZ13

NZ24 NZ25

...

wf1,1 wf1,2

...

row1,1 row1,2 row1,3

...

... ... ... ... ... ... ... ... ...

warp3

...

warp2

row1 row2 row3 row4 row5 row6 row7 row8 row9

...

warp1

NZ11

NZ23

NZ35

Shared memory

(b) Warp distributions for dense data

Fig. 4. Workload distribution in sparse block processing: (a) warp-to-row assignment and (b) feature-level parallel execution.

Dense Block Processing with 4-Way ILP. Dense partitions, characterized by regular access patterns and balanced workloads, beneﬁt from aggressive parallelization techniques. Our dense processing path exploits this regularity through a combination of collaborative warp execution and instruction-level parallelism (ILP). The key innovation lies in our 4-way ILP implementation, where each thread simultaneously processes four independent data elements. This design leverages the GPU’s instruction pipeline to overlap memory operations with arithmetic computations, eﬀectively hiding memory latency. Modern GPU architectures support multiple outstanding memory requests per thread, enabling concurrent data fetching while previous computations complete. This organization increases arithmetic intensity, reduces pipeline stalls, and improves occupancy without introducing synchronization overhead among threads within the warp. Algorithm 1 details our implementation strategy. Each thread maintains four independent accumulators (sums[0..3]) to eliminate data dependencies, allowing the GPU scheduler maximum ﬂexibility in instruction reordering. The strided access pattern, with stride = block_size×4, ensures that consecutive threads access consecutive memory addresses, achieving perfect memory coalescing. Additionally, all memory operations utilize __ldg() intrinsics to bypass the L1 cache and directly access the read-only data cache, optimizing bandwidth utilization for these predictable access patterns. This dual-path architecture ensures that both sparse and dense data patterns receive optimized treatment, maximizing overall kernel performance across diverse workload distributions. Memory Management Strategy

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

Algorithm 1: Dense Block Processing with 4-Way ILP Input: Thread ID tid, block size block_size, sparse values array, column indices, dense matrix B, feature index Output: Accumulated sums for four elements 1 stride ← block_size × 4; 2 sums[0..3] ← 0 ; // Initialize four accumulators 3 for k ← 0 to 3 do 4 idx ← tid + k× block_size; 5 if idx < nnz then 6 col ← __ldg(col_idx[idx]); 7 val ← __ldg(values[idx]) × __ldg(B[col][feat]); 8 sums[k] ← sums[k] + val; 9 end 10 end 11 return sums ;

Overview. Our memory management strategy addresses the fundamental challenge of maximizing memory bandwidth utilization while minimizing access latency in GPU kernels. We achieve this through three complementary techniques: adaptive memory hierarchy utilization based on data characteristics, optimized access patterns for coalesced memory transactions, and strategic use of shared memory for reduction operations. The kernel dynamically selects between sparse and dense processing paths, each with tailored memory access patterns to match the underlying data distribution. Memory Hierarchy Utilization. The kernel employs a hierarchical memory strategy that adapts to the characteristics of sparse versus dense data blocks. Table 1 summarizes the memory usage patterns for each processing path. Both paths leverage __ldg() intrinsics to access read-only data through the L2 cache, bypassing L1 to reduce cache pressure. The sparse path minimizes shared memory usage (primarily for reduction operations) while maintaining 8-10 registers per thread for basic accumulation. In contrast, the dense path allocates 512B-2KB of shared memory for intermediate results and consumes 16-20 registers per thread to maintain four independent accumulators necessary for 4-way instruction-level parallelism (ILP). This adaptive approach ensures eﬃcient resource utilization across varying data densities. Coalesced Memory Access Pattern. To maximize memory bandwidth, we implement an access pattern ensuring coalesced transactions within each warp. Each thread i accesses indices {i, i +Nt , i +2Nt , i +3Nt }, where Nt is the thread count per block. This design serves three purposes: 1. Coalescing: Consecutive threads access consecutive memory locations, achieving perfect coalescing.

L. Zhang et al. Table 1. Memory Usage Patterns in DualGCN Kernel Memory Sparse Dense Purpose Global (R) Coalesced Strided-coal. Input matrices Global (W) Atomic Atomic (red.) Output accum. Minimal 512B-2KB Reduction Shared L2 Cache __ldg() __ldg() Read-only 8-10/thr 16-20/thr Accumulators Registers Table 2. Graph Dataset Statistics Graph Nodes Edges ARTIST 50,515 1,638,396 ARXIV 169,343 1,166,243 COLLAB 235,868 2,358,104 COM-AMAZON 334,863 1,851,744 YEAST 1,710,902 3,636,546 PRODUCTS 2,449,029 123,718,280

Graph Nodes Edges AMAZON0601 403,394 5,478,357 PPA 576,289 42,463,862 TWITTER 580,768 1,435,116 YELP 716,847 13,954,819 OVCAR-8H 1,889,542 3,946,402 CITATION 2,927,963 30,387,995

2. ILP Optimization: The Nt stride enables independent memory requests, allowing concurrent servicing while arithmetic operations proceed on fetched data. 3. Bank Conﬂict Minimization: Regular patterns reduce shared memory bank conﬂicts during reductions. Adaptive Shared Memory Conﬁguration. Shared memory layout adjusts based on block dimensions. We allocate a [WPB] reduction buﬀer for partial results, with padding added for power-of-two sizes to prevent bank conﬂicts. The sparse path uses consecutive addresses for irregular data patterns. The dense path extends this across iterations, with threads advancing by blockDim between iterations (e.g., accessing [base, base+31], then [base+blockDim, base+blockDim+31]). This maintains coalesced access for larger memory regions, ensuring optimal bandwidth utilization across diverse data distributions.

Evaluation

4.1

Experimental Environment

Our experiments were conducted on a system running Ubuntu 20.04 equipped with an NVIDIA GeForce RTX 3090 GPU, using CUDA code compiled with NVCC 12.0. We evaluate SpMM performance using 12 benchmark graph datasets listed in Table 2. The SpMM computations, essential for GCN models, involve multiplying sparse matrices derived from these graphs with dense weight matrices having dimensions ranging from 16 to 128 columns. These widely-used benchmark datasets were selected for their diverse graph connectivity patterns, enabling comprehensive evaluation of our SpMM kernel optimizations for GCN workloads.

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

Ti(e ((s)

ARTIST

CUSPARSE

GNNAdvisor

AR IV

COLLAB

ACCEL 2

COM-AMAZON

DualGCN (ours) 3 2 1

AMAZON0601

PPA 20

1 1 0 0 25 50 75 100125 25 50 75 100125 25 50 75 100125 25 50 75 100125 25 50 75 100125 Di(e)sio) Di(e)sio) Di(e)sio) Dimension Dimension YELP YEAST OVCAR-8H PRODUCTS CITATION 5.0 30 100 5.0 10 20 1 2.5 2.5 5 10 25 50 75 100125 25 50 75 100125 25 50 75 100125 25 50 75 100125 025 50 75 100125 25 50 75 100125 Dimension Di(e)sio) Di(e)sio) Di(e)sio) Di(e)sio) Di(e)sio)

Time ((s)

0 25 50 75 100125 Di(e)sio) TWITTER 2

Fig. 5. The execution times of the four GCN accelerators with diﬀerent feature dimensions of the weight matrix.

Normali-ed Speedup No)malized S(eedu(

CUSPARSE ARTIST

GNNAdvisor ARXIV

ACCEL COLLAB

DualGCN_0 (ours) COM-AMAZON

DualGCN (ou)s)

AMAZON0601

PPA

2.0

1.0

0.0

TWITTER

YELP

YEAST

OVCAR-8H

PRODUCTS

0.0

2.0

1.0

0.0

CITATION

Fig. 6. The average normalized speedup of DualGCN (ours).

We evaluate DualGCN against leading GCN accelerators: NVIDIA’s cuSPARSE v12.0 [8], GNNAdvisor [13], and ACCEL [16]. While baselines use default partitioning, DualGCN employs hybrid partitioning based on anonymous random walks. Speciﬁcally, we perform 50 walks of 30 steps each to estimate neighbor density and compute a hybrid metric for partitioning graph data into sparse and dense components. Most algorithms except GNNAdvisor achieve linear partitioning complexity and support preprocessing. We measure only kernel execution time, as data transfer and preprocessing overheads are comparable across implementations and executed on CPUs. 4.2

Performance Evaluation

Figure 5 demonstrates that our proposed kernel DualGCN achieves superior performance with faster execution times across 12 datasets with column dimensions ranging from 16 to 128. Speciﬁcally, DualGCN kernel delivers average speedups of 2.53×, 3.8×, and 2.13× over cuSPARSE, GNNAdvisor, and ACCEL, respectively. These performance gains are attributed to DualGCN’s eﬃcient data partitioning scheme and optimized workload distribution, which maximize GPU platform utilization. This analysis conﬁrms that our dual-pronged approach— dividing graphs into sparse and dense components while employing strategic resource assignment—eﬀectively accelerates GCN-based applications. To isolate the eﬀect of our workload distribution strategy from data partitioning, we conducted a controlled experiment. We constructed DualGCN_0, which adopts ACCEL’s baseline partitioning technique while retaining DualGCN’s workload distribution method. Figure 6 compares ﬁve kernel implementations. Under the same partitioning scheme as ACCEL, DualGCN_0 achieves

L. Zhang et al.

at least 52% improvement and up to 4.5× speedup over existing methods. Combined with our proposed partitioning approach, the complete DualGCN achieves speedups of 1.48× to 6.4× across all 12 datasets, regardless of feature dimensions. These results demonstrate that both components independently and jointly contribute to DualGCN’s acceleration across diverse graph structures and conﬁgurations.

Conclusion

We introduce DualGCN, a novel algorithm-architecture optimization that accelerates Graph Convolutional Networks (GCNs) on GPUs. DualGCN leverages anonymous random walks to partition graph data into sparse and dense components. We implement a dual-path workload distribution scheme that enhances data locality and parallel execution in GCN models. Our kernel orchestrates workload allocation and memory access patterns across GPU blocks and warps, leveraging the partitioned structure. Experiments demonstrate DualGCN’s performance, achieving average speedups of 2.53×, 3.8×, and 2.13× over cuSPARSE, GNNAdvisor, and ACCEL, respectively.

Acknowledgments This work was supported in part by the National Natural Science Foundation of China (NSFC) under Grant No. 62302043, the Interdisciplinary Project of Capital Normal University under Grant No. 2026JCZD02, and JSPS KAKENHI under Grant No. 26K21227.

References 1. Çatalyürek, Ü.V., Deveci, M., Kaya, K., Uçar, B.: Multithreaded clustering for multi-level hypergraph partitioning. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium. pp. 848–859. IEEE (2012) 2. Chen, C., Li, K., Li, Y., Zou, X.: Regnn: A redundancy-eliminated graph neural networks accelerator. In: 2022 IEEE International Symposium on HighPerformance Computer Architecture (HPCA). pp. 429–443. IEEE (2022) 3. Fu, Q., Ji, Y., Huang, H.H.: Tlpgnn: A lightweight two-level parallelism paradigm for graph neural network computation on gpu. In: Proceedings of the 31st International Symposium on High-Performance Parallel and Distributed Computing (2022) 4. Gurevin, D., Shan, M., Huang, S., Hasan, M.A., Ding, C., Khan, O.: Prunegnn: Algorithm-architecture pruning framework for graph neural network acceleration. In: IEEE International Symposium on High-Performance Computer Architecture (HPCA) (2024) 5. Hamilton, W., Ying, Z., Leskovec, J.: Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017)

Dual-Metric Partitioning for Eﬃcient GCN Acceleration

6. Hwang, R., Kang, M., Lee, J., Kam, D., Lee, Y., Rhu, M.: Grow: A row-stationary sparse-dense gemm accelerator for memory-eﬃcient graph convolutional neural networks. In: IEEE International Symposium on High-Performance Computer Architecture (HPCA) (2023) 7. Micali, S., Zhu, Z.A.: Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics 200, 108–122 (2016) 8. Naumov, M., Chien, L., Vandermersch, P., Kapasi, U.: Cusparse library. In: GPU Technology Conference. vol. 12 (2010) 9. Peng, H., Xie, X., Shivdikar, K., Hasan, M.A., Zhao, J., Huang, S., Khan, O., Kaeli, D., Ding, C.: Maxk-gnn: Extremely fast gpu kernel design for accelerating graph neural networks training. In: Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2 (2024) 10. Qiao, P., Zhang, Z., Li, Y., Yuan, Y., Wang, S., Wang, G., Yu, J.X.: Astore: Uniformed adaptive learned index and cache for rdma-enabled key-value store. IEEE Transactions on Knowledge and Data Engineering 36(7), 2877–2894 (2024) 11. Sala, A., Zheng, H., Zhao, B.Y., Gaito, S., Rossi, G.P.: Brief announcement: revisiting the power-law degree distribution for social graph analysis. In: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (2010) 12. Shan, M., Gurevin, D., Nye, J., Ding, C., Khan, O.: Mergepath-spmm: Parallel sparse matrix-matrix algorithm for graph neural network acceleration. In: IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS) (2023) 13. Wang, Y., Feng, B., Li, G., Li, S., Deng, L., Xie, Y., Ding, Y.: {GNNAdvisor}: An adaptive and eﬃcient runtime system for {GNN} acceleration on {GPUs}. In: 15th USENIX symposium on operating systems design and implementation (OSDI 21) 14. Wang, Y., Feng, B., Wang, Z., Huang, G., Ding, Y.: {TC-GNN}: Bridging sparse {GNN} computation and dense tensor cores on {GPUs}. In: USENIX Annual Technical Conference (USENIX ATC) (2023) 15. Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., Philip, S.Y.: A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems 32(1) (2020) 16. Xie, X., Peng, H., Hasan, A., Huang, S., Zhao, J., Fang, H., Zhang, W., Geng, T., Khan, O., Ding, C.: Accel-gcn: High-performance gpu accelerator design for graph convolution networks. In: IEEE/ACM International Conference on Computer Aided Design (ICCAD) (2023) 17. Xu, K., Hu, W., Leskovec, J., Jegelka, S.: How powerful are graph neural networks? arXiv preprint arXiv:1810.00826 (2018) 18. Xu, W., Qiao, P., Liu, S., Zheng, Z., Cao, Y., Li, Z.: Continuous publication of weighted graphs with local diﬀerential privacy. Proceedings of the VLDB Endowment 18(11), 4214–4226 (2025) 19. You, H., Geng, T., Zhang, Y., Li, A., Lin, Y.: Gcod: Graph convolutional network acceleration via dedicated algorithm and accelerator co-design. In: IEEE International Symposium on High-Performance Computer Architecture (HPCA) (2022) 20. Zhu, Z., Li, F., Li, G., Liu, Z., Mo, Z., Hu, Q., Liang, X., Cheng, J.: Mega: A memory-eﬃcient gnn accelerator exploiting degree-aware mixed-precision quantization. In: 2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA). pp. 124–138. IEEE (2024)

Dual-Metric Partitioning with Adaptive Kernel Execution for Efficient GCN Acceleration

Analyze & explore related research in Conceptio

Related documents