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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Parallel implementation of Bellman-ford algorithm using CUDA architecture


    Contributors:


    Publication date :

    2017-04-01


    Size :

    511527 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    CUDA Implementation of GPU-Accelerated Spectrally Accurate Algorithm

    Jiao, Longyin / Zhao, Liangyu / Xue, Kuiju et al. | AIAA | 2019


    A Bellman-Ford approach to energy efficient routing of electric vehicles

    Abousleiman, Rami / Rawashdeh, Osamah | IEEE | 2015



    A UAV path planning with parallel ACO algorithm on CUDA platform

    Cekmez, Ugur / Ozsiginan, Mustafa / Sahingoz, Ozgur Koray | IEEE | 2014