Parallelizing shortest path algorithm for time dependent graphs with flow speed model
Various sequential algorithms for the shortest path problem on time dependent graphs are appearing in the literature. However, these algorithms mostly suffer from long running times and huge memory requirements. These problems are making them unsuitable for navigation applications which need to run on real time data with fast response times. For the shortest path problem with time dependent flow speed model, we propose parallel algorithms based on Modified Dykstra algorithm in order to speed up the running time of the sequential algorithm without requiring much more memory. We develop three different parallel implementations by using Cuda and OpenMP: These are (i) a Cuda based version, (ii) an OpenMP based version and (iii) a hybrid Cuda and OpenMP based version. We get up to 10 fold speedup in the OpenMP version, and 17 fold speed up in the other two versions.
2016 IEEE 10th International Conference on Application of Information and Communication Technologies (AICT)