Politecnico di Torino (logo)

Subgraph isomorphism acceleration on FPGAs using High-Level Synthesis

Roberto Bosio

Subgraph isomorphism acceleration on FPGAs using High-Level Synthesis.

Rel. Luciano Lavagno, Mihai Teodor Lazarescu. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022

PDF (Tesi_di_laurea) - Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives.

Download (1MB) | Preview

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.

Relators: Luciano Lavagno, Mihai Teodor Lazarescu
Academic year: 2022/23
Publication type: Electronic
Number of Pages: 50
Corso di laurea: Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering)
Classe di laurea: New organization > Master science > LM-32 - COMPUTER SYSTEMS ENGINEERING
Aziende collaboratrici: UNSPECIFIED
URI: http://webthesis.biblio.polito.it/id/eprint/25558
Modify record (reserved for operators) Modify record (reserved for operators)