CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Performance Analysis of Single Source Shortest Path Algorithm over Multiple GPUs in a Network of Workstations using OpenCL and MPI

by Krishnahari Thouti, S. R. Sathe
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 77 - Number 9
Year of Publication: 2013
Authors: Krishnahari Thouti, S. R. Sathe
10.5120/13424-1104

Krishnahari Thouti, S. R. Sathe . Performance Analysis of Single Source Shortest Path Algorithm over Multiple GPUs in a Network of Workstations using OpenCL and MPI. International Journal of Computer Applications. 77, 9 ( September 2013), 31-36. DOI=10.5120/13424-1104

@article{ 10.5120/13424-1104,
author = { Krishnahari Thouti, S. R. Sathe },
title = { Performance Analysis of Single Source Shortest Path Algorithm over Multiple GPUs in a Network of Workstations using OpenCL and MPI },
journal = { International Journal of Computer Applications },
issue_date = { September 2013 },
volume = { 77 },
number = { 9 },
month = { September },
year = { 2013 },
issn = { 0975-8887 },
pages = { 31-36 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume77/number9/13424-1104/ },
doi = { 10.5120/13424-1104 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:48:59.160734+05:30
%A Krishnahari Thouti
%A S. R. Sathe
%T Performance Analysis of Single Source Shortest Path Algorithm over Multiple GPUs in a Network of Workstations using OpenCL and MPI
%J International Journal of Computer Applications
%@ 0975-8887
%V 77
%N 9
%P 31-36
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Graphics Processing Units (GPUs) are being heavily used in various graphics and non-graphics applications. Many practical problems in computing can be represented as graphs to arrive at a particular solution. These graphs contains very large number, up to millions pairs of vertices and edges. In this paper, we present performance analysis of Dijkstra's single source shortest path algorithm over multiple GPU devices in a single machine as well as over a network of workstations using OpenCL and MPI. Experimental results prove that parallel execution of Dijkstra's algorithm has good performance when algorithm is run over multi-GPU devices in a single workstation as opposed to multi-GPU devices over a network of workstations. For our experimentation, we have used workstation having Intel Xeon 6-core Processor; supporting hyper-threading and a total of 24 threads with NVIDIA Quadro FX 3800 GPU device. The two GPU devices are connected by SLI Bridge. Overall, on average we achieved performance improvement up to an order of 10-15x.

References
  1. General-purpose computations using Graphics hardware, http://www. gpgpu. org/
  2. I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fathalian, M. Houston and P. Hanrahan, "Brook for GPUs: Stream Computing on Graphics Hardware," ACM Trans. Graph, Vol. 23, No. 3, 2004, pp. 777-786
  3. NVIDIA CUDA, http://developer. nvidia. com/cuda/
  4. OpenCL, http://www. khronos. org/registry/cl/
  5. Parallel Boost Graph Library, http://osl. iu. edu/research/pbgl/
  6. Jungwon Kim, Sangmin Seo, Jun Lee, Jeongho Nah, Gangwon Jo, and Jaejin Lee, "SnuCL: An OpenCL Framework for Heterogeneous CPU/GPU Clusters," ICS '12 in Proceedings of the 26th International Conference on Supercomputing, pp. 341 — 352, San Servolo Island, Venice, Italy, June 2012.
  7. OpenMPI: Open Source High Performance Computing, http://www. open-mpi. org/
  8. Jun-Dong Cho, Salil Raje, and Majid Sarrafzadeh. "Fast Approximation Algorithms on Maxcut, K-coloring, and K-color ordering for VLSI Applications," IEEE Transactions on Computers, 47(11):1253–1266, 1998.
  9. Thomas Lengauer and Robert Endre Tarjan. "A Fast Algorithm for Finding Dominators in a Flowgraph," ACM Trans. Program. Lang. Syst. , 1(1):121–141, 1979.
  10. P. J. Narayanan. "Single Source Shortest Path Problem on Processor Arrays," in Proceedings of the 4th IEEE Symposium on the Frontiers of Massively Parallel Computing, pages 553–556, 1992.
  11. J. Owens, D. Luebke, N. Govindaraju, M. Harris, J. Kruger, A. Lefohn and T. Purcell, "A Survey of General-Purpose Computation on Graphics Hardware," Computer Graphics Forum 26, 1 (Mar. 2007), pp. 80–113
  12. G. Venkataraman, S. Sahni, and S. Mukhopadhyaya, "A Blocked All-Pairs Shortest-Paths Algorithm," J. Exp. Algorithmics 8 (2003), 2. 2.
  13. Andreas Crauser, Kurt Mehlhorn, Ulrich Meyer and Peter Sanders, "A Parallelization of Dijkstra's Shortest Path Algorithm," MFCS 1998, pp. 722-731
  14. Nick Edmonds, Alex Breuer, Douglas Gregor, and Andrew Lumsdaine, "Single-Source Shortest Paths with the Parallel Boost Graph Library," in 9th {DIMACS} Implementation Challenge: The Shortest Path Problem, November 2006.
  15. G. Stefano, A. Petricola and C. Zaroliagis, "On the implementation of parallel shortest path algorithms on a supercomputer", in Proc. of ISPA'06, pp. 406-417, 2006.
  16. Avi Bleiweiss, "GPU Accelerated Pathfinding," Graphics Hardware 2008: pp. 65-74
  17. Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk and R. F. Werneck, "PHAST: Hardware-Accelerated Shortest Path Trees," IPDPS 2011, pp. 921-931
  18. I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck, "Highway Dimension, Shortest Paths, and Provably Efficient Algorithms," in Proceedings of the 21st Annual ACM–SIAM Symposium on Discrete Algorithms (SODA'10), 2010, pp. 782–793
  19. Gary J. Katz and Joseph T. Kider Jr, "All-Pairs Shortest-Paths for Large Graphs on the GPU," Graphics Hardware 2008, pp. 47-55
  20. P. Harsh and P. J. Narayan, "Accelerating large graph algorithms on the GPU using CUDA", IEEE High Performance Computing, 2007. vol. 4873 of Lecture Notes in Computer Science, Springer, pp. 197–208
  21. Aydin Buluç, John R. Gilbert and Ceren Budak, "Solving path problems on the GPU," Parallel Computing 36(5-6): pp. 241-253 (2010).
  22. R. Pienaar, B. Fischl, V. Caviness, N. Makris, and P. E. Grant, "Parallelizing Dijkstra's Single Source Shortest-path Graph Algorithm", Chapter 16, OpenCL Programming Guide, Addison-Wesley Publishers, 2011.
  23. The OpenCL specifications www. khronos. org/registry/cl/specs/opencl-1. 1. pdf
  24. B. Gaster, L. Howes, D. Kaeli, P. Mistry, and D. Schaa, "Heterogeneous Computing with OpenCL", Morgan Kaufmann Publishers, 2011.
  25. AMD Accelerated Parallel Processing OpenCL Programming Guide, Advanced Micro Devices, Inc. 2012. http://developer. amd. com/appsdk
  26. D. Kirk and W-m. Hwu, Programming Massively Parallel Processors: A Hands-on Approach. Morgan-Kaufmann Publishers, 2010.
  27. A. Munshi, B. Gaster, T. Mattson, J. Fung and D. Ginsburg, OpenCL Programming Guide, Addison-Wesley Publishers, 2011.
  28. M. Scarpino, "OpenCL in Action," Manning publications, 2011.
  29. Dijkstra's Algorithm, http://www. cs. auckland. ac. nz/~jmor159/PLDS210/dijkstra. html
  30. T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, 3rd Edition, The MIT Press.
Index Terms

Computer Science
Information Sciences

Keywords

GPU Computing OpenCL Multi-node GPU Cluster Dijkstra's algorithm Single source shortest path

Powered by PhDFocusTM