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

研究了快速排序算法,并在其基础上提出了基于多核技术的OpenMP并行编程模型的快速排序算法。实验结果表明,该并行算法具有较高的并行加速比和并行效率。

的实现

编程模型的快速排序算法。实验结

算法是对冒泡排序算法的一种改现代计算机的多核、核技术正在快速发展，何利用众如进， C A. Hor在 16由 . R. ae 9 2年提出。的基本思想是：过它通一

多核实现并行计算提高计算效率，已成为高性能计算技术领域研究的热点。对于配置了多核 C U的共享存储计算机系 P统，目前 O eMP已是一种共享存储并行编程模型的工业标 pn准，有良好的可编程性，具能够显著提高编程和计算效率。

次排序将数据分割成独立的两部分，中一部分的所有数其

据都比另外一部分的所有数据都要小，后再按照此方法对然

这两部分数据分别进行快速排序，整个排序过程可以递归并行处理，以此达到整个数据变成有序序列。3 2串行算法描述 .设要排序的数组为 A[】… N.]首先任意选取一 0 . A[ I, .个数据 (常选用第一个数据 )为关键数据，后将所有比通作然它小的数都放到它之前，有比它大的数放到它之后，个所这

本文分析 O eMP的并行编程模型特点， pn应用 O eMP pn 设计和实现一种快速排序并行算法，并进行 O eMP并行 pn程序与串行程序性能比较，验证本文所采用的 O e MP并 pn行编程方法的有效性。 2 p n P行编程简介 .Oe M并

过程称为一次排序。一次排序的算法描述如下： f) 1设有两个变量 IJ排序开始的时候：=,= 1、, I0 JN.;()以第一个数组元素作为关键数据，赋值给 ky即 2 e,ky A[】 e= 0;

计算机多核技术的发展带动了并行编程方法的研究和发展，其中以 O eMP为代表的并行编程方法是多核计算 pn机并行编程的主要方式。O eMP具有简单、植性好和可 pn移扩展等优点，由一组与平台无关的编译指导命令 (i ci s、环境变量 ( vrn n ai ls和运行库 dr t e) e v e i met r be) n o v a ( ni irr)组成。 O eM P的缩主语言目前支持 r t l ay u me b pn一

() J始向前搜索，由后开始向前搜索 ( J1, 3从开即 J .)找=到第一个

小于 ky的值 A[,与 A[交换； e J并] I] (1 I 4从开始向后搜索，由前向后搜索 ( I1,到第即 I十 )找：

F ra、和 C+语言，前最新版本为 3 0 ot n C r+当 .。 O eMP是通过编译器对程序中编译指导语句的翻译 pn

个大于 ky的 A[, A[交换； e I与】 J] () 5重复第 3 4步，、直到 IJ=;()数据 A[]置到 I; 6将 0放处

来实现并行计算的。例如在 CC+语言中，语句#rg /+用 pamao pprl l标识一段并行执行的程序块。O eMP编译 m aa e来 l pn指导语句可以根据需要包含多个子句项，在没有其它约束的条件下，子项可以无序和任意选择。例如# rg mp pamao prllo[句… 1使用最为频繁的编译指导语句，且 aal r子 ef是并可以搭配使用 p vt, rpia,, s r a,eut n i r ae fs r t i l t i t rd c o, i t v e f ap v e i sh dl等多种子句。 c eue

排序的整个算法采用递归调用一次排序的过程。设一次排序的函数为 qp s(,递归形式快速排序算法如下： k as)则P OCQu kot ra a, nee w, nee i ) R i sr A r d t It ro Itgr曲 c ( y a g l h

(算法对 dt[ w…hg]的数据进行快速排序本 a 1 a o i中 hI o< gh F lw hi The n

O e MP并行编程模式主要有两种： okji pn①fr- n模型， o常用于开发计算任务中内在的循环级并行性。其中 fr责建 bk负

qp s(aalw,J, k asdt, o hg k; h q i sr dt,o kI; uc ot a lw, -) k ( a q i sr dt,+,ih; uc ot a k l hg) k ( aE dI n FEN D PR0C

立多线程，启动多个线程完成并行计算量的任务； i i n使各线 o程汇集于主线程，由主线程完成串行计算量的任务，这种模式较为简单直观。②编写类似 S MD形式的程序， P利用 O eMP pn 的库函数 o g t num t ed(和 o g t tr a nm(可 mp e h as) mp e h e d u ) r_ _

_ _ _ _

3 3快速排序并行算法的设计与实现 .通过对传统快速排序串行算法并行化，以形成快速排可序 O eMP并行算法。首先分析计算问题的数据依赖关系， pn挖掘其内在并行性，后进行数据分割，建 N个线程，然创为

以进行任务划分。本文主要采用第二种方式。 3 p nP快速排序并行算法 .O e M

作者简介：佐勇，重庆人，士研究生，究方向：游男，硕研并行计算。一

6一 O

本文来源：https://www.bwwdw.com/article/fut4.html