Efficient Hybrid Breadth-First Search on GPUs
Efficient Hybrid Breadth-First Search on GPUs
复制标题
GPU 上的高效混合广度优先搜索
DOI：
10.1007/978-3-319-03889-6_5
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Takahashi
中科院分区：
文献类型：
--
作者：
Takaaki Hiragushi;D. Takahashi
广度优先搜索（BFS）是图处理的基本算法。这是一个非常重要的算法，因为许多图处理算法使用广度优先搜索作为子例程。近年来，大规模图已被应用于各个领域，并且越来越需要一种有效的方法来处理大规模图。在本文中，我们在 GPU 上提出了一种混合 BFS 实现，用于高效遍历复杂网络，与之前的 GPU 实现相比，我们实现了高达 29 倍的加速。我们还在分布式内存系统上应用了 GPU 的实现。该实施在具有 1,024 个 NVIDIA M2090 GPU 的 256 节点 HA-PACS 集群上实现了 117.546 GigaTEPS 的速度，并在 2013 年 6 月的 Graph500 列表中排名第 39 位。
Breadth-first search (BFS) is a basic algorithm for graph processing. It is a very important algorithm because a number of graph-processing algorithms use breadth-first search as a sub-routine. Recently, large-scale graphs have been used in various fields, and there is a growing need for an efficient approach by which to process large-scale graphs. In the present paper, we present a hybrid BFS implementation on a GPU for efficient traversal of a complex network, and we achieved a speedup of up to 29x, as compared to the previous GPU implementation. We also applied an implementation for GPUs on a distributed memory system. This implementation achieved a speed of 117.546 GigaTEPS on a 256-node HA-PACS cluster with 1,024 NVIDIA M2090 GPUs and was ranked 39th on the June 2013 Graph500 list.