Fast Diameter Computation of Large Sparse Graphs using GPUs

Giso H. Dal, Walter A. Kosters, Frank W. Takes
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


   title={Fast Diameter Computation of Large Sparse Graphs using GPUs},

   author={Dal, Giso H. and Kosters, Walter A. and Takes, Frank W.},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: