Implementation of Sorting Algorithms with CUDA: An Empirical Study

Ali Yazici; Hakan Gokahmetoglu

doi:10.18100/ijamec.53457

Implementation of Sorting Algorithms with CUDA: An Empirical Study

Year 2016, , 74 - 77, 28.08.2016

Ali Yazici , Hakan Gokahmetoglu

https://doi.org/10.18100/ijamec.53457

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

References

S. Cook, CUDA Programming: A Developer's Guide to Parallel Computing with GPUs (Applications of Gpu Computing), 1st. ed., Morgan Kaufmann, 2012
P. Pacheco, Introduction to Parallel Programming, Morgan Kaufmann, 2012
N. Wildt, The CUDA Handbook, A Comprehensive Guide to GPU Programming, Pearson Education, 2013
J. Edosomwan, Sorting Algorithm, LAP Lambert Academic Publishing, 2012
S. Arora and B. Barak, Computational Complexity: A Modern Approach, 1st. ed., Cambridge University Press, 2009
M. Dawra and P. Dawra, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 4, No 3, July 2012
D. S. Hirschberg, Communications of ACM, 21(8), 1978
B. Wilkinson and M. Allen, Parallel Programming: Techniques Workstations and Parallel Computers, 2nd. ed., Pearson Education, 2005. Using Networked
D. Merrill and A. Grimshaw, Revisiting Sorting for GPGPU Stream Architectures, Technical Report CS2010- 03, Department of Computer Science, University of Virginia. February 2010.
N. Satish, M. Harris and M. Garland, Designing Efficient Sorting Algorithms for Manycore GPUs, NVIDIA Technical Report NVR-2008-001, Sep. 2008., NVIDIA Corporation.
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
(2014) http://mathema.tician.de/software/pyCUDA/

Original Research Paper

Year 2016, , 74 - 77, 28.08.2016

Ali Yazici , Hakan Gokahmetoglu

https://doi.org/10.18100/ijamec.53457

Abstract

References

S. Cook, CUDA Programming: A Developer's Guide to Parallel Computing with GPUs (Applications of Gpu Computing), 1st. ed., Morgan Kaufmann, 2012
P. Pacheco, Introduction to Parallel Programming, Morgan Kaufmann, 2012
N. Wildt, The CUDA Handbook, A Comprehensive Guide to GPU Programming, Pearson Education, 2013
J. Edosomwan, Sorting Algorithm, LAP Lambert Academic Publishing, 2012
S. Arora and B. Barak, Computational Complexity: A Modern Approach, 1st. ed., Cambridge University Press, 2009
M. Dawra and P. Dawra, IJCSI International Journal of Computer Science Issues, Vol. 9, Issue 4, No 3, July 2012
D. S. Hirschberg, Communications of ACM, 21(8), 1978
B. Wilkinson and M. Allen, Parallel Programming: Techniques Workstations and Parallel Computers, 2nd. ed., Pearson Education, 2005. Using Networked
D. Merrill and A. Grimshaw, Revisiting Sorting for GPGPU Stream Architectures, Technical Report CS2010- 03, Department of Computer Science, University of Virginia. February 2010.
N. Satish, M. Harris and M. Garland, Designing Efficient Sorting Algorithms for Manycore GPUs, NVIDIA Technical Report NVR-2008-001, Sep. 2008., NVIDIA Corporation.
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
(2014) http://mathema.tician.de/software/pyCUDA/

There are 12 citations in total.

Details

Journal Section	Research Article
Authors	Ali Yazici Hakan Gokahmetoglu
Publication Date	August 28, 2016
Published in Issue	Year 2016

Cite

APA	Yazici, A., & Gokahmetoglu, H. (2016). Implementation of Sorting Algorithms with CUDA: An Empirical Study. International Journal of Applied Mathematics Electronics and Computers, 4(3), 74-77. https://doi.org/10.18100/ijamec.53457
AMA	Yazici A, Gokahmetoglu H. Implementation of Sorting Algorithms with CUDA: An Empirical Study. International Journal of Applied Mathematics Electronics and Computers. August 2016;4(3):74-77. doi:10.18100/ijamec.53457
Chicago	Yazici, Ali, and Hakan Gokahmetoglu. “Implementation of Sorting Algorithms With CUDA: An Empirical Study”. International Journal of Applied Mathematics Electronics and Computers 4, no. 3 (August 2016): 74-77. https://doi.org/10.18100/ijamec.53457.
EndNote	Yazici A, Gokahmetoglu H (August 1, 2016) Implementation of Sorting Algorithms with CUDA: An Empirical Study. International Journal of Applied Mathematics Electronics and Computers 4 3 74–77.
IEEE	A. Yazici and H. Gokahmetoglu, “Implementation of Sorting Algorithms with CUDA: An Empirical Study”, International Journal of Applied Mathematics Electronics and Computers, vol. 4, no. 3, pp. 74–77, 2016, doi: 10.18100/ijamec.53457.
ISNAD	Yazici, Ali - Gokahmetoglu, Hakan. “Implementation of Sorting Algorithms With CUDA: An Empirical Study”. International Journal of Applied Mathematics Electronics and Computers 4/3 (August 2016), 74-77. https://doi.org/10.18100/ijamec.53457.
JAMA	Yazici A, Gokahmetoglu H. Implementation of Sorting Algorithms with CUDA: An Empirical Study. International Journal of Applied Mathematics Electronics and Computers. 2016;4:74–77.
MLA	Yazici, Ali and Hakan Gokahmetoglu. “Implementation of Sorting Algorithms With CUDA: An Empirical Study”. International Journal of Applied Mathematics Electronics and Computers, vol. 4, no. 3, 2016, pp. 74-77, doi:10.18100/ijamec.53457.
Vancouver	Yazici A, Gokahmetoglu H. Implementation of Sorting Algorithms with CUDA: An Empirical Study. International Journal of Applied Mathematics Electronics and Computers. 2016;4(3):74-7.