A Parallel Implementation Method for Solving the Shortest Path Problem for Vehicular Networks
Salim A. Mohammed Ali, Emad H. Al-Hemiary · 2020
Vehicular networks are becoming an important area in research in many aspects. One aspect is the shortest path problem, since vehicles are mobile and condensed in behaviour, finding the shortest path for all vehicles to their destinations simultaneously and repeatedly is a cumbersome task. In this paper, a known algorithm is used for finding multi-source multi-destination shortest paths among all nodes, which is Hedetniemi's Algorithm. A recent parallel computation method of OpenCL (Open Compute Language) is used to reduce the complexity of the algorithm and achieve faster calculation for the paths simultaneously and repeatedly. Also, the paper investigates the parallelism efficiency and monitor the system performance when using high dimensional input data. A comparison is made through implementing the same algorithm using sequential computation versus parallel computation, and acceleration of 40X speedup was obtained for a significant number of nodes.