Performance evaluation of GPU-based parallel sorting algorithms

Area of Science:

• Computer Science
• High-Performance Computing

Background:

• Sequential sorting methods struggle with large datasets.
• Parallel sorting and GPU computing offer significant speedup potential.

Purpose of the Study:

• Investigate GPU-based parallelization of merge sort, quick sort, bubble sort, radix top-k selection sort, and slow sort using CUDA.
• Evaluate performance, parallel time complexity, and space complexity on modern GPUs.

Main Methods:

• Implemented and optimized GPU-based parallel sorting algorithms (MS, QS, BS, RS, SS) using CUDA.
• Conducted experiments on diverse datasets (random, reverse-sorted, sorted, nearly-sorted).
• Compared GPU-accelerated versions against sequential counterparts.

Main Results:

• Radix Sort achieved ~50x speedup, Quick Sort ~97x, and Merge Sort ~103x on 10 million random elements.
• Bubble Sort showed ~17x improvement but remained slower overall.
• Slow Sort demonstrated ~18.6x speedup.
• New single-GPU implementations achieve 17x to over 100x speedups.

Conclusions:

• GPU-accelerated sorting algorithms offer substantial performance improvements over sequential methods.
• Modern GPUs and CUDA enable significant acceleration for large-scale data sorting tasks.
• Radix, Quick, and Merge Sort show the most promising speedups for parallel processing.