A parallel implementation of the Bellman Ford algorithm using a GPU ...

Multimed Tools Appl DOI 10.1007/s11042-014-2013-3

Accelerating IP routing algorithm using graphics processing unit for high speed multimedia communication Jia Uddin & In-Kyu Jeong & Myeongsu Kang & Cheol-Hong Kim & Jong-Myon Kim

Received: 9 February 2014 / Revised: 28 March 2014 / Accepted: 8 April 2014 # Springer Science+Business Media New York 2014

Abstract This paper presents a Graphics Processing Unit (GPU)-based implementation of a Bellman-Ford (BF) routing algorithm using NVIDIA’s Compute Unified Device Architecture (CUDA). In the proposed GPU-based approach, multiple threads run concurrently over numerous streaming processors in the GPU to dynamically update routing information. Instead of computing the individual vertex distances one-by-one, a number of threads concurrently update a larger number of vertex distances, and an individual vertex distance is represented in a single thread. This paper compares the performance of the GPU-based approach to an equivalent CPU implementation while varying the number of vertices. Experimental results show that the proposed GPUbased approach outperforms the equivalent sequential CPU implementation in terms of execution time by exploiting the massive parallelism inherent in the BF routing algorithm. In addition, the reduction in energy consumption (about 99 %) achieved by using the GPU is reflective of the overall merits of deploying GPUs across the entire landscape of IP routing for emerging multimedia communications. Keywords Bellman-Ford algorithm . IP routing . Graphics processing unit . Clustering computing

J. Uddin : I.