论文标题
最佳级别同步共享 - 内存并行BFS算法，具有最佳的并行前缀-SUM算法及其对能源消耗的影响
An Optimal Level-synchronous Shared-memory Parallel BFS Algorithm with Optimal parallel Prefix-sum Algorithm and its Implications for Energy Consumption
论文作者
论文摘要
我们为共享记忆体系结构提供了一种工作效率的平行级别同步广度（BFS）算法，该算法在并行运行时间上实现了理论下降。最优性不管图形的形状如何。我们还展示了这种最优对程序的能源消耗的含义。关键的想法是，在任何计算步骤中完成工作的核心绝不比使用更多的处理核心。我们将其余的核心闲置，以节省能源并减少其他资源论点（例如，带宽，共享的卡车等）。我们的BFS不使用锁和原子说明，并且可以轻松扩展到共享记忆协处理器。
We present a work-efficient parallel level-synchronous Breadth First Search (BFS) algorithm for shared-memory architectures which achieves the theoretical lower bound on parallel running time. The optimality holds regardless of the shape of the graph. We also demonstrate the implication of this optimality for the energy consumption of the program empirically. The key idea is never to use more processing cores than necessary to complete the work in any computation step efficiently. We keep the rest of the cores idle to save energy and to reduce other resource contentions (e.g., bandwidth, shared caches, etc). Our BFS does not use locks and atomic instructions and is easily extendible to shared-memory coprocessors.
