1. CUDA-quicksort: an improved GPU-based implementation of quicksort
- Author
-
Luciano Milanesi, Emanuele Manca, Alessandro Orro, Giuliano Armano, and Andrea Manconi
- Subjects
0301 basic medicine ,Sorting algorithm ,Computer Networks and Communications ,Computer science ,Sorting ,02 engineering and technology ,Parallel computing ,Software_PROGRAMMINGTECHNIQUES ,Supercomputer ,Computer Science Applications ,Theoretical Computer Science ,Computational science ,03 medical and health sciences ,CUDA ,030104 developmental biology ,Computational Theory and Mathematics ,Data_FILES ,0202 electrical engineering, electronic engineering, information engineering ,Benchmark (computing) ,020201 artificial intelligence & image processing ,General-purpose computing on graphics processing units ,Software ,Quicksort ,ComputingMethodologies_COMPUTERGRAPHICS - Abstract
Sorting is a very important task in computer science and becomes a critical operation for programs making heavy use of sorting algorithms. General-purpose computing has been successfully used on Graphics Processing Units GPUs to parallelize some sorting algorithms. Two GPU-based implementations of the quicksort were presented in literature: the GPU-quicksort, a compute-unified device architecture CUDA iterative implementation, and the CUDA dynamic parallel CDP quicksort, a recursive implementation provided by NVIDIA Corporation. We propose CUDA-quicksort an iterative GPU-based implementation of the sorting algorithm. CUDA-quicksort has been designed starting from GPU-quicksort. Unlike GPU-quicksort, it uses atomic primitives to perform inter-block communications while ensuring an optimized access to the GPU memory. Experiments performed on six sorting benchmark distributions show that CUDA-quicksort is up to four times faster than GPU-quicksort and up to three times faster than CDP-quicksort. An in-depth analysis of the performance between CUDA-quicksort and GPU-quicksort shows that the main improvement is related to the optimized GPU memory access rather than to the use of atomic primitives. Moreover, in order to assess the advantages of using the CUDA dynamic parallelism, we implemented a recursive version of the CUDA-quicksort. Experimental results show that CUDA-quicksort is faster than the CDP-quicksort provided by NVIDIA, with better performance achieved using the iterative implementation. Copyright © 2015 John Wiley & Sons, Ltd.
- Published
- 2015
- Full Text
- View/download PDF