Accelerating betweenness centrality computation on heterogeneous processors

Abstract

The betweenness centrality (BC) measure of nodes in a graph is widely used in graph analysis. As both multicore CPUs and manycore GPUs are becoming greatly competitive in their parallel computation power, we propose to utilize these heterogeneous processors on a single machine to accelerate the BC computation. Specifically, we study edge-based versus virtualization-based parallelization strategies for GPU-based BC computation on unweighted graphs, and propose to optimize the two strategies to achieve the best performance. Furthermore, we examine the performance tradeoff of Distance-sensitive/insensitiveGPU-based BC on weighted graphs. We have implemented representative BC algorithms on the CPU and the GPU, and evaluated them on a server with two Intel E5-2650 CPUs and four NVIDIA M2090 GPUs. Our results show that, with suitable parallelization and optimization, BC computation can be scaled well on the set of heterogeneous processors.

Date of Award	2014
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology