Enhancements in high performance subgraph enumeration on graphics processors
Kawtikwar, Samiran
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/116103
Description
Title
Enhancements in high performance subgraph enumeration on graphics processors
Author(s)
Kawtikwar, Samiran
Issue Date
2022-07-18
Director of Research (if dissertation) or Advisor (if thesis)
Nagi, Rakesh
Hwu, Wen-Mei
Department of Study
Industrial&Enterprise Sys Eng
Discipline
Industrial Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
subgraph-enumeration, cuda, gpu, parallel algorithms, DFS, big graphs, graph analytics
Abstract
Subgraph enumeration is an important problem in graph theory with a wide range of applications. With rapidly increasing graph sizes due to advent of internet and smartphones, subgraph enumeration needs high performing implementations. Being NP-complete, this problem poses significant scalability challenges and needs efficient implementations for practical solutions. Fortunately, this problem is highly amenable to parallelization. There are already many solutions in the multi-core and distributed computing community. GPU (Graphics Processing Unit)-based solutions are recently gaining recognition as they offer massive parallelism without network delays. Most GPU solutions use Breadth First Traversal to utilize underlying parallelism and impose expensive restrictions on hardware due to huge memory requirements. PARSEC (Parallel Subgraph Enumeration and Counter) is the first GPU-based solution that uses Depth First Search and performs in-memory subgraph enumeration. In this thesis, PARSEC is improved by leveraging insights from traditional sequential solutions and advanced parallel programming techniques. The performance of Subgraph Enumeration is limited by the computational cost of adjacency list intersection operations. To tackle this, a smart preprocessing technique was developed for detecting opportunities for intersection reuse, which, in turn, reduces the number of intersections by up to 3.87×. A two-phase pruning technique was developed which shrinks the search space to further reduce the number of intersections by up to 6.6×. An in-depth analysis of PARSEC was conducted to overcome its load imbalance and limited hardware utilization. A hybrid parallelization scheme was developed that improves the load balance by up to 14×. Altogether, these improvements provide a geometric mean time speedup up to 4.6× across data graphs and up to 3.7× across all queries with max speedups up to 14.6×.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.