基于多线程归并排序算法设计

为解决传统递归方式的归并排序算法串行执行效率低的问题, 使用数据依赖关系分析方法对归并排序算法进行并行性分析。通过分析发现算法本身具有并行的特征, 在多核处理器下使用OpenMp编译制导语句对算法进行直接并行化处理。在数据量较大的情况下, 为了使算法执行的速度更快, 在多核处理器系统中设置多个线程, 并将序列分成多个组, 每个线程操作一组数据, 最后对多个局部有序的结果进行逐一合并。实验验证结果表明, 该并行化算法可使执行速度提高50%以上。

Merge Sort Algorithm Design Based on Multi Thread

In order to solve the traditional recursively merge sort algorithm serial execution efficiency of general problems, we used data dependence analysis methods on recursive merge sortalgorithm parallelism analysis. The analysis shows that the algorithm itself has the characteristics of parallel, and multi-core processors can be used to compile OpenMp direct guidance statement on parallel processing algorithms. In case of large amount of data, use multiple threads in a multi processor system, divide the sequence into several groups and set each thread operation ofa group of data in order to make the algorithm performs faster. Finally, the research merged a plurality of partial results which were ordered. Experiment result shows that this method of parallel algorithm can improve the speed of execution of the algorithm.