An Adaptive Parallel Algorithm for Computing Connected Components
| Autor: | Tony Pan, Patrick Flick, Srinivas Aluru, Oded Green, Chirag Jain |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
0301 basic medicine Computer science Breadth-first search Parallel algorithm Parallel computing 03 medical and health sciences Connectivity Connected component Analysis of parallel algorithms Social graph Cost efficiency Heuristic Graph partition Degree distribution Graph Modular decomposition 030104 developmental biology Computer Science - Distributed Parallel and Cluster Computing Computational Theory and Mathematics Hardware and Architecture Signal Processing Topological graph theory Graph (abstract data type) Algorithm design Distributed Parallel and Cluster Computing (cs.DC) MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems. 28:2428-2439 |
| ISSN: | 1045-9219 |
| Popis: | We present an efficient distributed memory parallel algorithm for computing connected components in undirected graphs based on Shiloach-Vishkin’s PRAM approach. We discuss multiple optimization techniques that reduce communication volume as well as load-balance the algorithm. We also note that the efficiency of the parallel graph connectivity algorithm depends on the underlying graph topology. Particularly for short diameter graph components, we observe that parallel Breadth First Search (BFS) method offers better performance. However, running parallel BFS is not efficient for computing large diameter components or large number of small components. To address this challenge, we employ a heuristic that allows the algorithm to quickly predict the type of the network by computing the degree distribution and follow the optimal hybrid route. Using large graphs with diverse topologies from domains including metagenomics, web crawl, social graph and road networks, we show that our hybrid implementation is efficient and scalable for each of the graph types. Our approach achieves a runtime of 215 seconds using 32 K cores of Cray XC30 for a metagenomic graph with over 50 billion edges. When compared against the previous state-of-the-art method, we see performance improvements up to 24 $\times$ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|