• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters
【24h】

Graphine: Programming Graph-Parallel Computation of Large Natural Graphs for Multicore Clusters

机译：Graphine：用于多核群集的大型自然图的编程图并行计算

获取原文
获取原文并翻译 | 示例
       
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Graph-parallel computation has become a crucial component in emerging applications of web search, data analytics and machine learning. In practice, most graphs derived from real-world phenomena are very large and scale-free. Unfortunately, distributed graph-parallel computation of these graphs still suffers strong scalability issues on contemporary multicore clusters. To embrace the multicore architecture in distributed graph-parallel computation, we propose the framework Graphine, which features (i) A Scatter-Combine computation abstraction that is evolved from the traditional vertex-centric approach by fusing the paired scatter and gather operations, executed separately on two edge sides, into a one-sided scatter. Further coupled with active message mechanism, it potentially reduces intermediate message cost and enables fine-grained parallelism on multicore architecture. (ii) An Agent-Graph data model, which leverages an idea similar to vertex-cut but conceptually splits the remote replica into two agent types of scatter and combiner, resulting in less communication. We implement the Graphine framework and evaluate it using several representative algorithms on six large real-world graphs and a series of synthetic graphs with power-law degree distributions. We show that Graphine achieves sublinear scalability with the number of cores per node, number of nodes, and graph sizes (up to one billion vertices), and is 215 times faster than the state-of-the-art PowerGraph on a cluster of 16 multicore nodes.
机译：图并行计算已成为新兴的Web搜索，数据分析和机器学习应用程序中的重要组成部分。在实践中，大多数来自现实世界现象的图非常大且无比例。不幸的是，这些图形的分布式图形并行计算在现代多核集群上仍然遭受着严重的可伸缩性问题。为了在分布式图并行计算中包含多核体系结构，我们提出了Graphine框架，该框架具有（i）一种Scatter-Combine计算抽象，它是通过将成对的散布和聚集操作融合在一起而从传统的以顶点为中心的方法演变而来的，分别执行在两个边缘侧，形成一个单侧分散。再加上主动消息机制，它有可能降低中间消息成本，并在多核体系结构上实现细粒度的并行性。 （ii）一个Agent-Graph数据模型，该模型利用了类似于顶点切割的思想，但在概念上将远程副本分为散布和合并两种代理类型，从而减少了通信。我们实现了Graphine框架，并使用几种代表性算法对六个大型现实世界图和一系列具有幂律度分布的合成图进行了评估。我们展示了Graphine通过每个节点的核心数量，节点数量和图形大小（最多十亿个顶点）实现了亚线性可扩展性，并且比16个集群上最新的PowerGraph快215倍多核节点。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号