Presentation
SIGN IN TO VIEW THIS PRESENTATION Sign In
A GPU Algorithm for Detecting Strongly Connected Components
SessionGraph Algorithms in HPC
DescriptionDetecting strongly connected components (SCCs) is an important step in various graph computations. The fastest GPU and CPU implementations from the literature work well on graphs where most of the vertices belong to a single SCC and the vertex degrees follow a power-law distribution. However, these algorithms can be slow on the mesh graphs used in certain radiative transfer simulations, which have a nearly constant vertex degree and can have significant variability in the number and size of SCCs. We introduce ECL-SCC, an SCC detection algorithm that addresses these shortcomings. Our approach is GPU-friendly and employs innovative techniques such as maximum ID propagation and edge removal. On an A100 GPU, ECL-SCC performs on par with the fastest prior GPU code on power-law graphs and outperforms it by 7.8x on mesh graphs. Moreover, ECL-SCC running on the GPU outperforms fast parallel CPU code by three orders of magnitude on meshes.
Event Type
Paper
TimeTuesday, 14 November 202311am - 11:30am MST
Location401-402
Accelerators
Algorithms
Graph Algorithms and Frameworks
TP
