Authors: Kaifan Jia, Yongchun Jiang, and Zhihao Ling (Institute of Software, Chinese Academy of Sciences; University of Chinese Academy of Sciences); Minghui Zhang (Institute of Software, Chinese Academy of Sciences; Hangzhou Institute for Advanced Study, UCAS); Xuran Wang and Ran Bao (Institute of Software, Chinese Academy of Sciences; University of Chinese Academy of Sciences); Haonan Zou (Institute of Software, Chinese Academy of Sciences; Hangzhou Institute for Advanced Study, UCAS); and Heng Zhang (Institute of Software, Chinese Academy of Sciences)
Abstract: Triangle counting is fundamental to graph analytics, yet GPUs face a tension between exact, irregular adjacency-list intersection and regular, inaccurate FP16 Tensor Core execution. ToT's FP16 pipeline is incorrect on 12 of 36 inputs and requires pre-kernel symbolic matching. We observe that semantic alignment alone is insufficient under heterogeneous mask density. We present BTC-TC, an exact system built around binary MMA. AND-popcount implements common-neighbor counting with 32-bit accumulation and enables online block matching. Because mask density varies, BTC-TC combines multi-granularity Bit-BSR with two-level adaptivity: it selects block geometry per graph, dispatches dense blocks to Bit Tensor Cores, and routes sparse blocks to CUDA cores. Across 36 inputs and 12 baselines on RTX PRO 6000, BTC-TC achieves the lowest post-clean end-to-end time on every input, with 1.92x geometric-mean kernel and 8.0x end-to-end speedups over ToT. It matches CPU ground truth on every input and maintains the gains on H100 and A800.
Presentation: file