Dissertation
Runtime and compilation optimizations for GPU-based subgraph matching
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Spring 2026
DOI: 10.25820/etd.008420
Abstract
Subgraph matching algorithms-such as graph pattern matching, motif counting, temporal subgraph matching, and continuous subgraph matching-are essential to many applications in bioinformatics, social network analysis, and cybersecurity. Despite extensive prior research on subgraph matching, the NP-hard complexity of these algorithms makes them performance bottlenecks, especially on large-scale graphs. Therefore, there is growing interest in leveraging the massive parallelism of GPUs to accelerate these computations.
This dissertation presents four works: STMatch, DCSM, GCSM, and Matcha, which address key performance and programmability challenges in accelerating subgraph matching algorithms on GPUs. These works advance the design of subgraph matching systems from three technical perspectives: parallel optimization (STMatch and DCSM), memory access optimization (GCSM), and programming models (Matcha).
STMatch introduces several parallelization techniques for GPU-based graph pattern matching. These techniques include a stack-based recursion simulator to eliminate recursion overhead, a depth-first extension strategy with work stealing to mitigate load imbalance, and loop unrolling to improve warp-level thread utilization, enabling STMatch to fully exploit the massive parallelism of GPUs. The techniques in STMatch are also applicable to other tasks, such as motif counting and temporal subgraph matching.
DCSM proposes a multi-version graph data structure for GPU-based continuous subgraph matching to address data race issues when processing multiple requests in parallel. DCSM’s interrequest parallelism enables it to efficiently handle real-world scenarios, where online systems must process real-time requests concurrently while maintaining high throughput and low response latency. Meanwhile, DCSM also applies parallel and pipelined optimizations to various operations on multi-version graphs and formally demonstrates their correctness.
GCSM makes memory access optimizations for GPU-based continuous subgraph matching, which exhibit highly skewed access frequencies across graph regions. GCSM introduces a graph-region sampling approach to identify frequently accessed data, which will be placed in high-bandwidth or on-chip memory. This optimized data placement across different memory hierarchies can significantly improve data locality. Since the performance of continuous subgraph matching systems is bounded by memory bandwidth, improved data locality can lead to significant speedups.
With the continuous emergence of new subgraph matching algorithms and hardware, implementing a high-performance program for each algorithm-hardware combination has become laborintensive. Therefore, we propose Matcha, a domain-specific language (DSL) for backtrackingbased subgraph matching algorithms. Users can define algorithmic logic using Matcha, and the Matcha compiler automatically generates optimized platform-specific code for the user program. Matcha leverages functional higher-order operators and a multi-level intermediate representation (IR) design to express a variety of algorithms while allowing the compiler to automatically perform domain-specific parallelization and memory optimizations.
These works together provide several methods for accelerating a broad class of subgraph matching algorithms, as well as a flexible and extensible programming language for building various new algorithms. Each work conducts comprehensive experiments to demonstrate the effectiveness of the proposed ideas. The core ideas in this dissertation can also be extended to a wide range of other irregular applications, such as backtracking algorithms, relational joins in database, and applications with irregular nested-loop structures. These non-subgraph matching algorithms can benefit from significant GPU acceleration through our approach and can also be implemented using the DSL we designed.
Details
- Title: Subtitle
- Runtime and compilation optimizations for GPU-based subgraph matching
- Creators
- Yihua Wei
- Contributors
- Peng Jiang (Advisor)Bijaya Adhikari (Committee Member)Steve Goddard (Committee Member)Kasturi Varadarajan (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Computer Science
- Date degree season
- Spring 2026
- DOI
- 10.25820/etd.008420
- Publisher
- University of Iowa
- Number of pages
- xvi, 133 pages
- Copyright
- Copyright 2026 Yihua Wei
- Language
- English
- Date submitted
- 04/22/2026
- Description illustrations
- Illustrations, graphs, charts, tables
- Description bibliographic
- Includes bibliographical references (pages 120-133).
- Public Abstract (ETD)
Subgraph matching algorithms are key building blocks in many real-world domains, such as bioinformatics, chemoinformatics, social network analysis, protein function prediction, and cybersecurity. However, the NP-hard complexity of subgraph matching often makes it a performance bottleneck, hindering progress in these domains. This has motivated growing interest in leveraging the massive parallelism of GPUs to accelerate these computations.
This dissertation proposes a set of optimization techniques for GPU-accelerated subgraph matching, addressing challenges such as load imbalance, thread underutilization, and redundant computation. We further design a domain-specific language (DSL) and an optimizing compiler that allows users to express subgraph matching workflows while the compiler automatically applies these optimizations. This dissertation also conducts comprehensive experiments on GPUs to validate the effectiveness of the proposed techniques.
The proposed techniques generalize beyond subgraph matching to other irregular applications with similar computational patterns, including backtracking search, relational joins, and irregular nested-loop computations, enabling efficient acceleration of these applications on GPUs.
- Academic Unit
- Computer Science
- Record Identifier
- 9985177376002771
Metrics
1 Record Views