HiTC: High-Performance Triangle Counting on HBM-Equipped FPGAs Using HLS

Triangle counting (TC) is one of the fundamental computing patterns in graph computing and social networks. Due to its high memory-to-computation ratio and random memory access patterns, it is nontrivial to accelerate TC's performance. In this work, we propose a high-performance TC (HiTC) accelerator to speed up triangle counting on high-bandwidth memory (HBM)-equipped FPGAs via software/hardware codesign. First, we propose hardware-friendly reordering, tiling, and encoding techniques to address the random access issue and optimize bandwidth utilization. Based on that, we design a streaming-based FPGA accelerator that leverages HBM to achieve higher bandwidth and customize the computation pipeline for better computing throughput. Experiments using the SuiteSparse dataset show that our HiTC achieves a geomean speedup of 8.6x (up to 24.1x) over the Vitis TC FPGA library on the AMD/Xilinx HBM-based Alveo U280 FPGA. Compared to the software implementation on two 12-core Intel Xeon Silver 4214 CPUs, HiTC achieves a geomean speedup of 18.6x (up to 669.8x).