Files in this item

FilesDescriptionFormat

application/pdf

application/pdfDODEJA-THESIS-2021.pdf (2MB)
(no description provided)PDF

Description

Title:High performance DFS-based subgraph enumeration on GPUs
Author(s):Dodeja, Vibhor
Advisor(s):Nagi, Rakesh; Hwu, Wen-mei
Department / Program:Electrical & Computer Eng
Discipline:Electrical & Computer Engr
Degree Granting Institution:University of Illinois at Urbana-Champaign
Degree:M.S.
Genre:Thesis
Subject(s):Subgraph enumeration, Pattern matching, Graphics processing units, acceleration, data mining
Abstract:Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. GPU-based solutions are gaining traction in recent times. Subgraph enumeration involves traversing a search tree formulated to find matches of a query in a graph. Most GPU-based solutions traverse the tree in a breadth-first manner which exploits parallelism at the cost of high memory requirement, which presents a formidable challenge for processing large graphs since the memory capacity of GPUs is significantly lower than that of CPUs. In this thesis, we propose a fast GPU-based solution based on depth-first traversal of the search tree. The depth-first approach requires less memory but presents more challenges for parallel execution. We apply various optimizations to optimally utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with state-of-the-art CPU and GPU implementations. We outperform them with a geometric mean speedup of 10,678x and 8.56x from CPU and GPU implementations respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by these state-of-the-art implementations due to their excessive memory requirement.
Issue Date:2021-04-26
Type:Thesis
URI:http://hdl.handle.net/2142/110559
Rights Information:Copyright 2021 Vibhor Dodeja
Date Available in IDEALS:2021-09-17
Date Deposited:2021-05


This item appears in the following Collection(s)

Item Statistics