Performance Evaluation of Parallel Count Sort using GPU Computing with CUDA
Performance Evaluation of Parallel Count Sort using GPU Computing with CUDA
复制标题
使用 GPU 计算和 CUDA 进行并行计数排序的性能评估
DOI：
10.17485/ijst/2016/v9i15/80080
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. P. Ghrera
中科院分区：
文献类型：
--
作者：
Neetu Faujdar;S. P. Ghrera
目的：排序在计算机科学的许多领域被认为是一个非常重要的应用。目前，在CUDA硬件上使用GPU计算的并行排序算法正在迅速增加。使用GPU计算背后的目标是用户可以获得更多的算法加速。方法：本文主要研究计数排序。它是一种非常有效的排序方法，时间复杂度为O(n)。计数排序的问题在于，不建议将其用于较大的数据集，因为它取决于关键元素的范围。本文针对这一缺陷进行了研究，并利用GPU计算和CUDA并行化了计数排序。发现：我们已经测量了并行计数排序比顺序计数排序获得的加速。排序基准已被用于测试和度量两个版本的计数排序（并行和顺序）的性能。排序基准有六种类型的测试用例，分别是均匀、桶状、高斯、排序、交错和零。在本文中，我们的发现是，我们已经在N=1000到N=10000000的更大数据集上测试了并行和顺序计数排序。改进：经过测试，在使用高斯测试用例的情况下，并行计数排序的效率提高了66倍。我们发现，在所有的测试用例中，并行计数排序的实验结果都优于顺序排序。
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.