Parametric multi-step scheme for GPU-accelerated graph
decomposition into strongly connected components

D 2017

Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components

ALDEGHERI, Stefano; Jiří BARNAT; Nicola BOMBIERI; Federico BUSATO; Milan ČEŠKA et. al.

Základní údaje

Originální název

Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components

Autoři

ALDEGHERI, Stefano; Jiří BARNAT; Nicola BOMBIERI; Federico BUSATO a Milan ČEŠKA

Vydání

Cham, 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016, od s. 519-531, 13 s. 2017

Nakladatel

Springer Verlag

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Švýcarsko

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/17:00100646

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-58942-8

ISSN

DOI

https://doi.org/10.1007/978-3-319-58943-5_42

UT WoS

000529303100042

EID Scopus

2-s2.0-85020418207

Klíčová slova anglicky

Directed graphs; Distributed computer systems; Problem solving

Štítky

core_A, firank_A

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 7. 1. 2019 14:28, RNDr. Pavel Šmerk, Ph.D.

Anotace

V originále

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 high-performance, e.g., GPU-accelerated, algorithms to solve it. Unfortunately, among existing GPU-enabled 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 multi-step scheme to evaluate existing GPU-accelerated 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 GPU-based 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 GPU-accelerated SCC decomposition.

Citovat

ALDEGHERI, Stefano; Jiří BARNAT; Nicola BOMBIERI; Federico BUSATO a Milan ČEŠKA. Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components. In 22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016. Cham: Springer Verlag, 2017, s. 519-531. ISBN 978-3-319-58942-8. Dostupné z: https://doi.org/10.1007/978-3-319-58943-5_42.

@inproceedings{1417426,
   author = {Aldegheri, Stefano and Barnat, Jiří and Bombieri, Nicola and Busato, Federico and Češka, Milan},
   address = {Cham},
   booktitle = {22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016},
   doi = {https://doi.org/10.1007/978-3-319-58943-5_42},
   keywords = {Directed graphs; Distributed computer systems; Problem solving},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Cham},
   isbn = {978-3-319-58942-8},
   pages = {519-531},
   publisher = {Springer Verlag},
   title = {Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components},
   year = {2017}
}

TY  - CONF
ID  - 1417426
AU  - Aldegheri, Stefano - Barnat, Jiří - Bombieri, Nicola - Busato, Federico - Češka, Milan
PY  - 2017
TI  - Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components
PB  - Springer Verlag
CY  - Cham
SN  - 9783319589428
KW  - Directed graphs
KW  - Distributed computer systems
KW  - Problem solving
N2  - 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 high-performance, e.g., GPU-accelerated, algorithms to solve it. Unfortunately, among existing GPU-enabled 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 multi-step scheme to evaluate existing GPU-accelerated 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 GPU-based 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 GPU-accelerated SCC decomposition.
ER  -

ALDEGHERI, Stefano; Jiří BARNAT; Nicola BOMBIERI; Federico BUSATO a Milan ČEŠKA. Parametric multi-step scheme for GPU-accelerated graph decomposition into strongly connected components. In \textit{22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016}. Cham: Springer Verlag, 2017, s.~519-531. ISBN~978-3-319-58942-8. Dostupné z: https://doi.org/10.1007/978-3-319-58943-5\_{}42.

Přehled o publikaci