HiCAM: Accelerating Parallel Triangle Counting via Bit-Efficient Content-Addressable Memory on FPGA

Abstract

Triangle counting is a fundamental primitive in large-scale graph analytics, yet its execution is bottlenecked by irregular memory access patterns and limited parallelism on conventional architectures. Prior FPGA-based CAM accelerators decouple data representation from matching semantics, wasting on-chip resources and requiring decompression before search. We present HiCAM, a software-hardware co-designed FPGA overlay that unifies graph data compression and associative matching into a single compressed-domain pipeline. HiCAM introduces a parameterizable locality-aware tuple encoding that packs multiple sorted vertex IDs into fixed-width entries aligned with the DSP datapath, and co-designs a bit-efficient CAM cell that searches compressed tuples directly—without runtime decompression. To handle the skewed degree distributions of real-world graphs, HiCAM employs run-time adaptive CAM grouping that trades parallelism for storage depth on a per-vertex basis, and a two-level memory-channel-aware partitioning framework for balanced multi-channel execution. Experimental results on a diverse suite of real-world datasets demonstrate that HiCAM achieves up to 10.6x speedup and 5.8x energy reduction over state-of-the-art FPGA baselines, and outperforms optimized 32-core CPU solutions by up to 3.8x in speed and 9.0x in energy efficiency.