Triangle Counting and Truss Decomposition using FPGA

Abstract

Triangle counting and truss decomposition are two essential procedures in graph analysis. As the scale of graphs grows larger, designing highly efficient graph analysis systems with less power demand becomes more and more urgent. In this paper, we present triangle counting and truss decomposition using a Field-Programmable Gate Array (FPGA). We leverage the flexibility of FPGAs and achieve low-latency high-efficiency implementations. Evaluation on SNAP dataset shows that our triangle counting and truss decomposition implementations achieve 43.5× on average (up to 757.7×) and 6.4× on average (up to 68.0×) higher performance per Watt respectively over GPU solutions.