Computing Strongly Connected Components in Parallel on CUDA

Logo poskytovatele
Logo poskytovatele
Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

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

Rok publikování 2011
Druh Článek ve sborníku
Konference Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
www http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6012868
Obor Informatika
Klíčová slova parallel graph algorithms; strongly connected components; CUDA
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.