Files in this item



application/pdfSENTHILKUMARKARTHIK-THESIS-2018.pdf (669kB)
(no description provided)PDF


Title:Scalable asynchronous connected components detection based on a parallel union-find algorithm
Author(s):Senthil Kumar Karthik, -
Advisor(s):Kale, Laxmikant
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Scalable Graph Connectivity
Parallel Union-Find
Graph Clustering
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.
Issue Date:2018-04-24
Rights Information:Copyright 2018 - Senthil Kumar Karthik
Date Available in IDEALS:2018-09-04
Date Deposited:2018-05

This item appears in the following Collection(s)

Item Statistics