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

Submit your paper
Know more
Reseach Article

GPU Matrix Sort (An Efficient Implementation of Merge Sort)

by Mukul Panwar, Monu Kumar, Sanjay Bhargava
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 89 - Number 18
Year of Publication: 2014
Authors: Mukul Panwar, Monu Kumar, Sanjay Bhargava
10.5120/15729-4450

Mukul Panwar, Monu Kumar, Sanjay Bhargava . GPU Matrix Sort (An Efficient Implementation of Merge Sort). International Journal of Computer Applications. 89, 18 ( March 2014), 9-11. DOI=10.5120/15729-4450

@article{ 10.5120/15729-4450,
author = { Mukul Panwar, Monu Kumar, Sanjay Bhargava },
title = { GPU Matrix Sort (An Efficient Implementation of Merge Sort) },
journal = { International Journal of Computer Applications },
issue_date = { March 2014 },
volume = { 89 },
number = { 18 },
month = { March },
year = { 2014 },
issn = { 0975-8887 },
pages = { 9-11 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume89/number18/15729-4450/ },
doi = { 10.5120/15729-4450 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:09:33.519887+05:30
%A Mukul Panwar
%A Monu Kumar
%A Sanjay Bhargava
%T GPU Matrix Sort (An Efficient Implementation of Merge Sort)
%J International Journal of Computer Applications
%@ 0975-8887
%V 89
%N 18
%P 9-11
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Sorting is one of the frequent used operations in computer science. Due to highly parallel computing nature of GPU architecture; it can be utilized for sorting purpose. We have considered the input array that is to be sorted in a 2D matrix form and applied a modified version of merge sort on that matrix. This modification leads to a much efficient sorting algorithm with reduced complexity. Therefore a lot of work has already been done to improve the efficiency of sorting algorithms. In this paper We have used the GPU architecture for solving the sorting problem.

References
  1. T. H. Coremen, C. E. Leiserson, R. L Rivest and C Stein, Introduction to algorithms, second Edition. The MIT Press and McGrawHill Book Company, 2001.
  2. D. E. Knuth, Art of Computer Programming, Volume 3: Sorting and Searching. Addison-wesely Professional, second ed. , April 1998.
  3. OpenGL- The Industry Standard for High Performance Graphics. http://www. opengl. org.
  4. Microsoft's DirectXdeveloper site: http://msdnmicrosoft. com/directx.
  5. NVIDIA Compute Unified Device Architecture (CUDA) Toolkit, version3. 2. http://www. developer. nvidia. com/object/cuda-3-2-downloads. html.
  6. D. J. Evans and R. C. Dumbar. The parallel Quick sort algorithm Part 1. Run time analysis. Int J. Compute Math, 12:19-55, 1982.
  7. D Cederman and P Tsigas "GPU- Quicksort: A practical quick sort algorithm for graphics processor". J. Exp Algorithms, vol. 14 PP. 1. 4. -1. 24-2009.
  8. N Satish, M Harris and M. Garland "Designing efficient sorting algorithms for manycore GPU's" in 23rd IEEE International Symposium on Parallel and Distributed Processing 1P. 1-10-2009.
  9. M Harris, S Sengupta and JD Owens, "Parallel Prefix sum (scan) with CUDA" in GPU Gems 3(H. Naguyen, ed), Addison Wesley, August 2007.
  10. Timothly J. Prucell Craig Donner, Mike Cammarano, Henrik Wann Jensen, and Pal Hanrahan. Photon Mapping on Programmable Graphics Hardware Pages 41-50. Eurographics Association 2003.
  11. Ujval J Kapasi, William J Dally, Scott Rixner, Peter R Mattson, John D Owens, Operations for data –parallel architecture.
  12. Erik Sintorn and Ulf Assarsson. Fast parallel GPU sorting using a Hybrid algorithm. In workshop on General purpose processing on Graphics processing units 2007.
Index Terms

Computer Science
Information Sciences

Keywords

Sorting Multi-Core CUDA Quicksort.