Other formats:
BibTeX
LaTeX
RIS
@inproceedings{920569,
author = {Barnat, Jiří and Bauch, Petr and Brim, Luboš and Češka, Milan},
address = {Anchorage, AK},
booktitle = {Proceedings of 25th IEEE International Parallel & Distributed Processing Symposium},
keywords = {parallel graph algorithms; strongly connected components; CUDA},
language = {eng},
location = {Anchorage, AK},
isbn = {978-1-61284-372-8},
pages = {544 - 555},
publisher = {IEEE Computer Society},
title = {Computing Strongly Connected Components in Parallel on CUDA},
url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6012868},
year = {2011}
}
TY - JOUR
ID - 920569
AU - Barnat, Jiří - Bauch, Petr - Brim, Luboš - Češka, Milan
PY - 2011
TI - Computing Strongly Connected Components in Parallel on CUDA
PB - IEEE Computer Society
CY - Anchorage, AK
SN - 9781612843728
KW - parallel graph algorithms
KW - strongly connected components
KW - CUDA
UR - http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6012868
N2 - 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.
ER -
BARNAT, Jiří, Petr BAUCH, Luboš BRIM and Milan ČEŠKA. Computing Strongly Connected Components in Parallel on CUDA. In \textit{Proceedings of 25th IEEE International Parallel \&{} Distributed Processing Symposium}. Anchorage, AK: IEEE Computer Society, 2011, p.~544 - 555. ISBN~978-1-61284-372-8.
|
