FASI: FPGA-friendly Subgraph Isomorphism on Massive Graphs

Subgraph isomorphism plays a significant role in many applications, such as social networks and bioinformatics. However, due to the inherent NP-hardness, it becomes challenging to compute matches efficiently in large real-world graphs. Many researchers have attempted to solve this problem with the help of new hardware. Nevertheless, most of them focus on GPU. Due to the dataflow feature and burst I/O optimization, FPGA is a potential competitor to speed up subgraph isomorphism. However, there are very few subgraph matching algorithms on FPGA. In this paper, we present an efficient FPGA-friendly Subgraph Isomorphism algorithm FASI, designed on CPU- FPGA heterogeneous platform which leverages FPGA's features. Unlike the existing FPGA-based method FAST, we adopt the worst-case-optimal-join-based pipeline design. First, we propose an FPGA-friendly data structure LPCSR for efficient access to neighbor lists. Second, we offer a joint parallelized pipeline strategy to accelerate matching process. Third, we propose a memory coalescing mechanism and a space-saving pre-allocated write back strategy. Our experiments on both synthetic and real graphs show that FASI outperforms other state-of-the-art subgraph matching algorithms on CPU, GPU and FPGA.