Optimized Merge Sort on Modern Commodity Multi-core CPUs
| Main Authors: | Xu, Ming; Wuhan University, Xu, Xianbin; Wuhan University, Yin, MengJia; Wuhan University, Zheng, Fang; Huazhong Agricultural University |
|---|---|
| Format: | Article info application/pdf eJournal |
| Bahasa: | eng |
| Terbitan: |
Universitas Ahmad Dahlan
, 2016
|
| Online Access: |
http://journal.uad.ac.id/index.php/TELKOMNIKA/article/view/2741 http://journal.uad.ac.id/index.php/TELKOMNIKA/article/view/2741/pdf_335 |
Daftar Isi:
- 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.