Presentation
SIGN IN TO VIEW THIS PRESENTATION Sign In
SIGMo: High-Throughput Batched Subgraph Isomorphism on GPUs for Molecular Matching
DescriptionSubgraph isomorphism is a fundamental graph problem with applications in diverse domains. Of particular interest is molecular matching, which uses a subgraph isomorphism formulation for the drug discovery process. While subgraph isomorphism is known to be NP-complete, in molecular matching a number of domain constraints allow for efficient implementations.
This paper presents SIGMo, a high-throughput, portable subgraph isomorphism framework for GPUs, specifically designed for batch molecular matching. SIGMo takes advantage of the specific domain formulation to provide a more efficient filter-and-join strategy: the framework introduces a novel multi-level iterative filtering technique based on neighborhood signature encoding to efficiently prune candidates before the join phase.
SIGMo is written in SYCL, allowing portable execution on AMD, Intel, and NVIDIA GPUs. Our experimental evaluation on a large dataset from ZINC demonstrates up to 1,470x speedup over state-of-the-art frameworks, achieving a throughput of 7.7 billion matches per second on a cluster with 256 GPUs.
This paper presents SIGMo, a high-throughput, portable subgraph isomorphism framework for GPUs, specifically designed for batch molecular matching. SIGMo takes advantage of the specific domain formulation to provide a more efficient filter-and-join strategy: the framework introduces a novel multi-level iterative filtering technique based on neighborhood signature encoding to efficiently prune candidates before the join phase.
SIGMo is written in SYCL, allowing portable execution on AMD, Intel, and NVIDIA GPUs. Our experimental evaluation on a large dataset from ZINC demonstrates up to 1,470x speedup over state-of-the-art frameworks, achieving a throughput of 7.7 billion matches per second on a cluster with 256 GPUs.
