| Graph plays a vital role in representing entities and their relationships in a variety of fields,such as e-commerce networks,social networks and biological networks.Given two vertices s and t,one of the fundamental problems in graph databases is to investigate the relationships between s and t.A well-studied problem in such area is k-hop constrained s-t simple path enumeration.Nevertheless,all existing algorithms targeting this problem follow the DFS-based paradigm,which cannot scale up well.Moreover,using hardware devices like FPGA to accelerate graph computation has become popular.Motivated by the above insights,in this paper,we propose the first CPUFPGA-based algorithm PEFP to solve the problem of k-hop constrained s-t simple path enumeration efficiently.On the host side,we develop a preprocessing algorithm Pre-BFS to reduce the graph size and search space.On the FPGA side in PEFP,a novel DFS-based batching technique is designed to save on-chip memory efficiently.In addition,we also adopt caching techniques to cache necessary data in FPGA BRAM(FPGA on-chip memory),which overcome the latency bottleneck brought by the read/write operations from/to FPGA DRAM(FPGA external memory).Finally,we propose a data separation technique to enable dataflow optimization for the path verification module;hence the sub-stages in that module can be executed in parallel.Comprehensive experiments on 12 real datasets show that PEFP outperforms the state-of-the-art algorithm JOIN by more than 1 order of magnitude by average,and up to 2 orders of magnitude in terms of preprocessing time,query processing time and total time,respectively. |
