Xunbin Su's paper of speeding up subgraph isomorphism on FPGA “FASI: FPGA-friendly Subgraph Isomorphism on Massive Graphs” has been accepted by ICDE 2023.

Subgraph isomorphism (also known as subgraph matching) plays a significant role in
graph algorithms. Due to the inherent NP-hardness, it becomes challenging to compute matches efficiently in large real-world graphs as the graph scales up. Therefore, more and more attention is paid to using hardware to accelerate subgraph matching algorithms. Recently, there have been a lot of research works on GPU, but many of them can only deal with the small size of the data graph, which is limited by the on-chip storage space. 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. Unlike the existing FPGA-based method FAST that adopts the edge-verification strategy, we adopt the worst-case-optimal-join-based pipeline design, which exploits FPGA's dataflow feature and burst I/O optimization. Specifically, we propose an FPGA-friendly data structure LPCSR for efficient access to neighbor lists. Then, we offer a joint parallelized pipeline strategy to accelerate matching process on FPGA. Finally, we propose a memory coalescing mechanism and a space-saving pre-allocated write back strategy to further improve the performance. 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.