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 103
- Downloads 0
Phishing Websites Classification using Hybrid SVM and KNN Approach
Phishing is a potential web threat that includes mimicking official websites to trick users by stealing their important information such as username and password related to financial systems. The attackers use social eng...
Defect Diagnosis in Rotors Systems by Vibrations Data Collectors Using Trending Software
Vibration measurements have been used to reliably diagnose performance problems in machinery and related mechanical products. A vibration data collector can be used effectively to measure and analyze the machinery...
Developing an Adaptive Language Model for Bahasa Indonesia
A language model is one of the important compo-nents in a speech recognition system. It is commonly developed using a statistical method called n-gram. However, a standard n-gram cannot be used for general domains with s...
Design of Reversible Counter
This article presents a research work on the design and synthesis of sequential circuits and flip-flops that are available in digital arena; and describes a new synthesis design of reversible counter that is optimized in...
Internet of Things and Healthcare Analytics for Better Healthcare Solution: Applications and Challenges
The total number of population in the world will keep on increasing. This will eventually pose challenges towards quality of life for example issues related to healthcare. Hence, a proper solution needs to be devised in...