Optimized Merge Sort on Modern Commodity Multi-core CPUs

Ming Xu, Xianbin Xu, MengJia Yin, Fang Zheng

Abstract


Sorting is a kind of widely used basic algorithms. As the high performance computing devices are increasingly common, more and more modern commodity machines have the capability of parallel concurrent computing. A new implementation of sorting algorithms is proposed to harness the power of newer SIMD operations and multi-core computing provided by modern CPUs. The algorithm is hybrid by optimized bitonic sorting network and multi-way merge. New SIMD instructions provided by modern CPUs are used in the bitonic network implementation, which adopted a different method to arrange data so that the number of SIMD operations is reduced. Balanced binary trees are used in multi-way merge, which is also different with former implementations. Efforts are also paid on minimizing data moving in memory since merge sort is a kind of memory-bound application. The performance evaluation shows that the proposed algorithm is twice as fast as the sort function in C++ standard library when only single thread is used. It also outperforms radix sort implemented in Boost library.

Full Text:

PDF


DOI: http://dx.doi.org/10.12928/telkomnika.v14i1.2741

Refbacks

  • There are currently no refbacks.


Copyright (c) 2016 Universitas Ahmad Dahlan

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.


TELKOMNIKA Telecommunication, Computing, Electronics and Control
website: http://telkomnika.ee.uad.ac.id
online system: http://journal.uad.ac.id/index.php/TELKOMNIKA
Phone: +62 (274) 563515, 511830, 379418, 371120 ext: 3208
Fax    : +62 (274) 564604

View TELKOMNIKA Stats