Computing Strongly Connected Components in Parallel on CUDA

Jiri Barnat, Petr Bauch, Lubos Brim, Milan Ceska
Faculty of Informatics, Masaryk University, Botanicka 68a, 60200 Brno, Czech Republic
IEEE International Parallel & Distributed Processing Symposium (IPDPS), 2011


   title={Computing Strongly Connected Components in Parallel on CUDA},

   author={Barnat, J. and Bauch, P. and Brim, L. and Ce{v{s}}ka, M.},

   booktitle={Parallel & Distributed Processing Symposium (IPDPS), 2011 IEEE International},





Download Download (PDF)   View View   Source Source   



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 selected parallel algorithms for CUDA accelerated computation. We also experimentally demonstrate that with a single GTX 480 GPU card we can easily outperform the optimal serial CPU implementation by an order of magnitude in most cases, 40 times on some sufficiently big instances. This is an interesting result as unlike the serial CPU case, the asymptotic complexity of the parallel algorithms is not optimal.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: