S-t connectivity is a decision problem asking, for vertices s and t in a graph, if t is reachable from s. Many parallel solutions for GPUs have been proposed in literature to solve the problem. The most efficient, which rely on two concurrent BFS starting from s and t have shown limitations when applied on sparse graphs (i.e., graphs with low average degree). In this paper we present FAST-CON, an alternative solution based on multi- source BFS and adjacency matrix to better exploit the massive parallelism of the GPU architectures with any type of graph. The results show that FAST-CON achieves speedup up to one order of magnitude for dense graphs and up to two orders of magnitude for sparse graph compared to the state of the art solutions.
FAST-CON: a Multi-source Approach for Efficient S-T Connectivity on Sparse Graphs
Rosalba Giugno;Samuele Cancellieri;Federico Busato;Nicola Bombieri
2023-01-01
Abstract
S-t connectivity is a decision problem asking, for vertices s and t in a graph, if t is reachable from s. Many parallel solutions for GPUs have been proposed in literature to solve the problem. The most efficient, which rely on two concurrent BFS starting from s and t have shown limitations when applied on sparse graphs (i.e., graphs with low average degree). In this paper we present FAST-CON, an alternative solution based on multi- source BFS and adjacency matrix to better exploit the massive parallelism of the GPU architectures with any type of graph. The results show that FAST-CON achieves speedup up to one order of magnitude for dense graphs and up to two orders of magnitude for sparse graph compared to the state of the art solutions.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
