X-SET: An Efficient Graph Pattern Matching Accelerator With Order-Aware Parallel Intersection Units

Graph Pattern Matching (GPM) is a critical task in a wide range of graph analytics applications, such as social network analysis and cybersecurity. Despite its importance, GPM remains challenging to accelerate due to its inherently irregular control flow and heavy reliance on set operations, which dominate execution time and introduce data dependencies that limit parallelism. While recent GPM accelerators attempt to improve performance, they often overlook the ordered nature of input data, resulting in redundant computations and inefficient hardware utilization.

This paper presents X-SET, a GPM accelerator that overcomes these limitations by introducing two key innovations. First, we propose an Order-Aware Set Intersection Unit (SIU), which exploits input ordering to reduce the hardware complexity of parallel set intersection from O (𝑁 2 ) to O (𝑁 log 𝑁 ), achieving high throughput and significant area savings by avoiding unnecessary comparisons. Second, we develop a barrier-free task scheduler that breaks traditional DFS scheduling constraints by enabling asynchronous, outof-order task execution across different levels of the GPM search tree. X-SET is integrated into a RISC-V SoC, supporting end-to-end acceleration. Extensive experimental results show that X-SET outperforms state-of-the-art GPM accelerators, achieving 4.6×-142.9× improvements in compute density, with a geometric mean of 13.7×, and delivering 6.4× geometric mean and 42.9× maximum speedup in end-to-end performance. X-SET is open-sourced at github 1 .