Parallelization of Counting Sort
摘要
Counting Sort is a novel sorting algorithm that runs in linear time and is well-known for its ease of use and efficiency when sorting numbers within a certain range. The suggested system investigates the parallelization of Counting Sort utilizing both Message Passing Interface (MPI) and Compute Unified Device Architecture (CUDA) to take advantage of distributed architecture and GPU computation. The proposed parallelization strategy aims to enhance the sorting performance by distributing the workload across multiple processors using MPI and exploiting the parallel processing capabilities of CUDA that are enabled by Graphical Processing Units (GPUs). The MPI framework is employed for inter-process communication and load balancing among distributed nodes, while CUDA is utilized to accelerate the sorting process by harnessing the parallel processing capabilities of modern GPUs. The paper presents the design and implementation details of the parallel Counting Sort algorithm, highlighting the specific challenges introduced for MPI and CUDA integration. Experimental results demonstrate the efficiency and scalability of the proposed parallelization approach, showcasing significant reductions in sorting time for large datasets compared to traditional serial implementations.