Abstract In this fast changing and uncertain world, to meet the user’s requirements the computer applications based on real world data always try to give responses in the minimum possible time. Single Source Shortest Path (SSSP) calculation is a basic requirement of applications using graphs portraying real world data like social networks and road networks etc. to get useful information from them. Some of these real world data changes very frequently, so recalculation of the shortest path for all nodes of a graph depicting these real world data after small updates of graph structure is an expensive process. To minimize the cost of recalculation shortest path algorithms need to process only the affected part of a graph after any update, and to speed-up any process parallel implementation of algorithm is a frequently used technique. This paper proposes a new parallel batch dynamic SSSP calculation approach and shows its implementation on a CPU- Graphic Processing Unit (GPU) based hybrid machine. The proposed algorithm is defined for positive edge weighted graphs. It accepts multiple edge weight updates simultaneously. It uses parallel modified Bellman Ford algorithm for SSSP recalculation of all affected nodes. Nvidia’s Tesla C2075 GPU is used to run the parallel implementation of the algorithm. The proposed parallel algorithm shows up to a twenty-fold speed increase as compared to best serial algorithm available in literature.

References

[1] Barbehenn M. and Hutchinson S., “Efficient Search and Hierarchical Motion Planning by Dynamically Maintaining Single-Source Shortest Paths Tree,” IEEE Transactions on Robotics and Automation, vol. 11, no. 2, pp. 198-214, 1995.

[2] Bauer R. and Wagner D., “Batch Dynamic Single-Source Shortest Path Algorithms: An Experimental Study,” in Proceedings of International Symposium on Experimental Algorithms, Berlin, pp. 51-62, 2009.

[3] Bellman R., “On A Routing Problem,” Quarterly of Applied Mathematics, vol. 16, no. 1, pp. 87-90, 1958.

[4] Brodal G., Traff J., and Zarolingis C., “A parallel Priority Data Structure With Applications,” in Proceedings of 11th International Parallel Processing Symposium, Geneva, pp. 689-693, 1997.

[5] Buluc A., Gilberta J., and Budaka C., “Solving Path Problems on the GPU,” Parallel Computing, vol. 36, no. 5-6, pp. 241-253, 2010.

[6] Bura W. and Boryczka M., “The Parallel Ant Vehicle Navigation System with CUDA Technology,” in Proceedings of International Conference on Computational Collective Intelligence, Gdynia, pp. 505-514, 2011.

[7] Buriol L., Resende M., and Thorup M., “Speeding Up Dynamic Shortest-Path Algorithms,” INFORMS Journal on Computing, vol. 20, no. 2, pp. 191-204, 2008.

[8] Crauser A., Mehlhom K., Meyer U., and Sanders P., “A Parallelization of Dijkstra’s Shortest Path Algorithm,” in Proceedings of 23rd International Symposium on Mathematical Foundations of Computer Science, Brno, pp. 722-732, 1998.

[9] Crobak J., Berry J., Madduri K., and Bader D., “Advanced Shortest Paths Algorithms on a Massively-Multithreaded Architecture,” in Proceedings of IEEE International Parallel and Distributed Processing Symposium, Rome, pp. 1- 8, 2007.

[10] Dashora S. and Khare N., “Implementation of Graph Algorithms over GPU: A Comparative Analysis,” in Proceedings of IEEE Students' Conference on Electrical, Electronics and Computer Science, Bhopal, pp. 1-8, 2012.

[11] Delling D. and Wagner D., “Landmark-Based Routing in Dynamic Graphs,” International Workshop on Experimental and Efficient Algorithms, Rome, pp. 52-65, 2007.

[12] Dijkstra E., “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959.

[13] Eklund P., Kirkby S., and Pollitt S., “A Dynamic Multi-Source Dijkstra's Algorithm for Vehicle Routing,” in Proceedings of Australian New Zealand Conference on Intelligent Information Systems, Adelaide, pp. 329-333, 1996.

[14] Ford L. and Fulkerson D., Flows in Network, Princeton University Press, 2010.

[15] Frigioni D., Spaccamela A., and Nanni U., “Fully Dynamic Algorithms for Maintaining Shortest Paths Trees,” Journal of Algorithms, vol. 34, no. 2, pp. 251-281, 2000.

[16] Harish P. and Narayanan P., “Accelerating Large Graph Algorithms on the GPU Using CUDA,” in Proceedings of International Conference on High-Performance Computing, Goa, pp. 197- 208, 2007.

[17] Jang H., Park A., and Jung K., “Neural Network Implementation Using CUDA and OpenMP,” in Proceedings of Digital Image Computing: Techniques and Applications, Canberra, pp. 155- 161, 2008.

[18] Kadhar M., “A Deadlock-Free Dynamic Reconfiguration Protocol for Distributed Routing on Interconnection Networks,” The International Arab Journal of Information Technology, vol. 11, no. 6, pp. 616-622, 2014.

