Parallel Optimization Strategy of Heap Sort Algorithm under Multi-core Environment
Parallel Optimization Strategy of Heap Sort Algorithm under Multi-core Environment
复制标题
多核环境下堆排序算法的并行优化策略
DOI：
10.1109/icmtma.2015.190
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Li Guoliang
中科院分区：
文献类型：
--
作者：
Wei Zhenhua;L. Zhifeng;Li Guoliang
随着多核和众核平台的普及，面向多核的并行编程和优化已成为计算机领域的研究热点。然而，绝大多数程序员仍然延续着传统的串行编程习惯。同时，主流的算法仍然是串行的。因此，如何有效地将串行程序并行化，高效地编写多核程序成为多核编程领域亟待解决的问题。本文采用基于openMP的并行技术，实现了堆排序算法的优化。首先，基于超立方体模型，将待排序的堆数据划分为n个（n为计算机线程数）块，称为子堆，分别进行排序。首先将问题的规模分解为1/n，然后利用归并排序算法对排序后的子堆进行归并，最后将并行优化堆排序算法与传统堆排序算法进行比较。当数据量达到1000万字节时，本文优化的并行堆排序算法在实验机上的执行效率较传统的串行堆排序算法有了明显的提高。而且，随着数据量的增加，两种算法之间的效率差距将显著加剧。
With the popularity of multi-core and many-core platform, multi-core-oriented parallel programming and optimization has become a research hotspot in computer field. However, the vast majority of programmers are still continuing the traditional serial programming habits. Meanwhile, the mainstream algorithms are still in serial. Therefore, how to parallelize the serial programs effectively and write the multi-core programs efficiently is becoming an urgent problem in the field of multi-core programming. In this paper, the optimization of the heap sort algorithm has been achieved adopting the parallel technology based on openMP. Firstly, based on the hypercube model, the heap data to be sorted are divided into n (n is the computer thread amount) blocks called sub-heap which will be sorted respectively. Thus, the scale of the problem is decomposed into 1/n, secondly, the sorted sub-heaps will be merged using merge sort algorithm, finally, the parallel optimized heap sort algorithm is compared to the traditional heap sort algorithm. When the data quantity comes up to ten million bytes, the execution efficiency of the optimized parallel heap sort algorithm of this paper is improved significantly compared with the traditional serial heap sort algorithm on the experimental computer. Furthermore, the efficiency gap between the two algorithms will be intensified prominently with the increasing data quantity.