کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432315 | 688855 | 2015 | 9 صفحه PDF | دانلود رایگان |
• A parallel distributed algorithm to solve st-connectivity problem.
• Based on an enhanced distributed Breadth First Search for GPUs.
• Two different implementations are proposed and compared.
• Number of st-connectivity problems solved per second (NSTPS): a metric to evaluate performances.
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.
Journal: Journal of Parallel and Distributed Computing - Volume 76, February 2015, Pages 145–153