16053

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

Neetu Faujdar, SP Ghrera
Jaypee University of Information Technology Waknaghat, P.O. Waknaghat, The Kandaghat, Distt. Solan, India
Pertanika Journal of Science & Technology, Vol. 24 (2), 331 – 350, 2016

@article{faujdar2016modified,

   title={Modified Levels of Parallel Odd-Even Transposition Sorting Network (OETSN) with GPU Computing using CUDA},

   author={Faujdar, Neetu and Ghrera, SP},

   year={2016}

}

Download Download (PDF)   View View   Source Source   

1645

views

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.
Rating: 0.5/5. From 1 vote.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: