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

Merge Sort Algorithm Design Based on Multi Thread

作　　者：孙琳琳[1] 侯秀萍[1] 朱波[1] 孙士明[1] 高灿[2] 

机构地区：[1]长春工业大学计算机科学与工程学院,长春130012 [2]苏州大学附属第一医院,江苏苏州215006

出　　处：《吉林大学学报（信息科学版）》2015年第1期105-110,共6页Journal of Jilin University（Information Science Edition）

基　　金：国家科技部863高技术基金资助项目(2011AA040602)

摘　　要：为解决传统递归方式的归并排序算法串行执行效率低的问题,使用数据依赖关系分析方法对归并排序算法进行并行性分析。通过分析发现算法本身具有并行的特征,在多核处理器下使用Open Mp编译制导语句对算法进行直接并行化处理。在数据量较大的情况下,为了使算法执行的速度更快,在多核处理器系统中设置多个线程,并将序列分成多个组,每个线程操作一组数据,最后对多个局部有序的结果进行逐一合并。实验验证结果表明,该并行化算法可使执行速度提高50%以上。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 sort algorithm 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 of a group of data in order to make the algorithm performs faster. Finally, the research merged a plurality of improve the partial results which were ordered. Experiment result shows that this method of parallel algorithm can of execution of the algorithm.

关 键 词：归并排序 多核多线程 OpenMp编译制导语句 数据依赖关系 并行化 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]