A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2017, Vol 8, Issue 10
Abstract
The modern CPU’s design, which is composed of hierarchical memory and SIMD/vectorization capability, governs the potential for algorithms to be transformed into efficient implementations. The release of the AVX-512 changed things radically, and motivated us to search for an efficient sorting algorithm that can take advantage of it. In this paper, we describe the best strategy we have found, which is a novel two parts hybrid sort, based on the well-known Quicksort algorithm. The central partitioning operation is performed by a new algorithm, and small partitions/arrays are sorted using a branch-free Bitonicbased sort. This study is also an illustration of how classical algorithms can be adapted and enhanced by the AVX-512 extension. We evaluate the performance of our approach on a modern Intel Xeon Skylake and assess the different layers of our implementation by sorting/partitioning integers, double floatingpoint numbers, and key/value pairs of integers. Our results demonstrate that our approach is faster than two libraries of reference: the GNU C++ sort algorithm by a speedup factor of 4, and the Intel IPP library by a speedup factor of 1.4.
Authors and Affiliations
Berenger Bramas
Keywords
Related Articles
- EP ID EP262275
- DOI 10.14569/IJACSA.2017.081044
- Views 100
- Downloads 0
Efficient Retrieval of Text for Biomedical Domain using Data Mining Algorithm
Data mining, a branch of computer science [1], is the process of extracting patterns from large data sets by combining methods from statistics and artificial intelligence with database management. Data mining is se...
Quadrant Based WSN Routing Technique By Shifting Of Origin
A sensor is a miniaturized, low powered (basically battery powered), limited storage device which can sense the natural phenomenon or things and convert it into electrical energy or vice versa using transduction process....
Efficient Algorithm for Maximal Clique Size Evaluation
A large dataset network is considered for computation of maximal clique size (MC). Additionally, its link with popular centrality metrics to decrease uncertainty and complexity and for finding influential points of any n...
A Posteriori Pareto Front Diversification Using a Copula-Based Estimation of Distribution Algorithm
We propose CEDA, a Copula-based Estimation of Distribution Algorithm, to increase the size, achieve high diversity and convergence of optimal solutions for a multiobjective optimization problem. The algorithm exploits th...
A Predictive Model for Solar Photovoltaic Power using the Levenberg-Marquardt and Bayesian Regularization Algorithms and Real-Time Weather Data
The stability of power production in photovoltaics (PV) power plants is an important issue for large-scale gridconnected systems. This is because it affects the control and operation of the electrical grid. An efficient...