Neetu Faujdar ¹, SatyaPrakash Ghrera ¹

Affiliations
1 Jaypee University of Information Technology, Department of CSE, Waknaghat, Himachal Pradesh, IN

Abstract

Objective: Sorting is considered a very important application in many areas of computer science. Nowadays parallelization of sorting algorithms using GPU computing, on CUDA hardware is increasing rapidly. The objective behind using GPU computing is that the users can get, the more speedup of the algorithms. Methods: In this paper, we have focused on count sort. It is very efficient sort with time complexity O(n). The problem with count sort is that, it is not recommended for larger sets of data because it depends on the range of key elements.In this paper this drawback has been taken for the research concern and we parallelized the count sort using GPU computing with CUDA. Findings: We have measured the speedup achieved by the parallel count sort over sequential count sort. The sorting benchmark has been used to test and measure the performance of both the versions of count sort (parallel and sequential). The sorting benchmark has six types of test cases which are uniform, bucket, Gaussian, sorted, staggered and zero.In this paper, our finding is that we have tested the parallel and sequential count sort on a larger sets of data which vary from N=1000 to N=10000000. Improvement: After testing, we have achieved 66 times more efficient results of the parallel count sort in the case of execution time using Gaussian test case. We found that the parallel count sort performs, the better experimental results over sequential in all the test cases.

Keywords

CUDA, GPU, Parallel Count Sort, Sorting, Sequential Count Sort

Full Text