Parallel implementation of Bellman-ford algorithm using CUDA architecture
Parallel implementation of Bellman-ford algorithm using CUDA architecture
复制标题
使用 CUDA 架构并行实现 Bellman-ford 算法
DOI：
10.1109/iceca.2017.8212794
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Shah
中科院分区：
文献类型：
--
作者：
Ganesh G Surve;M. Shah
涉及数百万个顶点的大型图在许多实际应用中很常见，处理起来很有挑战性。现在有许多应用，如电话网络中的路由、旅行信息系统、数据挖掘、机器人系统等，它们的数据都是用图来表示的，不同的图包含负边权或负边圈，用另一种单源最短路径算法(如Dijkstra算法、A∗算法等)处理效率低下。这些应用的数据每天都在增长，但我们仍然需要它们快速、实时地响应。目前，串行图算法由于耗时较大，已经达到了时间限制。Bellman-Ford算法是解决单源最短路径问题的最佳算法，在图论中被认为是一个优化问题。本文提出了一种Bellman-Ford算法的高性能实现，该算法利用NVIDIA的最新GPU架构的架构特征来提高性能和工作负载效率。对实现的并行Bellman-Ford优化，既面向算法又面向体系结构。本文介绍了实现Bellman-Ford算法并行化的新方法，并使用CUDA框架在NVIDIA GPU架构上实现了该算法的一些扩展或新版本。GPU为NVIDIA架构提供了一个名为CUDA的应用程序编程接口。
The large graphs involving millions of vertices are common in many real life applications and are challenging to process. Now a day there are number of application like routing in telephone network, travelling Information System, Data Mining, Robotic System and its data is represented in a graph and different graph contains negative weight of edges or negative edge cycle and are inefficient to process by another single source shortest path algorithm(e.g. Dijkstra's, A∗, etc.). Data of these applications are growing every day, but we still need fast and real time response from them. At present, the serial graph algorithms have reached the time limitation as they used to take a large amount of time. Bellman-ford algorithm is the best solution to solving single source shortest path problem and which is considered to be an optimization problem in the graph theory. This paper presents a high-performance implementation of the Bellman-Ford algorithm that exploits the architectural features of recent GPU architectures of NVIDIA to improve the performance and workload efficiency. Parallel Bellman-Ford optimizations to the implementation, which are oriented both algorithms and to the architecture. In this paper, we introduce new methods which achieve the parallelizing Bellman-Ford Algorithm and to implement some extended or new versions of this algorithm over NVIDIA GPU architecture using CUDA framework. GPU provides an application programming interface to the NVIDIA architecture named as CUDA.