Subgraph matching is a well-known NP-hard problem widely applied in fields such as bioinformatics, cheminformatics, and social network analysis. It aims to enumerate all embeddings in a data graph that are isomorphic to a query graph. Subgraph matching algorithms can be roughly classified into BFS-based and DFS-based algorithms. The intersection operation is the core operation in both types of algorithms and consumes a significant amount of time. There are numerous repeated intersection operations in subgraph matching, and their results can be reused. Recent studies have focused on implementing the DFS-based algorithm on GPUs with an explicit stack. We categorize the reuse in the DFS-based algorithm into two types: within-stack reuse and across-stack reuse. Previous works only considered within-stack reuse, which has a narrow scope of application and lacks generality for some query graphs. In this paper, we are the first to propose a method for across-stack reuse in DFS-based algorithms on GPUs. We introduce a tree-structured copy stack to reuse duplicate intersections and design a secondary checking mechanism to ensure the correctness of the reuse. We use the non-blocking lock mechanism to avoid read-write races and conduct a rigorous theoretical analysis to prove that the impact of the non-blocking lock on reuse is negligible. Moreover, we propose a GPU-specific optimization method that uses key nodes to reduce memory transactions during intersection operations. Compared with the state-of-the-art DFS-based matching algorithms, our work achieves $1.12 \times$ to $1.95 \times$ speedup, and the reuse rate reaches 78.68%.ACM Reference Format:Chen Chen, Shanzhi Gu, Junsheng Chang, and Li Shen. 2025. Accelerating DFS-based Subgraph Matching on GPU via Reusing Intersection. In. ACM, New York, NY, USA, 12 pages. https://doi.org/10.1145/nnnnnnn.nnnnnnnn

Subgraph isomorphism enumerates all embeddings in a data graph that are identical to a query graph. It is a well-known NP-hard problem widely used in various domains, such as bioinformatics, chem-informatics, and social network analysis. Recent works are focused on using GPUs for subgraph isomorphism. Due to the massive scale of intermediate results, current GPU implementations face challenges in scaling across multiple nodes due to high communication costs. The computational power of CPUs is not fully utilized in this process. We present a distributed framework for subgraph isomorphism that leverages CPU and GPU heterogeneous computing. It eliminates the intermediate results on GPU and significantly reduces communication overhead during the load-balancing process. The experiments indicate that our algorithm can be extended to multiple nodes with an almost linear efficiency improvement. Furthermore, our method also significantly outperforms other existing works on GPUs. It can reach an improvement of up to 21 × compared to the state-of-the-art implementation CuTS in the distributed environment.

Coverage guided dynamic verification is a widely used verification technique for RTL designs described using domain-specific languages for hardware and representing in some intermediate representations. Although the embedding of fuzz testing promote the abilities of coverage guided dynamic verification, there are lack of efficiently metric feedbacks utilization. In this paper, we proposed MMFuzz, a novel fuzzing tool enhanced by metric feedbacks. The proposed method utilze metric feedbacks efficiently in two aspects: seeds selection and mutators selection. The experimental results on several practical designs show that our method is able to achieve up to 1.0x improvements over the state-of-the-art RTL fuzzing tool with the same times of mutation.

Deep learning (DL) systems are typically used to accelerate training DL jobs. Training DL models requires feeding mass input data. It takes a long time to transfer training data from the storage nodes to the compute nodes. However, the computational resources of the GPUs are idle during the data transmission period, which results in a waste of computing resources. In DL systems, a large number of short-term jobs are queuing longer than their own execution times. Meanwhile, many multi-GPU jobs are suffering a long-queuing time due to not enough free GPU. To the best of our knowledge, no studies try to use the idle computation resources of GPU in the data transmission period.We propose Tereis, a package-based scheduler to make full use of GPU. Tereis predicts a DL job’s execution time and data transmission time, then safely package two jobs on the same GPU. One of the packaged jobs will be completed before the other job ends transferring data, which is what ‘safely’ means. This ‘safe’ Packaging does not cause GPU contention. Tereis also designs multi-level queues to prevent starvation. We implemented Tereis in python on the actual cluster and evaluated its performance. The experiment results show that Tereis decreases the average waiting time by 3.2× to10.5×, and has an improvement of 18% to 42% on makespan compared to other methods. Furthermore, we have made large-scale simulations to explore the sensitivities of Tereis. We find that Tereis performs better in the scenario where the job set has a distribution of large dataset size and jobs are submitted frequently.

Deep learning (DL) jobs normally run on GPU clusters. Some DL jobs need to be scheduled preemptively to avoid long waiting times. However, preempting a DL job is time-consuming, which consists of suspending and resuming. Suspending needs to complete the training process of the current epoch, and resuming needs to reload the model and the training data. The existing schedulers almost do not consider the overhead of preempting jobs; thus, they may preempt jobs with large time loss, increasing the waiting time and the makespan.In this paper, we present PickyMan, a preemptive scheduler to minimize the overhead of preempting jobs to reduce the average waiting time and the makespan. PickyMan has some innovations. (1) Predict execution time using network traffic and database. It predicts the execution time of a DL job by profiling the network traffic from storage nodes to computation nodes and using a database, without the requirement of allocating extra resources from the cluster. It can use profiled information of only four jobs to predict the execution times for other same-model jobs, and most of the predicted errors are less than 10%. (2) Modeling the overhead of preemption. It builds a model to predict the time loss of job suspensions and resumptions with an average error of less than 5%. (3)We abstract the problem of choosing the appropriate jobs for preemption as one of finding an ordered division of the set of running jobs and solve it quickly with a greedy algorithm. By conducting experiments on the small-scale actual cluster and making large-scale simulations, PickyMan reduces the average waiting time by 10%–92% and further reduces the makespan by up to 14%, compared to existing methods.

Data races hidden in concurrent programs have caused severe failures. To improve the reliability, many race detectors are proposed. However, most of the reported races are not harmful, which consumes manual effort to identify the harmful races. This paper proposes RaceChecker that can detect the potential races and identify the harmful races effectively and efficiently. Unlike previous detectors, RaceChecker combines happens-before relation and ad-hoc synchronization to prune the infeasible races so that fewer potential races are required to be verified. Before verification, RaceChecker groups the remaining potential races, guaranteeing the potential races in one group do not interfere with each other. Therefore, multiple potential races in one group can be verified together in one execution. To our knowledge, this is the first effective technique that groups the potential races to improve the efficiency. Unlike previous detectors that verify one potential race in one execution, RaceChecker dynamically controls thread scheduler to create real race conditions to verify multiple potential races in one execution, identifying the harmful races that cause program failures. We have implemented RaceChecker as a prototype tool and have experimented on a number of real-world concurrent programs. Results show that 66% of the potential races are infeasible and nearly 48% of the executions are reduced by the grouping strategy. The known harmful races are also identified effectively. By pruning and grouping, RaceChecker identifies the harmful races more efficiently. Comparing with RaceMob and RaceFuzzer, the time is reduced significantly, with an average of 45% and 81% respectively.