Scalable asynchronous connected components detection based on a parallel union-find algorithm
Senthil Kumar Karthik, -
Loading…
Permalink
https://hdl.handle.net/2142/101222
Description
Title
Scalable asynchronous connected components detection based on a parallel union-find algorithm
Author(s)
Senthil Kumar Karthik, -
Issue Date
2018-04-24
Director of Research (if dissertation) or Advisor (if thesis)
Kale, Laxmikant
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
M.S.
Degree Level
Thesis
Keyword(s)
Scalable Graph Connectivity
Parallel Union-Find
Graph Clustering
HPC
Charm++
Abstract
Connectivity in a graph is a well-studied problem. Various parallel algorithms to detect and label connected components exist, many of which are optimized for a shared-memory environment. However, scientific and engineering applications today process large-scale graphs that do not fit in a single compute node. This calls for a highly scalable solution to the connectivity problem. We propose a novel distributed-memory parallel algorithm based on the Union-Find data structure and asynchronous messaging. We strengthen the scalability of our approach by introducing several optimization techniques for parallel execution. The algorithm is implemented as a library using Charm++, a migratable object-based parallel programming model, allowing any Charm++ application to easily perform connected components detection. MPI applications may also use the library either via Adaptive MPI, or by using interoperability features of Charm++. In addition, the library will also support reading data from the disk. As a driving use case we utilize the library in ChaNGa, a cosmological simulation framework, to detect clusters of stars and classify galaxies. We evaluate the performance of our algorithm for real and synthetic graphs, computing connectivity on a probabilistic mesh benchmark with over 250 million edges in under 10 seconds using 4,096 cores of the Blue Waters (Cray XE) Supercomputer.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
