BiKD: Bidirectional Kernel Decomposition for Large-Scale GCNs on GPU

Abstract

Graph convolutional neural networks (GCNs) are representative graph neural network (GNN) models that can be used for analyzing and classifying nodes in graph structures. Since graph structures exhibit extremely sparse and irregular connections among many vertices, graph processing is not efficient on GPUs as GPUs are designed for accelerating regularly structured datasets. Since GCN kernels handle large feature data associated with vertices, GCN kernels exhibit extremely low efficiency on GPU. We analyze the behavior of the GCN aggregation kernel on GPU to reveal the performance hurdles of GCN kernels. In this paper, we propose an efficient GCN kernel design approach, called BiKD. We first propose a CTA-level vertex mapping approach to tackle the lower resource utilization in GPU. We reveal that the GPU’s kernel execution model is not efficient for handling unbalanced graph structures. By mapping vertices to multiple CTAs in GCN aggregation kernels, GPUs can instantly assign available resources to new CTAs without synchronization among multiple vertices. Then we propose kernel decomposition approaches to reduce the data structure size handled by a single GCN aggregation kernel. We observe GPU’s L2 cache cannot exploit inter-vertex locality since the size of feature data associated with vertices is significantly large compared to the L2 cache space. Our evaluation shows that the proposed kernel design improves GCN aggregation performance by 1.31× over GE-SpMM, 1.39× over DGL with METIS reordering (DGL-METIS), 2.11× over GNNAdvisor, and 2.22× over the baseline DGL implementation. We also observe that the proposed kernel design can improve the utilization of the GPU’s cache hierarchy dramatically.