Search NASA⌕ Search

DOE OSTI · 1836011

cuTS: Scaling Subgraph Isomorphism on Distributed Multi-GPUSystems Using Trie Based Data Structure

Abstract

Subgraph isomorphism is a pattern-matching algorithm widely used in many domains such as chem-informatics, bioinformatics, databases, and social network analysis. It is computationally expensive and is a proven NP-hard problem. The massive parallelism offered by the GPU hardware is well suited for solving the subgraph isomorphism. However, current GPU implementations are far from the achievable performance. Moreover, the enormous memory requirement of current approaches limits the problem size that can be handled. This work analyzes the fundamental challenges associated with processing the subgraph isomorphism on GPUs and develops an efficient GPU hardware-aware implementation. We also develop a new GPU-friendly trie-based data structure to drastically reduce the intermediate storage space requirement. Hence, our approach runs larger benchmarks than the competitors. We also develop the first distributed sub-graph isomorphism algorithm for GPUs. Our experimental evaluation section demonstrates the efficacy of our approach by comparing the execution time and number of cases that we can handle against the state-of-the-art GPU implementations.

Keep this discovery

Explore connections, maps & timelines

BibTeXRIS

Xiang, Lizhi, Khan, Md Ariful H., Serra, Edoardo, Halappanavar, Mahantesh, Sukumaran-Rajan, Aravind. 2021-09-02. cuTS: Scaling Subgraph Isomorphism on Distributed Multi-GPUSystems Using Trie Based Data Structure. https://doi.org/10.1145/3458817.3476214. https://searchnasa.com/record/osti%3A1836011/cuts-scaling-subgraph-isomorphism-on-distributed-multi-gpusystems-using-trie-based-data-structure

Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.