Optimized Merge Sort on Modern Commodity Multi-core CPUs

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 byoptimized 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.

Keywords: merge sort, bitonic network, SIMD, AVX

Author: Ming Xu, Xianbin Xu, MengJia Yin, Fang Zheng

Journal Code: jptkomputergg160215

Artikel Terkait :

Jp Teknik Komputer gg 2016

• An Improved Artificial Bee Colony Algorithm for Staged Search
• Multi-Criteria in Discriminant Analysis to Find the Dominant Features
• A Novel Multifunction Digital Chip Design Based on CMOS Technology
• An Improved Adaptive Niche Differential Evolution Algorithm
• Power Quality Analysis of Integration Photovoltaic Generator to Three Phase Grid under Variable Solar Irradiance Level
• A Combined User-order and Chunk-order Algorithm to Minimize the Average BER for Chunk Allocation in SCFDMA Systems
• An Optimized Model for MapReduce Based on Hadoop
• Hierarchical i* Modeling in Requirement Engineering
• The Optimal High Performance Computing Infrastructure for Solving High Complexity Problem
• Transformer Fault Diagnosis Method Based on Dynamic Weighted Combination Model
• Hybrid Hierarchical Collision Detection Based on Data Reuse
• Brightness and Contrast Modification in Ultrasonography Images Using Edge Detection Results
• Recognition of Fission Signals Based on Wavelet Analysis and Neural Network
• Application of Nonlinear Dynamical Methods for Arc Welding Quality Monitoring
• Chaos-Enhanced Cuckoo Search for Economic Dispatch with Valve Point Effects
• GPU CUDA Accelerated Image Inpainting using Fourth Order PDE Equation
• Comparative Analysis of Spatial Decision Tree Algorithms for Burned Area of Peatland in Rokan Hilir Riau
• Action Recognition of Human’s Lower Limbs Based on a Human Joint
• A Soft Error Study on Tri-gate Based FinFET and Junctionless-FinFET 6T SRAM Cell - A Comparison
• Design of AC Charging Interface and Status Acquisition Circuit for Electric Vehicles
• Towards Smooth and High-Quality Bitrate Adaptation for HTTP Adaptive Streaming
• Features Deletion on Multiple Objects Recognition
• Research on Batch Scheduling in Cloud Computing
• Classification of Motorcyclists not Wear Helmet on Digital Image with Backpropagation Neural Network
• Internet Protocol Based Satellite On-Board System