Technical Papers Archive

TriBIT: Triangle Counting Using Binary Tensor Core Operations


Authors: Sixte Oriol Llenas Segura (Barcelona Supercomputing Center (BSC), Universitat Politècnica de Catalunya (UPC)) and Marc Casas Guix (Barcelona Supercomputing Center (BSC))

Abstract: The graph triangle counting (TC) problem appears frequently in scientific computing domains such as large-scale graph processing, bioinformatics or social network analysis, motivating the need for efficient TC techniques on HPC platforms. However, existing approaches deliver suboptimal end-to-end performance due to (1) high memory consumption; (2) expensive graph preprocessing overheads; and (3) substantial data movement across heterogeneous CPU-GPU platforms.

To overcome these problems, we propose TriBIT, the first TC algorithm for GPUs that (1) leverages bitmap-based compressed data structures particularly tailored to the TC problem, significantly reducing memory footprint; and (2) exploits bitwise operations in GPU Tensor Core Units (TCUs). On single-GPU scenarios, using 810 sparse graphs from the SuiteSparse Matrix Collection, TriBIT achieves geometric mean speedups ranging from 4.63× to 213.61× over state-of-the-art approaches. In multi-GPU scenarios, TriBIT processes graphs with more than 128 billion edges, achieving a throughput of 381 billion triangles per second on 32 GPUs.



Presentation: file

Back to Technical Papers Archive Listing