Implementation of Sorting Algorithms with CUDA: An Empirical Study

Abstract

Sorting algorithms have been studied for more than 3 decades now. The aim of this paper is to implement some of the sorting algorithms using the CUDA language in a GPU environment provided by the Nvidia graphics cards. This empirical study is done for comparing the performance of the sorting algorithms in a run-time environment provided by the GPUs and the CUDA programming language. This study considers the implementation of bubble sort, insertion sort, quicksort, selection sort and shell sort algorithms. It is shown that there is a significant amount of speed-up in using CUDA and the Nvidia architecture instead of a sequential code running on standard architectures.

Keywords

• CUDA,sorting algorithms; GPGPU programming; parallel sorting

Original Research Paper

Abstract

References

1. S. Cook, CUDA Programming: A Developer's Guide to Parallel Computing with GPUs (Applications of Gpu Computing), 1st. ed., Morgan Kaufmann, 2012
2. P. Pacheco, Introduction to Parallel Programming, Morgan Kaufmann, 2012
3. N. Wildt, The CUDA Handbook, A Comprehensive Guide to GPU Programming, Pearson Education, 2013
4. J. Edosomwan, Sorting Algorithm, LAP Lambert Academic Publishing, 2012
5. S. Arora and B. Barak, Computational Complexity: A Modern Approach, 1st. ed., Cambridge University Press, 2009
6. M. Dawra and P. Dawra, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 4, No 3, July 2012
7. D. S. Hirschberg, Communications of ACM, 21(8), 1978
8. B. Wilkinson and M. Allen, Parallel Programming: Techniques Workstations and Parallel Computers, 2nd. ed., Pearson Education, 2005. Using Networked

9. D. Merrill and A. Grimshaw, Revisiting Sorting for GPGPU Stream Architectures, Technical Report CS2010- 03, Department of Computer Science, University of Virginia. February 2010.
10. N. Satish, M. Harris and M. Garland, Designing Efficient Sorting Algorithms for Manycore GPUs, NVIDIA Technical Report NVR-2008-001, Sep. 2008., NVIDIA Corporation.
11. D. B. Kirk and Wen-mei W. Hwu, Programming Massively Parallel Processors: A Hands-On Approach (1st ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2010
12. (2014) http://mathema.tician.de/software/pyCUDA/