Subgraph isomorphism acceleration on FPGAs using High-Level Synthesis

Subgraph isomorphism (or subgraph matching) is a well-known NP-hard problem that consists of searching all the distinct embeddings of a query graph in a large data graph. It has a wide range of applications, almost in all the domains in which graph patterns reveal valuable information, especially in social network analysis, chemical compound search, and computer-aided design. Due to the relevance of the problem, starting from 1970, several algorithms have been proposed, most of which adopt a backtracking approach by recursively mapping query vertices to data vertices. However, due to the intrinsic properties of graph computations, such as irregular communication patterns and little spatial and temporal locality, these algorithms cannot be easily accelerated in hardware. An alternative approach to address the problem consists of seeing the query graph as a multiway join between relations, which are the edges, and where the vertices are the attributes. In recent years, the database community has proposed new join algorithms, typically called Worst-Case Optimal Join (WCOJ) algorithms, which have the property of bounding the number of intermediate results generated, in addition to showing an intrinsic concurrency. Given these new results, the thesis studies the feasibility of accelerating the subgraph isomorphism by using a WCOJ approach, designing a kernel able to pre-process the graphs and evaluate the results all on FPGA. The proposed implementation works around a novel parameterized data structure based on hash tables, which has been designed to respect the complexity requirements of WCOJ algorithms as well as leave space for parameter optimization. The algorithm has been developed in C++ using Vitis™ HLS tool by Xilinx Inc.