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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F17%3A00100646" target="_blank" >RIV/00216224:14330/17:00100646 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216305:26230/16:PU126379

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-58943-5_42" target="_blank" >http://dx.doi.org/10.1007/978-3-319-58943-5_42</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-58943-5_42" target="_blank" >10.1007/978-3-319-58943-5_42</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

22nd International Conference on Parallel and Distributed Computing, Euro-Par 2016

ISBN

9783319589428

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

13

Strana od-do

519-531

Název nakladatele

Springer Verlag

Místo vydání

Cham

Místo konání akce

Grenoble; France

Datum konání akce

1. 1. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000529303100042