Research and ACM SRC Posters Archive

A Multi-Phase GPU Pipeline for Biconnected Components


Poster Type: Research Posters

Author: Soumendra Banerjee (University of North Texas), Turja Kundu (University of North Texas), Sanjukta Bhowmick (University of North Texas), Sriram Srinivasan (Bowie State University)

Abstract: Graph biconnectivity is a fundamental primitive for structural analysis, but classical algorithms rely on depth-first search, which is inherently sequential and does not scale to GPUs. We present a multi-phase, GPU-resident pipeline for computing biconnected components on large-scale undirected graphs. Our pipeline first removes 1-core vertices through iterative peeling, then grows depth-capped breadth-first search trees from multiple random roots in parallel, ensuring each vertex joins exactly one tree. We resolve each tree's non-tree edges into local biconnected components, then merge components across tree boundaries using the remaining cross-tree edges. We evaluate our approach on 17 real-world networks on a single NVIDIA A100 GPU. Our approach substantially outperforms earlier GPU and CPU baselines, including WK-17, WK-18, and CPU-based FAST-BCC, and achieves an average speedup of 2.49x over FAST-BCC-Filter, the current state-of-the-art GPU approach.

Best Poster Finalist (BP): no
Poster: PDF
Poster Summary: PDF


Back to Poster Archive Listing