• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Parallel and Distributed Systems, IEEE Transactions on >BFS-4K: An Efficient Implementation of BFS for Kepler GPU Architectures
【24h】

BFS-4K: An Efficient Implementation of BFS for Kepler GPU Architectures

机译：BFS-4K：开普勒GPU架构BFS的高效实现

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

摘要

Breadth-first search (BFS) is one of the most common graph traversal algorithms and the building block for a wide range of graph applications. With the advent of graphics processing units (GPUs), several works have been proposed to accelerate graph algorithms and, in particular, BFS on such many-core architectures. Nevertheless, BFS has proven to be an algorithm for which it is hard to obtain better performance from parallelization. Indeed, the proposed solutions take advantage of the massively parallelism of GPUs but they are often asymptotically less efficient than the fastest CPU implementations. This paper presents , a parallel implementation of BFS for GPUs that exploits the more advanced features of GPU-based platforms (i.e., NVIDIA Kepler) and that achieves an asymptotically optimal work complexity. The paper presents different strategies implemented in to deal with the potential workload imbalance and thread divergence caused by any actual graph non-homogeneity. The paper presents the experimental results conducted on several graphs of different size and characteristics to understand how the proposed techniques are applied and combined to obtain the best performance from the parallel BFS visits. Finally, an analysis of the most representative BFS implementations for GPUs at the state of the art and their comparison with are reported to underline the efficiency of the proposed solution.
机译：广度优先搜索（BFS）是最常见的图形遍历算法之一，并且是广泛的图形应用程序的基础。随着图形处理单元（GPU）的出现，已经提出了一些工作来加速图形算法，尤其是在这种多核体系结构上的BFS。但是，事实证明，BFS是很难从并行化获得更好性能的算法。确实，所提出的解决方案利用了GPU的大规模并行性，但是它们通常比最快的CPU实现渐渐地效率低。本文介绍了针对GPU的BFS并行实现，该实现利用了基于GPU的平台（即NVIDIA Kepler）的更高级功能，并实现了渐近优化的工作复杂性。本文提出了不同的实施策略，以应对任何实际图形不均一性引起的潜在工作负载不平衡和线程发散。本文介绍了在几个不同大小和特征的图形上进行的实验结果，以了解所提出的技术如何应用​​和组合以从并行BFS访问中获得最佳性能。最后，据报道，对最先进的GPU最具代表性的BFS实现进行了分析，并与之进行了比较，以强调所提出解决方案的效率。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号