TC-GNN: Bridging Sparse GNN Computation and Dense Tensor Cores on GPUs

Yuke Wang, Boyuan Feng, Zheng Wang, Guyue Huang, Yufei Ding

TL;DR

Graph Neural Networks (GNNs) are powerful but computationally expensive due to sparse graph operations. This paper introduces TC-GNN, a novel framework that bridges sparse GNN computations with dense Tensor Cores (TCs) on GPUs. TC-GNN achieves significant speedups by intelligently translating sparse graph structures to fit the dense computation capabilities of TCs, outperforming existing state-of-the-art GNN frameworks.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) have become essential for machine learning on graph-structured data, excelling in areas like e-commerce and financial services. However, their performance is often hampered by the inherent sparsity and irregularity of graph operations, particularly in the aggregation phase, which can consume over 80% of the runtime. Existing GNN frameworks typically rely on sparse linear algebra libraries (like cuSPARSE) that run on CUDA cores. This approach fails to leverage newer, highly efficient hardware units like NVIDIA's Tensor Cores (TCs), which are optimized for dense matrix operations (GEMM). While TCs offer massive throughput improvements for dense computations, directly applying them to sparse GNNs is challenging due to memory costs and the irregular nature of sparse data, often leading to performance degradation or inefficient utilization.

Methods

TC-GNN introduces a three-pronged approach to bridge sparse GNNs and dense TCs:

  • Sparse Graph Translation (SGT): This novel technique reorganizes the sparse graph structure to fit the fixed-dimension input requirements of TCs. SGT identifies non-zero elements and condenses them into fewer, denser tiles. This is achieved by re-indexing neighbor IDs, exploiting the commonality of neighbor sharing in real-world graphs to reduce memory access overhead.
  • TCU-tailored Algorithm and GPU Kernel Design: TC-GNN designs algorithms and kernels that leverage the strengths of both CUDA cores and TCs. CUDA cores manage memory-intensive data access and thread-level operations, while TCs handle the compute-intensive GEMM operations on the dense tiles generated by SGT. This collaboration aims to maximize GPU resource utilization.
  • Framework Integration: TC-GNN is integrated into the PyTorch framework, providing a user-friendly API for defining and training GNN models, enhancing programmability and reducing the learning curve.

Datasets

The paper evaluates TC-GNN on a variety of datasets, categorized into three types:

  • Type I: Typical GNN algorithm datasets (e.g., Cora, Citeseer, Pubmed) characterized by smaller graphs but rich node embedding information.
  • Type II: Popular benchmark datasets for graph kernels (e.g., OVCAR-8H, Yeast, DD) consisting of small graphs with dense intra-graph connections.
  • Type III: Large graphs with a high number of nodes and edges and significant structural irregularity (e.g., amazon0505, artist, com-amazon, soc-BlogCatalog, amazon0601).

Key Insights and Ideas

  • Bridging Sparsity and Density is Key: The core insight is that by intelligently transforming sparse graph data, it can be made compatible with dense computation units like Tensor Cores, unlocking significant performance gains.
  • SGT is Crucial for TCU Utilization: The Sparse Graph Translation technique is fundamental. It not only makes sparse data fit TCU's dense input requirements but also significantly improves the density of non-zero elements within TCU blocks, leading to better computation intensity.
  • CUDA Cores and TCs are Better Together: A hybrid approach, where CUDA cores handle data movement and TCs perform computations, is more effective than relying solely on one or the other for sparse GNN workloads.
  • GNNs are Data-Movement Bound: The paper highlights that GNN computations, especially sparse ones, are often limited by memory access. SGT and optimized dataflows help mitigate this by improving data locality and reducing redundant memory operations.

Key Results

  • TC-GNN achieves an average speedup of 1.70× over the state-of-the-art Deep Graph Library (DGL) framework across various models and datasets.
  • The framework demonstrates significant speedups on Type I and Type III graphs, where the irregularity of sparse structures is more pronounced.
  • TC-GNN achieves high SM occupancy (averaged 85.28%), which is 21.05% higher than DGL on average.
  • Compared to PyTorch Geometric (PyG), TC-GNN shows an average speedup of 1.76× for GCN and 2.82× for AGNN.
  • The SGT technique significantly reduces the number of traversed TCU blocks (on average 67.47%).
  • The overhead of SGT is consistently low, averaging 4.43% compared to the overall training time.

Limitations and Future Work

  • TCU-specific Design: While TC-GNN is designed for TCUs, the authors suggest that the SGT technique can be adapted for other accelerators with dense MM primitives (e.g., AMD-GPUs with MatrixCore, TPUs) and even CPUs with AVX instructions.
  • Future GPU Designs: The authors anticipate future GPU designs with more TCUs per SM or more SMs on GPUs. TC-GNN can be adapted to these changes by adjusting warp-per-block configurations and parallelism strategies.
  • Distributed GNN Computation: TC-GNN can be directly incorporated into distributed sampled graph settings. For distributed full-graph settings, modifications involving inter-GPU communication techniques (like Unified Virtual Memory and NVSHMEM) would be necessary.
  • Hardware Feature Inspiration: The work suggests that future hardware could benefit from dynamic TCU input tile shapes and dynamic structural sparsity of input tiles for even higher performance.

Summary updated

Abstract

Recently, graph neural networks (GNNs), as the backbone of graph-based machine learning, demonstrate great success in various domains (e.g., e-commerce). However, the performance of GNNs is usually unsatisfactory due to the highly sparse and irregular graph-based operations. To this end, we propose TC-GNN, the first GNN acceleration framework based on GPU Tensor Core Units (TCUs). The core idea is to reconcile the "Sparse" GNN computation with the high-performance "Dense" TCUs. Specifically, we conduct an in-depth analysis of the sparse operations in mainstream GNN computing frameworks. We introduce a novel sparse graph translation technique to facilitate TCU processing of the sparse GNN workload. We implement an effective CUDA core and TCU collaboration design to fully utilize GPU resources. We integrate TC-GNN with the PyTorch framework for high programmability. Rigorous experiments show an average of 1.70X speedup over the state-of-the-art DGL framework across various models and datasets.
BibTeX
@inproceedings{wang2023tc,
  author = {Yuke Wang and Boyuan Feng and Zheng Wang and Guyue Huang and Yufei Ding},
  title = {{TC-GNN: Bridging Sparse GNN Computation and Dense Tensor Cores on GPUs}},
  booktitle = {USENIX ATC},
  year = {2023},
  url = {https://openreview.net/forum?id=ibrT192ArX},
}
Figure