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

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

OpenCL Parallel Blocked Approach for Solving All Pairs Shortest Path Problem on GPU

by Manish Pandey, Sanjay Sharma
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 111 - Number 15
Year of Publication: 2015
Authors: Manish Pandey, Sanjay Sharma
10.5120/19613-1500

Manish Pandey, Sanjay Sharma . OpenCL Parallel Blocked Approach for Solving All Pairs Shortest Path Problem on GPU. International Journal of Computer Applications. 111, 15 ( February 2015), 8-17. DOI=10.5120/19613-1500

@article{ 10.5120/19613-1500,
author = { Manish Pandey, Sanjay Sharma },
title = { OpenCL Parallel Blocked Approach for Solving All Pairs Shortest Path Problem on GPU },
journal = { International Journal of Computer Applications },
issue_date = { February 2015 },
volume = { 111 },
number = { 15 },
month = { February },
year = { 2015 },
issn = { 0975-8887 },
pages = { 8-17 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume111/number15/19613-1500/ },
doi = { 10.5120/19613-1500 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:47:57.823904+05:30
%A Manish Pandey
%A Sanjay Sharma
%T OpenCL Parallel Blocked Approach for Solving All Pairs Shortest Path Problem on GPU
%J International Journal of Computer Applications
%@ 0975-8887
%V 111
%N 15
%P 8-17
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
Abstract

All-Pairs Shortest Path Problem (APSP) finds a large number of practical applications in real world. This paper presents a blocked parallel approach for APSP using an open standard framework OpenCL, which provides development environment for utilizing heterogeneous computing elements of computer system and to take advantage of massive parallel capabilities of multi-core processors such as graphics processing unit (GPU) and CPU. This blocked parallel approach exploits the local shared memory of GPU, thereby enhancing the overall performance. The proposed solution is for directed and dense graphs with no negative cycles and is based on blocked Floyd Warshall (FW) and Kleene's algorithm. Like Floyd Warshall this approach is also in-place and therefore requires no extra memory.

References
  1. P. Mateti, Cleveland, Ohio, N. Deo, "Parallel Algorithms for Single Source Shortest Path Problems" Computing 29 Springer, pp 31-49
  2. Rothberg, M. L. E. , Wolfe, M. , "The cache performance and optimizations of blocked algorithms". In: Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating System, pp. 63–74, 1991.
  3. Lumsdaine, D. Gregor, B. Hendrickson, and J. Berry, "Challenges in parallel graph processing," Parallel Processing Letters, vol. 17, no. 1, pp. 5–20, 2007
  4. A. Frieze and L. Rudolph, "A parallel algorithm for all pairs shortest paths in a random graph", Technical Report, Dept. of Com. Sci. , Carnegie-Mellon Univ. (1982).
  5. Park, J. , Penner, M. , Prasanna, V. , "Optimizing graph algorithms for improved cache performance". In: Proc. of International Parallel and Distributed Processing Symposium, 2002.
  6. K. Fatahalian, J. Sugerman, P. Hanrahan, "Understanding the efficiency of GPU algorithms for matrix–matrix multiplication", in: HWWS '04: Proceedings of the ACM SIGGRAPH/ EUROGRAPHICS Conference, ACM, New York, 2004, pp. 133–137.
  7. S. Mu, X. Zhang, N. Zhang, J. Lu, Y. S. Deng, and S. Zhang. "IP routing processing with graphic processors". In DATE '10, March 2010.
  8. P. Harish, P. J. Narayanan, "Accelerating large graph algorithms on the GPU using CUDA", in: Proc. of 14th Int'l Conf. High Performance Computing (HiPC'07), Dec. 2007.
  9. David A. Badar, K. Madduri, "Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2", in: ICPP, pages 523-530, 2006.
  10. Penner, M. , Prasanna, V. , "Cache-friendly implementations of transitive closure", in: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, 2001.
  11. Ullman, J. , Yannakakis, M. : The input/output complexity of transitive closure. In: Proceedings of the1990 ACM SIGMOD International Conference on Management of Data, Volume 19, 1990.
  12. Paolo D'Alberto, A. Nicolau, "R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks", Algorithmica 47 (2) (2007) pp. 203–213.
  13. NVIDIA OpenCL Resources, http://developer. nvidia. com/opencl.
  14. Floyd, R. : Algorithm 97: Shortest path. Communications of the ACM 5 (1962).
  15. OpenCL 1. 2 reference pages, KHRONOS, 2012. http://www. khronos. org/registry/cl/sdk/1. 2/docs/ man/xhtml.
  16. Gary J. Katz, Joseph T. KiderJr, "All-Pairs Shortest-Paths for Large Graphs on the GPU", in: Proceedings of the 23rd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, pages 47-55, 2008.
  17. Venkataraman G. , Sahni S. , Mukhopadhyaya S. , "A blocked all-pairs shortest-paths algorithm". J. Exp. Algorithmics 8 (2003), 2. 2.
  18. Han S. -C. , Franchetti f. , Püschel M. , "Program generation for the all-pairs shortest path problem". In: Parallel Architectures and Compilation Tech-niques (PACT) (2006), pp. 222–232.
  19. Larsen E. , Mcallister D. , "Fast matrix multiplies using graphics hardware". In: Supercomputing, ACM/IEEE 2001 Conference (10-16 Nov. 2001), 43–43.
  20. Owens J. D. , Luebke D. , Govindaraju N. , Harris M. , Krüger J. , Lefohn A. E. , Purcell T, "A survey of general-purpose computation on graphics hardware". In: Computer Graphics Forum 26, 1 (Mar. 2007), 80–113.
  21. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clittord Stein, "An Introduction To Algorithms", McGraw-Hill Book Publication, First Edition, 1990.
  22. Owens J. D. , Davis, Houston, M. , Luebke, D. , Green, S. , "GPU Computing", in: Proceedings of the IEEE, Volume: 96 , Issue: 5 , 2008.
  23. AMD Inc. , "AMD Acclerated Parallel Processing OpenCL Programming Guide", July 2012.
  24. A. Munshi, B. R. Gaster, T. G. Mattson, J. Fung, D. Ginsburg, "OpenCL Programming Guide", Addison-Wesley pub. , 2011.
  25. OpenCL Specification, http://www. khronos. org/ registry/cl/specs/opencl-1. 2. pdf.
  26. Manish Pandey, Sanjay Sharma, "A Parallel Recursive Approach for Solving All Pairs Shortest Path Problem on GPU using OpenCL", International Journal of Computer Science and Information Technologies(IJCSIT), ISSN:0975-9646,vol 5(6),2014,8198-8204
Index Terms

Computer Science
Information Sciences

Keywords

OpenCL Graphics processing Unit All Pairs Shortest Path Floyd Warshall

Powered by PhDFocusTM