Research Article
GPU Matrix Sort (An Efficient Implementation of Merge Sort)
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 89 - Issue 18 |
| Published: March 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 },
year = { 2014 },
volume = { 89 },
number = { 18 },
pages = { 9-11 },
doi = { 10.5120/15729-4450 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2014
%A Mukul Panwar
%A Monu Kumar
%A Sanjay Bhargava
%T GPU Matrix Sort (An Efficient Implementation of Merge Sort)%T
%J International Journal of Computer Applications
%V 89
%N 18
%P 9-11
%R 10.5120/15729-4450
%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
- 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.
- D. E. Knuth, Art of Computer Programming, Volume 3: Sorting and Searching. Addison-wesely Professional, second ed. , April 1998.
- OpenGL- The Industry Standard for High Performance Graphics. http://www. opengl. org.
- Microsoft's DirectXdeveloper site: http://msdnmicrosoft. com/directx.
- NVIDIA Compute Unified Device Architecture (CUDA) Toolkit, version3. 2. http://www. developer. nvidia. com/object/cuda-3-2-downloads. html.
- 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.
- 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.
- 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.
- M Harris, S Sengupta and JD Owens, "Parallel Prefix sum (scan) with CUDA" in GPU Gems 3(H. Naguyen, ed), Addison Wesley, August 2007.
- 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.
- Ujval J Kapasi, William J Dally, Scott Rixner, Peter R Mattson, John D Owens, Operations for data –parallel architecture.
- 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
Keywords