[19] Katz G. and Kider J., “All Pairs Shortest-Paths for Large Graphs on the GPU,” in Proceedings of 23rd ACM SIGGRAPH/ EUROGRAPHICS Symposium Graphics Hardware, Sarajevo, pp. 47-55, 2008.

[20] King V. and Thorup M., “A Space Saving Trick for Directed Dynamic Transitive Closure And Shortest Path Algorithms,” in Proceedings of International Computing and Combinatorics Conference, Guilin, pp. 268-277, 2001.

[21] Lattanzi S., Panconesi A., and Sivakumar D., “Milgram-routing in Social Networks,” in Proceedings of 20th International Conference on World Wide Web, Hyderabad, pp. 725-734, 2011.

[22] Leskovec J., “Stanford Large Network Dataset Collection,” Stanford University, http://snap.stanford.edu/data/, Last Visited, 2014.

[23] Li F., Klette R., and Morales S., “An Approximate Algorithm for Solving Shortest Path Problems for Mobile Robots or Driver Assistance,” in Proceedings of Intelligent Vehicles Symposium, Xi'an, pp. 42-47, 2009. Parallel Batch Dynamic Single Source Shortest Path Algorithm and ... 225

[24] Martín P., Torres R., and Gavilanes A., “CUDA Solutions for the SSSP Problem,” in Proceedings of International Conference on Computational Science, Baton Rouge, pp. 904-913, 2009.

[25] Matsumoto K., Nakasato N., and Sedukhin S., “Blocked All-Pairs Shortest Paths Algorithm for Hybrid CPU-GPU System,” in Proceedings of 13th IEEE International Conference on High Performance Computing and Communications, Banff, pp. 145-152, 2011.

[26] Misra S. and Oommen B., “Dynamic Algorithms for the Shortest Path Routing Problem: Learning Automata-Based Solutions,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 35, no. 6, pp. 1179-1192, 2005.

[27] Narva ́ez P., Siu K., and Tzeng H., “New Dynamic Algorithms for Shortest Path Tree Computation,” IEEE/ACM Transactions on Networking, vol. 8, no. 6, pp. 734-746, 2000.

[28] Nickolls J. and Dally W., “The GPU Computing Era,” IEEE Micro, vol. 30, no. 2, pp. 56-69, 2010.

[29] Nishizeki T., Tamassia R., and Wagner D., “Graph Algorithms and Applications,” Dagstuhl- Seminar report, Schloss Dagstuhl, 1998.

[30] NVIDIA Corporation, “CUDA C programming guide (2013),” http://docs.nvidia.com/cuda/pdf/CUDA_C_Progr amming_Guide.pdf, Last Visited, 2014.

[31] Ramalingam G. and Reps T., “On the Computational Complexity of Dynamic Graph Problems,” Theoretical Computer Science, vol. 158, no. 1-2, pp. 233-277, 1996.

[32] Reps T. and Ramalingam G., “An Incremental Algorithm for a Generalization of the Shortest- Path Problem,” Journal of Algorithms, vol. 21, no. 2, pp. 267-305, 1996.

[33] Sancı S. and I¸sler V., “A Parallel Algorithm for UAV Flight Route Planning on GPU,” International Journal of Parallel Programming, vol. 39, no. 6, pp. 809-837, 2011.

[34] Singh D. and Khare N., “Parallel Implementation of the Single Source Shortest Path Algorithm on CPU-GPU Based Hybrid System,” International Journal of Computer Science and Information Security, vol. 11, no. 9, pp. 74-80, 2013.

[35] Sintorn E. and Assarsson U., “Fast Parallel GPU- Sorting Using a Hybrid Algorithm,” Journal of Parallel and Distributed Computing, vol. 68, no. 10, pp. 1381-1388, 2008.

[36] Tang Y., Zhang Y., and Chen H., “Parallel Shortest Path Algorithm Based On Graph- Partitioning and Iterative Correcting,” in Proceedings of 10th IEEE International Conference on High Performance Computing and Communications, Dalian, pp. 155-161, 2008.

[37] Tran Q., “Designing Efficient Many-Core Parallel Algorithms for All-Pairs Shortest-Paths Using CUDA,” in Proceedings of 7th International Conference on Information Technology: New Generations, Las Vegas, pp. 7- 12, 2010. Dhirendra Singh received his PhD degree in computer science and engineering from the Maulana Azad National Institute Technology, Bhopal, India in 2015. After his Post graduation, he has worked as Software Developer in NIIT Technologies Ltd., New Delhi, India. Currently he is working as Assistant Professor in the department of Computer Science and Engineering, Maulana Azad National Institute Technology, Bhopal, India. Nilay Khare is Ex-HOD of the department of Computer Science and Engineering, Maulana Azad National Institute Technology, Bhopal, India. He is having more than 27 years of teaching and research experience. Currently he is working as Associate Professor in the department of Computer Science and Engineering, Maulana Azad National Institute Technology, Bhopal, India. His research interests include algorithms, theoretical computer science and VLSI design.