BEEP: Balanced Efficient subgraph Enumeration in Parallel

Samiran Kawtikwar, Mohammad Almasri, Wen Mei Hwu, Rakesh Nagi, Jinjun Xiong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

BEEP is a state-of-the-art subgraph enumerator that delivers high performance through a combination of balanced, parallel GPU processing and novel algorithmic improvements. With a rapidly increasing demand for fast tools on large graphs, GPU-based subgraph enumerators are of growing interest. Most existing GPU enumerators are based on Breadth First Search (BFS), which often impose limitations on hardware resources due to excessive memory requirements. PARSEC [12] was the first GPU enumerator to adopt Depth First Search (DFS) that demonstrated impressive speedups and its adaptability to hardware with limited memory resources. However, PARSEC's DFS implementation suffers from computational inefficiencies and load imbalances. BEEP introduces novel search space reduction techniques and load balancing strategies to tackle these challenges in DFS-based parallelization and achieves exceptional performance and scalability. Experimental results indicate that BEEP outperforms PARSEC with geometric mean speedups of up to 10.52× across disparate data graphs and up to 7.28× across various queries with maximum speedups of 33.46×. This makes BEEP the fastest subgraph enumerator to date. Furthermore, a multi-GPU implementation is developed that exhibits almost linear scalability with the number of devices.

Original languageEnglish (US)
Title of host publication52nd International Conference on Parallel Processing, ICPP 2023 - Main Conference Proceedings
PublisherAssociation for Computing Machinery
Pages142-152
Number of pages11
ISBN (Electronic)9798400708435
DOIs
StatePublished - Aug 7 2023
Event52nd International Conference on Parallel Processing, ICPP 2023 - Salt Lake City, United States
Duration: Aug 7 2023Aug 10 2023

Publication series

NameACM International Conference Proceeding Series

Conference

Conference52nd International Conference on Parallel Processing, ICPP 2023
Country/TerritoryUnited States
CitySalt Lake City
Period8/7/238/10/23

ASJC Scopus subject areas

  • Human-Computer Interaction
  • Computer Networks and Communications
  • Computer Vision and Pattern Recognition
  • Software

Fingerprint

Dive into the research topics of 'BEEP: Balanced Efficient subgraph Enumeration in Parallel'. Together they form a unique fingerprint.

Cite this