Name
Abstract | ||
|---|---|---|
Sorting is one of the fundamental operations of Computer Science. Many problems, such as plasma real-time diagnostic, image re-ranking, and suffix array construction, require that we sort several arrays in the form of matrix lines or array segments. We define this type of task as segmented sorting. Considering the importance of this problem, the main goal of this study is to provide insight into different techniques for solving it, while also answering the question What is the best performing strategy? for different combinations of array lengths and segment sizes. In order to perform segmented sorting, we can either call a sorting procedure for each of the array segments or use an implementation specialized in this operation. As an alternative, we explore an approach named fix sort, which adjusts the array to allow off-the-shelf general sorting algorithms to perform segmented sorting. We implemented and compared different methods to sort multiple segments in a shared memory environment using CUDA. Throughout our experiments, we noticed a great variation in performance when using the MGPU and CUB libraries, the bitonic sort from CUDA samples, the fix sort-based strategies, and a radix sort procedure called for each segment. The tests showed that using fix sort can be favorable in some cases, and enabled us to create a guideline for efficient implementation of segmented sorting routines based on the parameters of array lengths and number of segments. |
Year | Venue | Field |
|---|---|---|
2016 | HPCC/SmartCity/DSS | Counting sort,Internal sort,Computer science,Adaptive sort,Parallel computing,Selection sort,External sorting,Bucket sort,Sorting algorithm,Proxmap sort,Distributed computing |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Rafael Schmid | 1 | 0 | 0.34 |
| Flavia Pisani | 2 | 0 | 0.34 |
| Edson Borin | 3 | 38 | 10.27 |
| Edson Norberto Cáceres | 4 | 29 | 7.30 |