Improving vertex-frontier based GPU breadth-first search  

作　　者：杨博 卢凯 高颖慧 徐凯 王小平 程志权 

机构地区：[1]Science and Technology on Parallel and Distributed Processing Laboratory,National University of Defense Technology [2]College of Computer, National University of Defense Technology [3]Department of Electronic Science and Engineering, National University of Defense Technology [4]Avatar Science Company

出　　处：《Journal of Central South University》2014年第10期3828-3836,共9页中南大学学报（英文版）

基　　金：Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of China;Project supported by the Program for New Century Excellent Talents in University of China;Projects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China

摘　　要：Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.Breadth-first search（BFS） is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×10^9 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×10^9 edges/s.

关 键 词：breadth-first search GPU graph traversal vertex frontier 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]