多核计算环境下快速排序并行算法的实现.pdf

《多核计算环境下快速排序并行算法的实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多核计算环境下快速排序并行算法的实现游佐勇罗省贤(成都理工大学信息工程学院，四川成都610059)[摘要]研究了快速排序算法，并在其基础上提出了基于多核技术的OpenMP并行编程模型的快速排序算法。实验结果表明，该并行算法具有较高的并行加速比和并行效率。【关键词]多核处理器；OpenMP；并行算法；快速排序I．引言现代计算机的多核、众核技术正在快速发展，如何利用多核实现并行计算提高计算效率，已成为高性能计算技术领域研究的热点。对于配置了多核CPU的共享存储计算机系统，目前OpenMV已是一种共享存储并行编程模型

2、的工业标准，具有良好的可编程性，能够显著提高编程和计算效率。本文分析OpenMP的并行编程模型特点，应用OpenMP设计和实现一种快速排序并行算法，并进行OpenMP并行程序与串行程序性能比较，验证本文所采用的OpenMP并行编程方法的有效性。2．OpengP并行编程简介计算机多核技术的发展带动了并行编程方法的研究和发展，其中以OpenMP为代表的并行编程方法是多核计算机并行编程的主要方式。OpenMP具有简单、移植性好和可扩展等优点，由一组与平台无关的编译指导命令(directives)、环境变量(envir

3、onmentvariables)和运行库(runtimelibrary)组成。OpenMP的缩主语言目前支持Fortran、C和C++语言，当前最新版本为3．0。OpenMP是通过编译器对程序中编译指导语句的翻译来实现并行计算的。例如在C／C++语言中，用语句#pragmaompparallel来标识一段并行执行的程序块。Openl旧编译指导语句可以根据需要包含多个子句项，在没有其它约束的条件下，子项可以无序和任意选择。例如撑pragmaompparallelfor[子句⋯】是使用最为频繁的编译指导语句，并且可

4、以搭配使用private，firstprivate，if，lastprivate．reduction，schedule等多种子句。OpenMe并行编稃模式主要有两种：@fork-join模型，常用于开发计算任务中内在的循环级并行性。其中fork负责建立多线程，启动多个线程完成并行计算量的任务：ioin使各线程汇集于主线程，由主线程完成串行计算量的任务，这种模式较为简单直观。②编写类似SPMD形式的程序，利用OpenMP的库函数omp_get_num_threads()和omp_get_thread_num()可

5、以进行任务划分。本文主要采用第二种方式。3．Oper■P快速排序并行算法作者简介：游佐勇，男，重庆人，项士研究生。研究方向：并行计算。一60一3．1问题描述快速排序(quick．sort)算法足对冒泡排序算法的一种改进，由C．A．R．Hoare在1962年提出。它的基本思想是：通过～次排序将数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归并行处理，以此达到整个数据变成有序序列。3．2串行算法描述设要排序的数组为A[O

6、】．．⋯·A[N-l】，首先任意选取一个数据(通常选用第～个数据)作为关键数据，然后将所有比它小的数都放到它之前，所有比它大的数放到它之后，这个过程称为一次排序。一次排序的算法描述如下：(1)设有两个变茸I、J，排序开始的时候：I=0，J=N．1；(2)以第一个数组元素作为关键数据，赋值给key，即key=A[0]：(3)从J开始向前搜索，即由后开始向前搜索(J-J．1)，找到第一个小于key的值A【J】，并与A[I】交换；(4)从I开始向后搜索，即由前向后搜索(I=I+1)，找到第一个大于key的A【I】，与

7、A【J】交换：(5)重复第3、4步，直到I=J；(6)将数据A【0】放置到l处；排序的整个算法采用递归调用一次排序的过程。设一次捧序的函数为qlcpassO，则递归形式快速排序算法如下：PROCQuicksort(Arraydata，Integerlow，Integerhigh)(本算法对data[10w⋯high]ee的数据进行快速排序IFlow

8、nd环ENDPRoC3．3快速捧序并行算法的设计与实现通过对传统快速j{}序串行算法并行化，可以形成快速捧序OpenMP并行算法。首先分析计算问题的数据依赖关系，挖掘其内在并行性，然后进行数据分割，创建N个线程，为每个线程分配一份分割后的数据，各线程分别对各自的数据进行排序后，再利用归并排序算法进行排序。具体过程如图l所示。l到N个线程并行执行图10pengP快速排序流程图由图1所示的