Scalable asynchronous connected components detection based on a parallel union-find algorithm

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2018

Author dc:creator

• Senthil Kumar Karthik, -

Contributors dc:contributor

• Kale, Laxmikant

• Scalable Graph Connectivity
• Parallel Union-Find
• Graph Clustering
• HPC
• Charm++

Statement dc:rights

• Copyright 2018 - Senthil Kumar Karthik

Language dc:language

en

Handle dc:identifier

http://hdl.handle.net/2142/101222

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/101222