Modified Levels of Parallel Odd-Even Transposition Sorting Network (OETSN) with GPU Computing using CUDA

Abstract

Sorting huge data requires an enormous amount of time. The time needed for this task can be minimised using parallel processing devices like GPU. The odd-even transposition sorting network algorithm is based on the idea that each level uses an equal number of comparators to arrange data. The existing parallel OETSN algorithm compares the elements in each phase for any type of test case. If the elements are not in the increasing order, then they are swapped. In this way, the algorithm takes the same time for sorting and for unique test cases. In this paper, we propose an algorithm that is the modified version of the existing OETSN algorithm. Our approach reduces the number of levels in the OETSN based on the nature of the data. Time complexity is also reduced from O(n) to O(1) for sorted and zero test cases. The proposed algorithm is tested for six types of test case, which are uniform, Gaussian, zero, bucket, staggered and sorted. The comparison with existing techniques is also presented in this paper. After evaluation, the proposed modified version of OETSN is found to be more efficient in two types of test case i.e. sorted and zero test cases. GPU computing using CUDA hardware is used to test the algorithms. The speedup achieved by the parallel OETSN algorithm over sequential OETSN is also computed. The proposed approach achieves an improvement in execution time that is 981661.6 times faster in the sorted test case and 904620.7 times faster in the zero test case using 2500000 elements and 1024 threads in comparison to the existing parallel OETSN