The st-connectivity problem (ST-CON) is a decision problem that asks, for vertices ss and tt in a graph, if tt is reachable from ss. 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, Massimo; Carbone, Giancarlo; Mastrostefano, Enrico; Vella, Flavio. - In: JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING. - ISSN 0743-7315. - ELETTRONICO. - (2014). [10.1016/j.jpdc.2014.09.013]
Solutions to the st-connectivity problem using a gpu-based distributed bfs
BERNASCHI, Massimo;CARBONE, Giancarlo;MASTROSTEFANO, Enrico;VELLA, FLAVIO
2014
Abstract
The st-connectivity problem (ST-CON) is a decision problem that asks, for vertices ss and tt in a graph, if tt is reachable from ss. 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
