Thread-Level Parallel Algorithm for Sorting Integer Sequence on Multi-core Computers
Zhong Cheng, Ke Qi, Liu Jun, Huang Yi-Ran · 2011
According to the characteristics of multi-core architectures and binary storage property of integer sequence, this paper proposes an efficient thread-level parallel algorithm for sorting integer sequence on multi-core computers. The algorithm divides the input integer sequence to several data blocks in main memory and distributes these blocks into the shared L2 cache and private L1 cache respectively, implements dynamically load balance among the processing cores, and utilizes data-level parallel SIMD instructions and thread-binding technique to speed up the sorting procedure. Experiment results show that the algorithm can obtain high speedup and good scalability, and its execution efficiency will not be affected by the data distribution of input integer sequence.