Computing Strongly Connected Components in Parallel on CUDA

Investor logo
Investor logo
Investor logo

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BARNAT Jiří BAUCH Petr BRIM Luboš ČEŠKA Milan

Year of publication 2011
Type Article in Proceedings
Conference Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium
MU Faculty or unit

Faculty of Informatics

Citation
Web http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6012868
Field Informatics
Keywords parallel graph algorithms; strongly connected components; CUDA
Description The problem of decomposing a directed graph into its strongly connected components is a fundamental graph problem inherently present in many scientific and commercial applications. In this paper we show how some of the existing parallel algorithms can be reformulated in order to be accelerated by NVIDIA CUDA technology. In particular, we design a new CUDA-aware procedure for pivot selection and we adapt the particular parallel algorithms for CUDA accelerated computation. We also experimentally demonstrate that with a single GTX 480 GPU card we can easily outperform optimal serial CPU implementation -- by an order of magnitude in most cases, 40 times on some sufficiently big instances. This is a particularly interesting result as unlike the serial CPU case, the asymptotic complexity of the parallel algorithms is not optimal.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.