Solutions to the st-connectivity problem using a GPU-based distributed BFS
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Bonani A; Del Fatto V; Gennari R (Association for Computing Machinery, Inc, 2018)Algorithmic thinking is at the core of computational thinking. Tangible interactive solutions can help children develop algorithmic thinking skills. This paper focusses on exploratory research concerning tangibles for graph ...
Bonani A; Del Fatto V; Dodero G; Gennari R (RWTH, 2017)Algorithmic thinking is at the hearth of the best known computational thinking. It requires the abilities to decompose and model a problem with a certain representation, and devise or understand an algorithm for making a ...
Bonani A; Del Fatto V; Dodero G; Gennari R; Raimato G (Springer, 2017)The paper presents exploratory steps of the design of interactive tangible objects for the scaffolding of algorithmic thinking of 9–13 years old school classes, and specifically graph algorithmic thinking. By following a ...