← Publications
conference2021ICORE 2026 A*CORE 2023 A*CCF A

FAST: FPGA-based Subgraph Matching on Massive Graphs

Xin Jin, Zhengyi Yang, Xuemin Lin, Shiyu Yang, Lu Qin, You Peng

IEEE International Conference on Data Engineering (ICDE)

RAIDS Lab Authors

Zhengyi Yang
Zhengyi Yang
Director

Details

Year
2021
Venue
IEEE International Conference on Data Engineering (ICDE)
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Rankings
ICORE 2026 A* · CORE 2023 A* · CCF A

Research Area

Scalable Data Systems

Tags

GraphMatchingFPGA

Resources

arXiv ↗DOI ↗

Abstract

Subgraph matching is a basic operation widely used in many applications. However, due to its NP-hardness and the explosive growth of graph data, it is challenging to compute subgraph matching, especially in large graphs. In this paper, we aim at scaling up subgraph matching on a single machine using FPGAs. Specifically, we propose a CPU-FPGA co-designed framework. On the CPU side, we first develop a novel auxiliary data structure called candidate search tree (CST) which serves as a complete search space of subgraph matching. CST can be partitioned and fully loaded into FPGAs' on-chip memory. Then, a workload estimation technique is proposed to balance the load between the CPU and FPGA. On the FPGA side, we design and implement the first FPGA-based subgraph matching algorithm, called FAST. To take full advantage of the pipeline mechanism on FPGAs, task parallelism optimization and task generator separation strategy are proposed for FAST, achieving massive parallelism. Moreover, we carefully develop a BRAM-only matching process to fully utilize FPGA's on-chip memory, which avoids the expensive intermediate data transfer between FPGA's BRAM and DRAM. Comprehensive experiments show that FAST achieves up to 462.0x and 150.0x speedup compared with the state-of-the-art algorithm DAF and CECI, respectively. In addition, FAST is the only algorithm that can handle the billion-scale graph using one machine in our experiments.

Author Affiliations

Xin Jin
East China Normal University
Zhengyi Yang
University of New South Wales
Xuemin Lin
University of New South Wales
Shiyu Yang
Guangzhou University
Lu Qin
University of Technology Sydney
You Peng
University of New South Wales

BibTeX

@inproceedings{jin2021fast,
  title = {FAST: FPGA-based Subgraph Matching on Massive Graphs},
  author = {Jin, Xin and Yang, Zhengyi and Lin, Xuemin and Yang, Shiyu and Qin, Lu and Peng, You},
  url = {http://dx.doi.org/10.1109/ICDE51399.2021.00129},
  doi = {10.1109/icde51399.2021.00129},
  booktitle = {2021 IEEE 37th International Conference on Data Engineering (ICDE)},
  publisher = {IEEE},
  year = {2021},
  month = Apr,
  pages = {1452-1463}
}