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 104
- Downloads 0
Dense Hand-CNN: A Novel CNN Architecture based on Later Fusion of Neural and Wavelet Features for Identity Recognition
Biometric recognition or biometrics has emerged as the best solution for criminal identification and access control applications where resources or information need to be protected from unauthorized access. Biometric tra...
Performance Comparison of Detection, Recognition and Tracking Rates of the different Algorithms
This article discusses the approach of human detection and tracking in a homogeneous domain using surveillance cameras. This is a vast area in which significant research has been taking place from more than a decade and...
A New 30 GHz AMC/PRS RFID Reader Antenna with Circular Polarization
The work on this guideline focus on the development and the design of a circularly polarized metallic EBG antenna fed by two microstrip lines. In order to achieve that purpose, a list of indicative specifications has bee...
Performance Analysis of Keccak f-[1600]
Keccak is the latest Hash Function selected as the winner of NIST Hash Function Competition. SHA-3 is not meant to replace SHA-2 as no significant attacks on SHA-2 have been demonstrated. But it is designed in response t...
Detecting Public Sentiment of Medicine by Mining Twitter Data
The paper presents a computational method that mines, processes and analyzes Twitter data for detecting public sentiment of medicine. Self-reported patient data are collected over a period of three months by mining the T...