The st-connectivity problem (ST-CON) is a decision problem that asks, for vertices s and t in a graph, if t is reachable from s. Although originally defined for directed graphs, it can also be studied on undirected graphs and used as a building block for solving more complex tasks on large scale graphs. We present solutions to ST-CON based on a high performance Breadth First Search (BFS) executed on clusters of Graphics Processing Units (GPUs) using the Nvidia CUDA platform. To measure performances, we use the number of ST-CONs per second. We present the results for two different implementations that highlight the impact of atomic operations in CUDA.

Solutions to the st-connectivity problem using a GPU-based distributed BFS / Bernaschi, M.; Carbone, G.; Mastrostefano, E.; Vella, F.. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - 76:(2015), pp. 145-153. [10.1016/j.jpdc.2014.09.013]

Solutions to the st-connectivity problem using a GPU-based distributed BFS

Vella F.
2015-01-01

Abstract

The st-connectivity problem (ST-CON) is a decision problem that asks, for vertices s and t in a graph, if t is reachable from s. Although originally defined for directed graphs, it can also be studied on undirected graphs and used as a building block for solving more complex tasks on large scale graphs. We present solutions to ST-CON based on a high performance Breadth First Search (BFS) executed on clusters of Graphics Processing Units (GPUs) using the Nvidia CUDA platform. To measure performances, we use the number of ST-CONs per second. We present the results for two different implementations that highlight the impact of atomic operations in CUDA.
2015
Bernaschi, M.; Carbone, G.; Mastrostefano, E.; Vella, F.
Solutions to the st-connectivity problem using a GPU-based distributed BFS / Bernaschi, M.; Carbone, G.; Mastrostefano, E.; Vella, F.. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - 76:(2015), pp. 145-153. [10.1016/j.jpdc.2014.09.013]
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/332858
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 6
social impact