High-Level Synthesis Exploration of Cache size Effects in FPGA-Based subgraph Isomorphism Acceleration

Graphs are a widely used data structure to represent relationships between entities, where vertices correspond to objects and edges describe the connections between them. Examples range from chemical structures, where atoms are connected by bonds, to social networks, where users are linked by friendships. In this work, we focus on undirected, vertex-labeled graphs, a common representation in many domains where entities and their relationships need to be modeled. The main problem addressed is the subgraph isomorphism task, which aims to identify occurrences of a smaller graph pattern within a much larger graph dataset. This problem is known to be computationally challenging and has applications across diverse areas such as network analysis, bioinformatics, and cheminformatics. Graph datasets pose unique memory challenges due to their irregular access patterns and lack of spatial locality. Even if two vertices are connected, their data is often stored far apart in memory, resulting in frequent cache misses and inefficient data retrieval. The subgraph matching algorithm itself responsible for checking vertex correspondences and label equality was already implemented as part of previous research work and is not the focus of this work. Instead, the focus is on memory caching and its role in optimizing data access for FPGA-based subgraph isomorphism acceleration. To address these challenges, the DataGraph is stored using large hash tables, with a hash function mapping each vertex to a memory location. Although this approach increases the overall memory footprint compared to storing the graph in its original adjacency-list format, the reason is that large hash tables and Bloom filters require additional space to represent vertices and their adjacency information in a more uniform layout. The approach also reorganizes the data to enhance locality based on the specific access pattern of the subgraph isomorphism algorithm, which further improves cache utilization and reduces irregular memory accesses. The FPGA architecture designed in this thesis is built around a parameterizable cache positioned between the external DDR memory and the processing kernel. The kernel executes a multi-way join algorithm, which identifies query matches by intersecting adjacency sets retrieved from the hash tables. The system operates in two main phases: 1.??Preprocessing – Constructs hash tables and Bloom filters for the DataGraph according to the QueryGraph structure. 2.??Multi-way join – Identifies matches by intersecting adjacency sets, relying primarily on cached data accesses to reduce memory latency and improve efficiency. The cache size is parameterized so that different configurations can be synthesized, enabling an empirical study of how cache capacity affects performance. The evaluation focuses on the impact of cache dimensions, with particular attention to line sizes and set sizes in the proposed accelerator. The results show that, while larger caches generally improve performance, the choice of cache granularity also plays an important role: for the same total cache size, certain line size and set size configurations provide more favorable results. In particular, identical caches in terms of memory occupation can perform differently depending on their configuration, due to the specific access pattern of the function reading from the cache. This highlights the importance of carefully tuning cache parameters rather than simply increasing capacity.