High performance DFS-based subgraph enumeration on GPUs

Dodeja, Vibhor

Permalink

https://hdl.handle.net/2142/110559 Copy

Description

Title

High performance DFS-based subgraph enumeration on GPUs

Author(s)

Dodeja, Vibhor

Issue Date

2021-04-26

Director of Research (if dissertation) or Advisor (if thesis)

• Nagi, Rakesh
• Hwu, Wen-mei

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(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.

Graduation Semester

2021-05

Type of Resource

Thesis

Permalink

http://hdl.handle.net/2142/110559

Copyright and License Information

Copyright 2021 Vibhor Dodeja

Owning Collections