  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.
