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