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

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

孙琳琳1，侯秀萍1，朱波1，孙士明1，高灿2

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

【期刊名称】吉林大学学报（信息科学版）

【年(卷),期】2015(033)001

【总页数】6

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

0 引言

近年来，处理器的发展已经由单核处理器转为多核处理器，由单一主频的提高转为由多个处理核心进行并行计算提高计算性能［1］。虽然多核处理器已经成为主要发展趋势，但传统的串行程序并不能在多核处理器结构下获得性能的提升。为了使串行程序能有效利用多核处理器硬件方面的优势，需要对串行程序进行并行化处理。目前比较流行的并行编程模型OpenMp，通过在源程序代码中添加编译制导语句，编译器识别这种标识会自动创建线程对程序进行并行化。同时在多核处理器系统中，多个线程可以同时在不同的处理核心上运行，以达