Publication Details

Parametric Multi-Step Scheme for GPU-Accelerated Graph Decomposition into Strongly Connected Components

ALDEGHERI Stefano, BARNAT Jiří, BOMBIERI Nicola, BUSATO Federico and ČEŠKA Milan. Parametric Multi-Step Scheme for GPU-Accelerated Graph Decomposition into Strongly Connected Components. In: Proceedings of 2nd Workshop on Performance Engineering for Large Scale Graph Analytics. Lecture Notes in Computer Science, vol. 10104. Cham: Springer Verlag, 2016, pp. 519-531. ISBN 978-3-319-58942-8.
Czech title
Parametrický GPU-Akcelerovaný Algoritmus pro Rozklad Grafů na Silně Souvislé Komponenty
Type
conference paper
Language
english
Authors
Aldegheri Stefano (UV)
Barnat Jiří, prof. RNDr., Ph.D. (FI MUNI)
Bombieri Nicola (UV)
Busato Federico (UV)
Češka Milan, doc. RNDr., Ph.D. (DITS FIT BUT)
Keywords


strongly connected components
GPU-accelerated algorithms
parametric multi-step algorithms
performance evaluation

Abstract

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.

Published
2016
Pages
519-531
Proceedings
Proceedings of 2nd Workshop on Performance Engineering for Large Scale Graph Analytics
Series
Lecture Notes in Computer Science
Volume
10104
Conference
Performance Engineering for Large Scale Graph Analytics, Grenoble, FR
ISBN
978-3-319-58942-8
Publisher
Springer Verlag
Place
Cham, DE
DOI
UT WoS
000529303100042
EID Scopus
BibTeX
@INPROCEEDINGS{FITPUB11295,
   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 Multi-Step Scheme for GPU-Accelerated Graph Decomposition into Strongly Connected Components",
   pages = "519--531",
   booktitle = "Proceedings of 2nd Workshop on Performance Engineering for Large Scale Graph Analytics",
   series = "Lecture Notes in Computer Science",
   volume = 10104,
   year = 2016,
   location = "Cham, DE",
   publisher = "Springer Verlag",
   ISBN = "978-3-319-58942-8",
   doi = "10.1007/978-3-319-58943-5\_42",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/11295"
}
Back to top