Narrow Results

The ability of the existence of vectorizing compilers to extract vector instructions from blocks of sequential code does not remove the need for proper choice of software algorithms. In this paper, we study the vectorization of the insertion sorting, shellsort, and radix sortings. To measure their suitability for vectorization, we have implemented them on a Convex C-l, and computed the scalar/vector speedup for each method. We observed that for sorting methods based on compare/exchange, contingent methods often thought unsuitable for vectorization, the insertion sort is well performed, especially when using an M-section approach. And for radix sortings, the LSD methods are more suited to vectorization compared to the MSD methods. Finally, based on our study and experiments, we suggest that the straight radix sorting is a good choice for use on vector supercomputers.

Non-volatile memory (NVM) has emerged as an alternative of the next-generation memory due to its non-volatility, byte addressability, high storage-density, and low-energy consumption. However, NVM also has some limitations, e.g. asymmetric read and write latency. Therefore, at present, it is not realistic to completely replace DRAM with NVM in computer systems. A more feasible scheme is to adopt the hybrid memory architecture composed of NVM and DRAM. Following the assumption of hybrid memory architecture, in this paper, we propose an NVM-friendly sorting algorithm called NVMSorting. Particularly, we introduce a new concept called Natural Run to improve the existing MONTRES algorithm. Further, we apply the proposed NVMSorting to database join algorithms to improve the performance of the existing sort-merge join. To verify the performance of our proposal, we implement six existing sorting algorithms as baselines, including the MONTRES algorithm, and conduct comparative experiments on real Intel Optane DC persistent memory. The results show that NVMSorting outperforms other sorting algorithms in terms of execution time and NVM writes. In addition, the results of the join experiment show that the NVMSorting algorithm achieves the highest performance among all schemes. Especially, in the partially ordered data, the execution time of NVMSorting is 2.9%, 2.7%, and 4.2% less than MONTRES, external sort, and quick sort, respectively. Also, the amount of NVM writes of the NVMSorting is 26.1%, 43.6%, 96.2% less than MONTRES, external sort, and quick sort, respectively.

In this paper, we analyze the dual pivot Quicksort, a variant of the standard Quicksort algorithm, in which two pivots are used for the partitioning of the array. We are solving recurrences of the expected number of key comparisons and exchanges performed by the algorithm, obtaining the exact and asymptotic total average values contributing to its time complexity. Further, we compute the average number of partitioning stages and the variance of the number of key comparisons. In terms of mean values, dual pivot Quicksort does not appear to be faster than ordinary algorithm.