首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >An Adaptive Parallel Algorithm for Computing Connected Components
【24h】

An Adaptive Parallel Algorithm for Computing Connected Components

机译:一种计算连接组件的自适应并行算法

获取原文
获取原文并翻译 | 示例

摘要

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 .
机译:我们提出了一种有效的分布式内存并行算法,用于基于Shiloach-Vishkin的PRAM方法计算无向图中的连接组件。我们讨论了减少通信量以及负载均衡算法的多种优化技术。我们还注意到,并行图连接算法的效率取决于基础图拓扑。特别是对于短直径图形组件,我们观察到并行广度优先搜索(BFS)方法提供了更好的性能。但是,运行并行BFS对于计算大直径部件或大量小部件效率不高。为了解决这一挑战,我们采用了一种启发式算法,该算法允许算法通过计算度分布并遵循最佳混合路径来快速预测网络的类型。使用大型图具有来自不同领域的多元拓扑,包括宏基因组学,Web爬网,社交图和道路网络,我们证明了我们的混合实现对于每种图类型都是有效且可扩展的。我们的方法使用Cray XC30的32 K内核实现了215秒的运行时间,从而获得了超过500亿条边的宏基因组图。与以前的最新方法相比,我们看到性能提高了24倍。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号