Direction-Optimizing广度优先搜索

摘要

广度优先搜索是许多图形处理应用程序使用的一个重要内核。在BFS的许多新兴应用中，例如分析社会网络，输入图是低直径和无标度的。我们提出了一种适合小直径图的混合方法，它结合了传统的自顶向下算法和新的自底向上算法。自下而上的算法可以极大地减少检查边的数量，这反过来加速了搜索的整体速度。在多套接字服务器上，我们的混合方法在一系列标准合成图上显示了3.3-7.8的速度提升，在真实社交网络图上显示了2.4-4.6的速度提升，与强大的基线相比。我们通常还会将之前领先的共享内存(多核和GPU)实现的性能提高一倍。

科学的规划

超级计算2012论文选集

摘要

版权

更多相关文章