Enhancements in high performance subgraph enumeration on graphics processors

Kawtikwar, Samiran

Permalink

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

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

Graduation Semester

2022-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Samiran Kawtikwar

Owning Collections