Conference paperALDEGHERI Stefano, BARNAT Jiří, BOMBIERI Nicola, BUSATO Federico and ČEŠKA Milan. Parametric MultiStep Scheme for GPUAccelerated Graph Decomposition into Strongly Connected Components. In: Proceedings of 2nd Workshop on Performance Engineering for Large Scale Graph Analytics. Cham: Springer Verlag, 2016, pp. 519531. ISBN 9783319589428.  Publication language:  english 

Original title:  Parametric MultiStep Scheme for GPUAccelerated Graph Decomposition into Strongly Connected Components 

Title (cs):  Parametrický GPUAkcelerovaný Algoritmus pro Rozklad Grafů na Silně Souvislé Komponenty 

Pages:  519531 

Proceedings:  Proceedings of 2nd Workshop on Performance Engineering for Large Scale Graph Analytics 

Conference:  Performance Engineering for Large Scale Graph Analytics 

Series:  LNCS 10104 

Place:  Cham, DE 

Year:  2016 

ISBN:  9783319589428 

DOI:  10.1007/9783319589435_42 

Publisher:  Springer Verlag 

Keywords 

strongly connected components GPUaccelerated algorithms parametric multistep algorithms performance evaluation 
Annotation 

The problem of decomposing a directed graph into strongly connected components (SCCs) is a fundamental graph problem that is inherently present in many scientific and commercial applications. Clearly, there is a strong need for good highperformance, e.g., GPUaccelerated, algorithms to solve it. Unfortunately, among existing GPUenabled algorithms to solve the problem, there is none that can be considered the best on every graph, disregarding the graph characteristics. Indeed, the choice of the right and most appropriate algorithm to be used is often left to inexperienced users. In this paper, we introduce a novel parametric multistep scheme to evaluate existing GPUaccelerated algorithms for SCC decomposition in order to alleviate the burden of the choice and to help the user to identify which combination of existing techniques for SCC decomposition would fit an expected use case the most. We support our scheme with an extensive experimental evaluation that dissects correlations between the internal structure of GPUbased algorithms and their performance on various classes of graphs. The measurements confirm that there is no algorithm that would beat all other algorithms in the decomposition on all of the classes of graphs. Our contribution thus represents an important step towards an ultimate solution of automatically adjusted scheme for the GPUaccelerated SCC decomposition. 
BibTeX: 

@INPROCEEDINGS{
author = {Stefano Aldegheri and Ji{\v{r}}{\'{i}} Barnat and
Nicola Bombieri and Federico Busato and Milan
{\v{C}}e{\v{s}}ka},
title = {Parametric MultiStep Scheme for GPUAccelerated
Graph Decomposition into Strongly Connected
Components},
pages = {519531},
booktitle = {Proceedings of 2nd Workshop on Performance Engineering for
Large Scale Graph Analytics},
series = {LNCS 10104},
year = {2016},
location = {Cham, DE},
publisher = {Springer Verlag},
ISBN = {9783319589428},
doi = {10.1007/9783319589435_42},
language = {english},
url = {http://www.fit.vutbr.cz/research/view_pub.php?id=11295}
} 
