Fast Diameter Computation of Large Sparse Graphs using GPUs
Institute for Computing and Information Sciences, Radboud University Nijmegen, The Netherlands
22nd IEEE International Conference on Parallel, Distributed and network-based Processing (PDP 2014), 2014
@article{dal2013fast,
title={Fast Diameter Computation of Large Sparse Graphs using GPUs},
author={Dal, Giso H. and Kosters, Walter A. and Takes, Frank W.},
year={2013}
}
In this paper we propose a highly parallel GPU-based bounding algorithm for computing the exact diameter of large real-world sparse graphs. The diameter is defined as the length of the longest shortest path between vertices in the graph, and serves as a relevant property of all types of graphs that are nowadays frequently studied. Examples include social networks, web-graphs and routing networks. We verify the performance of our parallel approach on a set of large graphs comprised of millions of vertices, and using a CUDA GPU observe an increase in performance of up to 21.1x compared to a CPU algorithm using the same strategy. Based on these results, we provide a characterization of the types of graphs that are well-suited for traversal by means of our parallel diameter algorithm. We furthermore include a comparison of different GPU algorithms for single-source shortest path computations, which is not only a crucial step in computing the diameter, but also relevant in many other distance and neighborhood-based algorithms.
November 17, 2013 by hgpu
