Performance Analysis of Parallel Bucket Sort

Abstract

One of the most fascinating problems in computer science is sorting. Starting from small scale applications, Sorting algorithms are used in variety of applications such as large scale databases and large scale search engines. Thus, optimizing the sorting algorithms has a big advantage. Bucket sort is one of the most popular comparison based integer sorting algorithm. Optimizing the bucket sort is an interesting research area. Threads, SSE instructions and GPU programing is used to optimize the algorithm. GPUs (graphics processing units) are becoming an attractive computing platform not only for traditional graphics computation but also for general-purpose computation, because of the computational power, programming capabilities and their comparatively low cost modern GPUs have. This improvement of GPUs with highly parallel programming environments such as CUDA has led to a variety of complex general purpose applications with remarkable performance improvements. Algorithm is implemented and tested on windows platform. Visual studio is used to do the implementation. Two methods are used to do the profiling of the algorithm. Own profiler is created using windows timer and Intel Inspector is used as a third party tool for profiling. CUDA was used to for do the General Purpose Computing on Graphics Processing Unit(GPGPU). Results shown that how the algorithm works with different kind of parallelization. For small number of elements, it is better to do the sorting in single thread. Increasing the number of threads doesn’t give any positive results for the optimization. Bottleneck of GPU and CPU is shown on this research clearly. CPU base parallelization is enough for bucket sort which is proven on this research.