2026-09-20T14:56:01Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/101222 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Kale, Laxmikant Senthil Kumar Karthik, - 2018-09-04T20:36:54Z 2018-09-04T20:36:54Z 2020-09-05T09:15:09Z 2018-04-24 2018-05 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. Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2020-05-01 The student, - Senthil Kumar Karthik, accepted the attached license on 2018-04-24 at 16:01. The student, - Senthil Kumar Karthik, submitted this Thesis for approval on 2018-04-24 at 16:17. This Thesis was approved for publication on 2018-04-24 at 17:09. DSpace SAF Submission Ingestion Package generated from Vireo submission #12454 on 2018-08-31 at 17:21:26 Made available in DSpace on 2018-09-04T20:36:54Z (GMT). No. of bitstreams: 2 SENTHILKUMARKARTHIK-THESIS-2018.pdf: 669223 bytes, checksum: 35b2a1b95520cfc20fcd4073f2ddfaa8 (MD5) LICENSE.txt: 4220 bytes, checksum: f6bfd3369d3dadd3a99e12a3c16d63df (MD5) Previous issue date: 2018-04-24 Embargo set by: Seth Robbins for item 107306 Lift date: 2020-09-04T20:37:00Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system Embargo set by: Seth Robbins for item 107306 Lift date: 2020-09-04T20:42:08Z Reason: Author requested U of Illinois access only (OA after 2yrs) in Vireo ETD system U of I Only Restriction Lifted for Item 107306 on 2020-09-05T09:15:09Z. application/pdf http://hdl.handle.net/2142/101222 en Copyright 2018 - Senthil Kumar Karthik Scalable Graph Connectivity Parallel Union-Find Graph Clustering HPC Charm++ Scalable asynchronous connected components detection based on a parallel union-find algorithm text text Computer Science Computer Science University of Illinois at Urbana-Champaign Thesis M.S.