Dhirendra Pratap Singh ¹, Nilay Khare ¹

Affiliations
1 Department of Computer Science and Engineering, Maulana Ajad National Institute of Technology, Bhopal - 462003, Madhya Pradesh, IN

Abstract

The objective of this research is to propose and implement a fast parallel Single source shortest path (SSSP) algorithm on Graphics Processing Unit (GPU) based highly parallel and cost effective platform for dense and complete graphs. The proposed algorithm is a variant of Dijkstra’s algorithm for SSSP calculation for complete and dense graphs. In place of relaxing all the edges of a selected node as in Dijkstra’s algorithm, it relaxes one-one selected edge of different nodes of the graph simultaneously at any iteration. This paper shows parallel implementation of both Dijkstra’s algorithm and our modified Dijkstra’s algorithm on a GPU-based machine. We evaluate these implementations on NVIDIA Tesla C2075 GPU- based machines. Parallel implementation of proposed modified Dijkstra’s algorithm gives a two to three times speed increase over a parallel Dijkstra’s algorithm on a GPU-based machine for complete and dense graphs. The proposed algorithm has minimized the number of edges relaxed by one parallel thread at any iteration of parallel Dijkstra’s algorithm.

Keywords

CUDA, Graph Algorithm, GPU Computing, Parallel Dijkstra’s Algorithm, Parallel Single Source Shortest Path Algorithm.

Full Text