Enhancements in high performance subgraph enumeration on graphics processors

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×.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Kawtikwar, Samiran

Contributors dc:contributor

• Nagi, Rakesh
• Hwu, Wen-Mei

• subgraph-enumeration
• cuda
• gpu
• parallel algorithms
• DFS
• big graphs
• graph analytics

Statement dc:rights

• Copyright 2022 Samiran Kawtikwar

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/116103

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116103