17223

Fast Sorting Algorithms using AVX-512 on Intel Knights Landing

Berenger Bramas
Max Planck Computing and Data Facility (MPCDF)
arXiv:1704.08579 [cs.MS], (24 Apr 2017)

@article{bramas2017fast,

   title={Fast Sorting Algorithms using AVX-512 on Intel Knights Landing},

   author={Bramas, Berenger},

   year={2017},

   month={apr},

   archivePrefix={"arXiv"},

   primaryClass={cs.MS}

}

Download Download (PDF)   View View   Source Source   Source codes Source codes

689

views

This paper describes fast sorting techniques using the recent AVX-512 instruction set. Our implementations benefit from the latest possibilities offered by AVX-512 to vectorize a two-parts hybrid algorithm: we sort the small arrays using a branch- free Bitonic variant, and we provide a vectorized partitioning kernel which is the main component of the well-known Quicksort. Our algorithm sorts in-place and is straightforward to implement thanks to the new instructions. Meanwhile, we also show how an algorithm can be adapted and implemented with AVX-512. We report a performance study on the Intel KNL where our approach is faster than the GNU C++ sort algorithm for any size in both integer and double floating-point arithmetics by a factor of 4 in average.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: