Super Sort Algorithm Using MPI and CUDA
Sorting algorithms have been a subject of research. Throughout the years various sorting algorithms have been implemented and their performance has been evaluated by comparing the space and time complexity. In this paper the super sort sorting algorithm w
- PDF / 703,006 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 694 Views
Abstract Sorting algorithms have been a subject of research. Throughout the years various sorting algorithms have been implemented and their performance has been evaluated by comparing the space and time complexity. In this paper the super sort sorting algorithm with time complexity O(nlogn) has been implemented with MPI and CUDA. The intention is to compare the time taken by super sort algorithm when executed sequentially using C program and the time taken when implemented using CUDA and MPI. Keywords CUDA · MPI programming · Sorting techniques · Super sort algorithm
1 Introduction The array of n random elements is usually sorted in ascending or descending order to perform the needed operations. The sorting of elements is of two types: one uses comparison and the other doesn’t. Comparison-type sorting [1] consists of bubble sorting, insertion sorting, selection sorting, merge sorting, quick sorting and so on. Non-comparison-type sorting consists of radix sorting, bucket sorting and so on [2]. Anaghashree · S. D. Pereira · R. B. Ashwath (B) · S. Rai · N. G. Kini Department of Computer Science and Engineering, Manipal Institute of Technology, Manipal Academy of Higher Education, Manipal 576104, Karnataka, India e-mail: [email protected] Anaghashree e-mail: [email protected] S. D. Pereira e-mail: [email protected] S. Rai e-mail: [email protected] N. G. Kini e-mail: [email protected] © The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2021 S. C. Satapathy et al. (eds.), Intelligent Data Engineering and Analytics, Advances in Intelligent Systems and Computing 1177, https://doi.org/10.1007/978-981-15-5679-1_16
165
166
Anaghashree et al.
In this paper the super sort algorithm [3], a comparison sort algorithm, has been implemented using MPI and then with CUDA. A list of n elements is taken which is unsorted. Forward selection is carried out and a small sorted list is obtained. On the unsorted listed backward sort is carried out and a backward sorted list is obtained. Unsorted list with lesser elements than there were originally is left behind. This happens recursively until no elements are left in the unsorted list. Then the backward and forward sorted lists are merged to obtain the sorted list. This is done with MPI and CUDA in C programming to compare the time taken to sort.
2 Sorting Algorithm The method discussed in this paper arranges the given components in ascending or descending order. The sorting happens in four stages as explained in the following part. When the recursive call finally returns, what is left is a fully sorted array of given input elements. Initially, the first element in the given array is chosen as the maximum element. That element is removed from the given unsorted list of elements and added onto an empty list called the forwardSorted list. The next element is compared with this maximum element. If it happens to be greater than the present element named maximum, it is removed from the list and appe
Data Loading...
